Tài liệu Lý thuyết đồ thị

ĐỀ TÀI: Lý thuyết đồ thị

Chương 1 : MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ
I. MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ
1. Định nghĩa đồ thị
2. Các thuật ngữ cơ bản
3. Đường đi, chu trình. Đồ thị liên thông.
II. MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ
1 Thuật toán tìm kiếm trên đồ thị
1.1 Tìm kiếm theo chiều sâu trên đồ thị
1.2 Tìm kiếm theo chiều rộng trên đồ thị
1.3 Tìm đường đi và kiểm tra tính liên thông
2 Tìm đường đi ngắn nhất
2.1. Các khái niệm
2.2 Thuật toán Ford – Bellman
2.3 Thuật toán Dijkstra
Chương 2
PHÁT BIỂU BÀI TOÁN LUỒNG TRÊN MẠNG
I. PHÁT BIỂU BÀI TOÁN
1.Mạng. Luồng trong mạng
2. Bài toán luồng cực đại trong mạng
3. Lát cắt. Đường tăng luồng . Định lý Ford- Fulkerson
4. Thuật toán Ford – Fulkerson tìm luồng cực đại trong mạng
II. BÀI TOÁN LUỒNG CỰC ĐẠI VỚI KHẢ NĂNG THÔNG QUA CÁC CUNG – CÁC ĐỈNH
1.Bài toán
2. Giải quyết bài toán
3. Một số bài toán tối ưu tổ hợp ứng dụng từ bài toán luồng
3.1. Bài toán đám cưới vùng quê
3.2. Bài toán về hệ thống đại diện chung
3.3. Về một bài toán tối ưu rời rạc.
3.3.1 Bài toán phân nhóm sinh hoạt
3.3.2 Bài toán lập lịch cho hội nghị
CHƯƠNG III
PHÂN TÍCH VÀ CÀI ĐẶT
I. PHÂN TÍCH BÀI TOÁN
1. Mô hình bài toán
2. Phương pháp giải quyết
3. Biểu diễn đồ thị
3.1 Biểu diễn mạng G với khả năng thông qua các cung - đỉnh
3.2 Biểu diễn mạng G’ tương ứng với mạng G
III. MỘT SỐ HÀM VÀ THỦ TỤC CỦA CHƯƠNG TRÌNH NGUỒN
II. MỘT SỐ GIAO DIỆN CHÍNH CỦA CHƯƠNG TRÌNH
1. Giao diện chính
2. Giao diện nhập ma trân A biểu diễn mạng G = (V,E) với khả năng thông qua các cung các đỉnh.
2. Giao diện biểu diễn mạng với luồng cực đại