Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Nội dung của bài giảng trình bày về đại cương về đồ thị, đồ thị Euler và đồ thị Hamilton, đồ thị có trọng số và bài toán đường đi ngắn nhất, định nghĩa và tính chất của cây, cây khung và bài toán cây khung nhỏ nhất, biểu diễn đồ thị trên máy tính, đường đi, chu trình và đồ thị liên thông, một số thuật ngữ cơ bản, định nghĩa đồ thị và giới thiệu về đồ thị. | TRƯỜNG ĐẠI HỌC SƯ PHẠM TP.HCM KHOA TOÁN – TIN HỌC TÓM TẮT BÀI GIẢNG Môn LÝ THUYẾT ĐỒ THỊ Giảng viên biên soạn: Nguyễn Ngọc Trung TP.HCM 9.2006 MỤC LỤC Chương 1. Đại cương về đồ thị .3 1.1 Giới thiệu 3 1.2 Định nghĩa đồ thị.3 1.3 Một số thuật ngữ cơ bản 6 1.4 Đường đi, chu trình và đồ thị liên thông 8 1.5 Biểu diễn đồ thị trên máy tính .11 1.5.1 Biểu diễn đồ thị bằng ma trận kề 11 1.5.2 Ma trận liên thuộc đỉnh – cạnh .13 Chương 2. Đồ thị Euler và đồ thị Hamilton.15 2.1 Đồ thị Euler.15 2.2 Đồ thị Hamilton.17 Chương 3. Đồ thị có trọng số và bài toán đường đi ngắn nhất .20 3.1 Đồ thị có trọng số 20 3.2 Bài toán đường đi ngắn nhất 21 3.2.1 Đường đi ngắn nhất xuất phát từ một đỉnh22 3.2.2 Thuật toán Dijkstra – Trường hợp đồ thị không có cạnh/cung âm.25 Chương 4. Cây.27 4.1 Định nghĩa và tính chất của cây .
