Phần 2. LÝ THUYẾT ĐỒ THỊ
Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
1
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à nội
2
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à nội
3
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à nội
4
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à nội
5
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ị