Báo cáo cấu trúc dữ liệu và giải thuật: Lý thuyết đồ thị

Báo cáo cấu trúc dữ liệu và giải thuật

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ể liên hệ được với nhau hay không ?; hay vấn đề phân biệt hai hợp chất hoá học có cùng
công thức phân tử nhưng lại khác nhau về công thức cấu tạo cũng được giải quyết nhờ mô hình đồ
thị. Hiện nay, môn học này là một trong những kiến thức cơ sở của bộ môn khoa học máy tính

MỤC LỤC

§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. ĐỘ PHỨC TẠP TÍNH TOÁN CỦA BFS VÀ DFS………………………………………………………………………..21
§4. TÍNH LIÊN THÔNG CỦA ĐỒ THỊ ……………………………………………………………………………………. 22
I. ĐỊNH NGHĨA………………………………………………………………………………………………………………………………22
II. TÍNH LIÊN THÔNG TRONG ĐỒ THỊ VÔ HƯỚNG……………………………………………………………………..23
III. ĐỒ THỊ ĐẦY ĐỦ VÀ THUẬT TOÁN WARSHALL……………………………………………………………………23
IV. CÁC THÀNH PHẦN LIÊN THÔNG MẠNH……………………………………………………………………………….26
§5. VÀI ỨNG DỤNG CỦA CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ…………………………………. 36
I. XÂY DỰNG CÂY KHUNG CỦA ĐỒ THỊ …………………………………………………………………………………….36
II. TẬP CÁC CHU TRÌNH CƠ BẢN CỦA ĐỒ THỊ……………………………………………………………………………38
III. ĐỊNH CHIỀU ĐỒ THỊ VÀ BÀI TOÁN LIỆT KÊ CẦU…………………………………………………………………39
IV. LIỆT KÊ KHỚP…………………………………………………………………………………………………………………………44
I. BÀI TOÁN 7 CÁI CẦU………………………………………………………………………………………………………………..47
II. ĐỊNH NGHĨA……………………………………………………………………………………………………………………………..47
III. ĐỊNH LÝ…………………………………………………………………………………………………………………………………..47
IV. THUẬT TOÁN FLEURY TÌM CHU TRÌNH EULER…………………………………………………………………..48
V. CÀI ĐẶT……………………………………………………………………………………………………………………………………48
VI. THUẬT TOÁN TỐT HƠN………………………………………………………………………………………………………….50
§7. CHU TRÌNH HAMILTON, ĐƯỜNG ĐI HAMILTON, ĐỒ THỊ HAMILTON……………………………… 53
I. ĐỊNH NGHĨA………………………………………………………………………………………………………………………………53
II. ĐỊNH LÝ……………………………………………………………………………………………………………………………………53
III. CÀI ĐẶT…………………………………………………………………………………………………………………………………..53
§8. BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT………………………………………………………………………………. 57
I. ĐỒ THỊ CÓ TRỌNG SỐ……………………………………………………………………………………………………………….57
II. BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT…………………………………………………………………………………………57
III. TRƯỜNG HỢP ĐỒ THỊ KHÔNG CÓ CHU TRÌNH ÂM – THUẬT TOÁN FORD BELLMAN………..58
IV. TRƯỜNG HỢP TRỌNG SỐ TRÊN CÁC CUNG KHÔNG ÂM – THUẬT TOÁN DIJKSTRA………….60
V. THUẬT TOÁN DIJKSTRA VÀ CẤU TRÚC HEAP………………………………………………………………………63
VI. TRƯỜNG HỢP ĐỒ THỊ KHÔNG CÓ CHU TRÌNH – THỨ TỰ TÔ PÔ …………………………………………65
VII. ĐƯỜNG ĐI NGẮN NHẤT GIỮA MỌI CẶP ĐỈNH – THUẬT TOÁN FLOYD……………………………..68
VIII. NHẬN XÉT…………………………………………………………………………………………………………………………….70
§9. BÀI TOÁN CÂY KHUNG NHỎ NHẤT ……………………………………………………………………………… 72
I. BÀI TOÁN CÂY KHUNG NHỎ NHẤT…………………………………………………………………………………………72
II. THUẬT TOÁN KRUSKAL (JOSEPH KRUSKAL – 1956) ……………………………………………………………..72
III. THUẬT TOÁN PRIM (ROBERT PRIM – 1957)……………………………………………………………………………76
§10. BÀI TOÁN LUỒNG CỰC ĐẠI TRÊN MẠNG…………………………………………………………………… 80
I. BÀI TOÁN…………………………………………………………………………………………………………………………………..80
II. LÁT CẮT, ĐƯỜNG TĂNG LUỒNG, ĐỊNH LÝ FORD – FULKERSON………………………………………….80
III. CÀI ĐẶT…………………………………………………………………………………………………………………………………..82
IV. THUẬT TOÁN FORD – FULKERSON (L.R.FORD & D.R.FULKERSON – 1962)………………………….85
§11. BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI TRÊN ĐỒ THỊ HAI PHÍA…………………………………………. 89
I. ĐỒ THỊ HAI PHÍA (BIPARTITE GRAPH)…………………………………………………………………………………….89
II. BÀI TOÁN GHÉP ĐÔI KHÔNG TRỌNG VÀ CÁC KHÁI NIỆM…………………………………………………..89
III. THUẬT TOÁN ĐƯỜNG MỞ……………………………………………………………………………………………………..90
IV. CÀI ĐẶT…………………………………………………………………………………………………………………………………..90
§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…………………………………………………………………………………………………….. 95
I. BÀI TOÁN PHÂN CÔNG …………………………………………………………………………………………………………….95
II. PHÂN TÍCH ……………………………………………………………………………………………………………………………….95
III. THUẬT TOÁN………………………………………………………………………………………………………………………….96
IV. CÀI ĐẶT…………………………………………………………………………………………………………………………………100
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……….105
VI. ĐỘ PHỨC TẠP TÍNH TOÁN……………………………………………………………………………………………………106
§13. BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI TRÊN ĐỒ THỊ……………………………………………………….111
I. CÁC KHÁI NIỆM………………………………………………………………………………………………………………………111
II. THUẬT TOÁN EDMONDS (1965)…………………………………………………………………………………………….112
III. PHƯƠNG PHÁP LAWLER (1973)…………………………………………………………………………………………….113
IV. CÀI ĐẶT…………………………………………………………………………………………………………………………………115
V. ĐỘ PHỨC TẠP TÍNH TOÁN…………………………………………………………………………………………………….119