Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Lý thuyết đồ thị - Lê Minh Hoàng

Bài giảng Lý thuyết đồ thị cung cấp cho sinh viên những nội dung cơ bản gồm: các khái niệm cơ bản; biểu diễn đồ thị trên máy tính; các thuật toán tìm kiếm trên đồ thị; tính liên thông của đồ thị; vài ứng dụng của các thuật toán tìm kiếm trên đồ thị; chu trình Hamilton, đường đi Hamilton, đồ thị Hamilton; bài toán đường đi ngắn nhất; bài toán cây khung nhỏ nhất; . Mời các bạn cùng tham khảo! | Lý thuyết đồ thị 1 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 Lê Minh Hoàng Lý thuyết đồ thị 2 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 amp D.R.FULKERSON - 1962 .85 11. BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI TRÊN ĐỒ THỊ HAI .