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 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 MỤC LỤC Chương 1. Đại cương về đồ thị .3 Giới thiệu 3 Định nghĩa đồ Một số thuật ngữ cơ bản 6 Đường đi, chu trình và đồ thị liên thông 8 Biểu diễn đồ thị trên máy tính .11 Biểu diễn đồ thị bằng ma trận kề 11 Ma trận liên thuộc đỉnh – cạnh .13 Chương 2. Đồ thị Euler và đồ thị Đồ thị Đồ thị Chương 3. Đồ thị có trọng số và bài toán đường đi ngắn nhất .20 Đồ thị có trọng số 20 Bài toán đường đi ngắn nhất 21 Đường đi ngắn nhất xuất phát từ một đỉnh22 Thuật toán Dijkstra – Trường hợp đồ thị không có cạnh/cung Chương 4. Định nghĩa và tính chất của cây .
