Ph n 2.ầ LÝ THUY T Đ Ế Ồ
THỊ
1
Ph n 2ầ
LÝ THUYẾT ĐỒ THỊ
Graph Theory
Ph n 2.ầ LÝ THUY T Đ Ế Ồ
THỊ
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Ị
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Ị
4
Chương 1
CÁC KHÁI NIỆM CƠ BẢN
Ph n 2.ầ LÝ THUY T Đ Ế Ồ
THỊ
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ồ ị