Chuyen de BD HSG 2

MỤC LỤC
MỤC LỤC 1
§0. MỞ ĐẦU 3
§1. CÁC KHÁI NIỆM CƠ BẢN 4
I. ĐỊNH NGHĨA ĐỒ THỊ (GRAPH) 4
II. CÁC KHÁI NIỆM 5
§2. BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 6
I. MA TRẬN LIỀN KỀ (MA TRẬN KỀ) 6
II. DANH SÁCH CẠNH 7
III. DANH SÁCH KỀ 7
IV. NHẬN XÉT 8
§3. CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ 10
I. BÀI TOÁN 10
II. THUẬT TOÁN TÌM KIẾM THEO CHIỀU SÂU (DEPTH FIRST SEARCH) 11
III. THUẬT TOÁN TÌM KIẾM THEO CHIỀU RỘNG (BREADTH FIRST SEARCH) 16
IV. CẤP ĐỘ PHỨC TẠP TÍNH TOÁN CỦA BFS VÀ DFS 20
§4. TÍNH LIÊN THÔNG CỦA ĐỒ THỊ 21
I. ĐỊNH NGHĨA 21
II. TÍNH LIÊN THÔNG TRONG ĐỒ THỊ VÔ HƯỚNG 22
III. ĐỒ THỊ ĐẦY ĐỦ VÀ THUẬT TOÁN WARSHALL 22
IV. CÁC THÀNH PHẦN LIÊN THÔNG MẠNH 25
§5. MỘT VÀI ỨNG DỤNG CỦA CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ 34
I. XÂY DỰNG CÂY KHUNG CỦA ĐỒ THỊ 34
II. TẬP CÁC CHU TRÌNH CƠ BẢN CỦA ĐỒ THỊ 36
III. ĐỊNH CHIỀU ĐỒ THỊ VÀ BÀI TOÁN LIỆT KÊ CẦU 37
IV. LIỆT KÊ KHỚP 42
§6. CHU TRÌNH EULER, ĐƯỜNG ĐI EULER, ĐỒ THỊ EULER 46
I. BÀI TOÁN 7 CÁI CẦU 46
II. ĐỊNH NGHĨA 46
III. ĐỊNH LÝ 46
IV. THUẬT TOÁN FLEURY TÌM CHU TRÌNH EULER 47
V. CÀI ĐẶT 47
VI. THUẬT TOÁN TỐT HƠN 49
§7. CHU TRÌNH HAMILTON, ĐƯỜNG ĐI HAMILTON, ĐỒ THỊ HAMILTON 51
I. ĐỊNH NGHĨA 51
II. ĐỊNH LÝ 51
III. CÀI ĐẶT 51
§8. BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT 55
I. ĐỒ THỊ CÓ TRỌNG SỐ 55
II. BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT 55
III. TRƯỜNG HỢP ĐỒ THỊ KHÔNG CÓ CHU TRÌNH ÂM - THUẬT TOÁN FORD BELLMAN 56
IV. TRƯỜNG HỢP TRỌNG SỐ TRÊN CÁC CUNG KHÔNG ÂM - THUẬT TOÁN DIJKSTRA 59
V. TRƯỜNG HỢP ĐỒ THỊ KHÔNG CÓ CHU TRÌNH - THỨ TỰ TÔ PÔ 61
VI. ĐƯỜNG ĐI NGẮN NHẤT GIỮA MỌI CẶP ĐỈNH - THUẬT TOÁN FLOYD 63
VII. NHẬN XÉT 64
§9. BÀI TOÁN CÂY KHUNG NHỎ NHẤT 66
I. BÀI TOÁN CÂY KHUNG NHỎ NHẤT 66
II. THUẬT TOÁN KRUSKAL (JOSEPH KRUSKAL - 1956) 66
III. THUẬT TOÁN PRIM (ROBERT PRIM - 1957) 70
§10. BÀI TOÁN LUỒNG CỰC ĐẠI TRÊN MẠNG 74
I. BÀI TOÁN 74
II. LÁT CẮT, ĐƯỜNG TĂNG LUỒNG, ĐỊNH LÝ FORD - FULKERSON 74
III. CÀI ĐẶT 76
IV. THUẬT TOÁN FORD - FULKERSON (L.R.FORD & D.R.FULKERSON - 1962) 79
§11. BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI TRÊN ĐỒ THỊ HAI PHÍA 82
I. ĐỒ THỊ HAI PHÍA (BIPARTITE GRAPH) 82
II. BÀI TOÁN GHÉP ĐÔI KHÔNG TRỌNG VÀ CÁC KHÁI NIỆM 82
III. THUẬT TOÁN ĐƯỜNG MỞ 83
IV. CÀI ĐẶT 83
§12. BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI VỚI TRỌNG SỐ CỰC TIỂU TRÊN ĐỒ THỊ HAI PHÍA - THUẬT TOÁN HUNGARI 88
I. BÀI TOÁN PHÂN CÔNG 88
II. PHÂN TÍCH 88
III. THUẬT TOÁN 89
IV. CÀI ĐẶT 93
V. BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI VỚI TRỌNG SỐ CỰC ĐẠI TRÊN ĐỒ THỊ HAI PHÍA 98

§0. MỞ ĐẦU
Trên thực tế có nhiều bài toán liên quan tới một tập các đối tượng và những mối liên hệ giữa chúng, đòi hỏi toán học phải đặt ra một mô hình biểu diễn một cách chặt chẽ và tổng quát bằng ngôn ngữ ký hiệu, đó là đồ thị. Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ thứ XVIII bởi nhà toán học Thuỵ Sĩ Leonhard Euler, ông đã dùng mô hình đồ thị để giải bài toán về những cây cầu Konigsberg nổi tiếng.

Mặc dù Lý thuyết đồ thị đã được khoa học phát triển từ rất lâu nhưng lại có nhiều ứng dụng hiện đại. Đặc biệt trong khoảng vài mươi năm trở lại đây, cùng với sự ra đời của máy tính điện tử và sự phát triển nhanh chóng của Tin học, Lý thuyết đồ thị càng được quan tâm đến nhiều hơn. Đặc biệt là các thuật toán trên đồ thị đã có nhiều ứng dụng trong nhiều lĩnh vực khác nhau như: Mạng máy tính, Lý thuyết mã, Tối ưu hoá, Kinh tế học v.v... Chẳng hạn như trả lời câu hỏi: Hai máy tính trong mạng có thể