Phần 2 LÝ THUYẾT ĐỒ THỊ Graph Theory Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 1 Nội dung Chương 1. Các khái niệm cơ bản Đồ thị vô hướng và có hướng Các thuật ngữ cơ bản Một số dạng đồ thị vô hướng đặc biệt Chương 2. Biểu diễn đồ thị Ma trận kề, ma trận trọng số, Ma trận liên thuộc đỉnh cạnh Danh sách cạnh, Danh sách kề Chương 3. Duyệt đồ thị Tìm kiếm theo chiều sâu; Tìm kiếm theo chiều rộng Tìm đường đi và kiểm tra tính liên thông Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 2 Nội dung Chương 4. Cây và cây khung của đồ thị Cây và các tính chất của cây Cây khung của đồ thị Bài toán cây khung nhỏ nhất Chương 5. Bài toán đường đi ngắn nhất Phát biểu bài toán Đường đi ngắn nhất xuất phát từ một đỉnh (Thuật toán Dijkstra, Ford-Bellman) Đường đi ngắn nhất trên đồ thị không có chu trình Đường đi ngắn nhất giữa mọi cặp đỉnh (Thuật toán Floyd) Chương 6. Bài toán luồng cực đại trong mạng Mạng, luồng và bài toán luồng cực đại Định lý Ford-Fulkerson Thuật toán Ford-Fulkerson Một số ứng dụng Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 3 Chương 1 CÁC KHÁI NIỆM CƠ BẢN Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 4 Chương 1 CÁC KHÁI NIỆM CƠ BẢN 1.1. Đồ thị trong thực tế 1.2. Các loại đồ thị 1.3. Bậc của đỉnh 1.4. Đồ thị con 1.5. Đồ thị đẳng cấu 1.6. Đường đi và chu trình 1.7. Tính liên thông 1.8. Một số loại đồ thị đặc biệt 1.9. Tô màu đồ thị Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 5 Đồ thị là gì? Không phải cái này Trong toán học đời thường hiểu là: Bản vẽ hay Sơ đồ biểu diễn dữ liệu nhờ sử dụng hệ thống toạ độ. Trong toán rời rạc: Đây là cấu trúc rời rạc có tính trực quan cao, rất tiện ích để biểu diễn các quan hệ. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 6 Các ứng dụng thực tế của đồ thị Có tiềm năng ứng dụng trong nhiều lĩnh vực (Đồ thị có thể dùng để biểu diễn các quan hệ. Nghiên