- CÁC THUẬT TOÁN TRÊN ĐỒ THỊ. - ĐỊNH NGHĨA ĐỒ THỊ (GRAPH . - 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Ị. - TÍNH LIÊN THÔNG TRONG ĐỒ THỊ VÔ HƯỚNG. - ĐỒ THỊ ĐẦY ĐỦ VÀ THUẬT TOÁN WARSHALL. - VÀI ỨNG DỤNG CỦA CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ. - XÂY DỰNG CÂY KHUNG CỦA ĐỒ THỊ. - TẬP CÁC CHU TRÌNH CƠ BẢN CỦA ĐỒ THỊ. - ĐỊNH CHIỀU ĐỒ THỊ VÀ BÀI TOÁN LIỆT KÊ CẦU. - CHU TRÌNH EULER, ĐƯỜNG ĐI EULER, ĐỒ THỊ EULER. - CHU TRÌNH HAMILTON, ĐƯỜNG ĐI HAMILTON, ĐỒ THỊ HAMILTON. - ĐỒ THỊ CÓ TRỌNG SỐ. - TRƯỜNG HỢP ĐỒ THỊ KHÔNG CÓ CHU TRÌNH ÂM - THUẬT TOÁN FORD BELLMAN. - TRƯỜNG HỢP ĐỒ THỊ KHÔNG CÓ CHU TRÌNH - THỨ TỰ TÔ PÔ. - BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI TRÊN ĐỒ THỊ HAI PHÍA . - ĐỒ THỊ HAI PHÍA (BIPARTITE GRAPH . - 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 . - THUẬT TOÁN . - 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 . - BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI TRÊN ĐỒ THỊ . - 266 Hình 82: Đồ thị hai phía và bộ ghép M. - 267 Hình 83: Mô hình luồng của bài toán tìm bộ ghép cực đại trên đồ thị hai phía. - 285 Hình 87: Đồ thị G và một bộ ghép M. - Trong đồ thị có hướng, các cạnh được gọi là các cung. - Cạnh liên thuộc, đỉnh kề, bậc Đối với đồ thị vô hướng G = (V, E). - Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 173 §2. - BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH 2.1. - Khi đó ta có thể biểu diễn đồ thị bằng một ma trận vuông A = [aij] cấp n. - Điều đó khá tốn thời gian trong trường hợp đồ thị dày (nhiều cạnh). - Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 175 2.3. - Với đồ thị G = (V, E). - {Ma trận kề của đồ thị} n, i, j: Integer. - Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 177 §3. - CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ 3.1. - BÀI TOÁN Cho đồ thị G = (V, E). - Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 179 OutputFile = 'PATH.OUT'. - {Ma trận kề của đồ thị} Free: array[1..max] of Boolean. - {Khởi tạo đồ thị chưa có cạnh nào} ReadLn(fi, n, m, S, F). - Bài toán đặt ra là phải liệt kê hết các khớp của đồ thị. - Số thành phần liên thông của đồ thị không thay đổi. - {Ma trận kề của đồ thị} Numbering, Low, nC: array[1..max] of Integer. - 1 to n do if a[u, v] then {Xét mọi v kề u} Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 217 if Numbering[v. - CHU TRÌNH EULER, ĐƯỜNG ĐI EULER, ĐỒ THỊ EULER 6.1. - B A D C Hình 72: Mô hình đồ thị của bài toán bảy cái cầu 6.2. - Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 219 Một đồ thị có hướng liên thông yếu G = (V, E) có đường đi Euler nhưng không có chu trình Euler nếu tồn tại đúng hai đỉnh u, v ∈ V sao cho deg+(u. - CÀI ĐẶT Ta sẽ cài đặt thuật toán Fleury trên một đa đồ thị vô hướng. - Input: file văn bản EULER.INP • Dòng 1: Chứa số đỉnh n của đồ thị (n ≤ 100. - Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 221 while not SeekEof(f) do begin ReadLn(f, u, v, k). - Nếu như chu trình C tìm được chứa tất cả các cạnh của đồ thị thì đó là chu trình Euler. - Thuật toán trên có thể dùng để tìm chu trình Euler trong đồ thị có hướng liên thông yếu, mọi đỉnh có bán bậc ra bằng bán bậc vào. - Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 223 P_4_06_2.PAS * Thuật toán hiệu quả tìm chu trình Euler program Euler_Circuit. - {Xoá cạnh đó khỏi đồ thị} Push(v). - B C M E F J K A D H G N I L M D A B C M F G N L I J K N H E M Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 225 §7. - CHU TRÌNH HAMILTON, ĐƯỜNG ĐI HAMILTON, ĐỒ THỊ HAMILTON 7.1. - ĐỊNH NGHĨA Cho đồ thị G = (V, E) có n đỉnh Chu trình (x1, x2. - Đây là một điều kiện đủ để một đồ thị có chu trình Hamilton. - Đồ thị có hướng G liên thông mạnh và có n đỉnh. - {Ma trận kề của đồ thị: a[u, v. - Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 227 end. - Số gán cho mỗi cạnh của đồ thị được gọi là trọng số của cạnh. - Khi đó phát sinh yêu cầu tìm đường đi ngắn nhất giữa hai đỉnh của đồ thị. - Dưới đây ta sẽ xét một số thuật toán tìm đường đi ngắn nhất từ đỉnh S tới đỉnh F trên đơn đồ thị có hướng G = (V, E) có n đỉnh và m cung. - Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 245 8.8. - gán cho những cạnh không có trong đồ thị ban đầu. - Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 247 §9. - Sau đây ta sẽ xét hai thuật toán thông dụng để giải bài toán cây khung nhỏ nhất của đơn đồ thị vô hướng có trọng số. - Đồ thị Gf được gọi là đồ thị tăng luồng. - Ví dụ: với đồ thị tăng luồng Gf như trên, giả sử chọn đường đi . - {Để ý rằng ⏐cf[u, v]⏐ là trọng số của cung (u, v) trên đồ thị tăng luồng} if Abs(cf[u, v. - Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 261 end. - {Dựng đồ thị tăng luồng} if not FindPath then Break. - Tại mỗi bước từ đỉnh u thăm đỉnh v trong BFS, thì Delta[v] có thể được tính bằng giá trị nhỏ nhất trong hai giá trị Delta[u] và trọng số cung (u, v) trên đồ thị tăng luồng. - Bước lặp sẽ tìm đường đi từ A tới B trên đồ thị tăng luồng đồng thời tính luôn các nhãn (Trace[v], Delta[v. - f[u, v]} Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 263 begin Trace[v. - Khi đã tìm được luồng cực đại thì theo thuật toán trên sẽ không có đường đi từ A tới B trên đồ thị tăng luồng. - Mỗi đỉnh v khác với A và B được gán Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 265 khả năng thông qua d[v]. - BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI TRÊN ĐỒ THỊ HAI PHÍA 11.1. - then < Không phải đồ thị hai phía > else . - Ví dụ: với đồ thị hai phía trong hình Hình 82 và bộ ghép M = {(X1, Y1), (X2, Y2)} X3 và Y3 là những đỉnh chưa ghép, các đỉnh khác là đã ghép Đường (X3, Y2, X2, Y1) là đường pha Đường (X3, Y2, X2, Y1, X1, Y3) là đường mở. - X Y Hình 82: Đồ thị hai phía và bộ ghép M 11.3. - Biểu diễn đồ thị hai phía Giả sử đồ thị hai phía G = (X∪Y, E) có các X_đỉnh ký hiệu là X[1], X[2. - Ta sẽ biểu diễn đồ thị hai phía này bằng ma trận A cỡ mxn. - Như vậy nếu thăm tới một Y_đỉnh chưa ghép thì tức là ta tìm đường mở kết thúc Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 269 ở Y_đỉnh chưa ghép đó, quá trình tìm kiếm dừng ngay. - Ví dụ: Biến đổi ma trận trọng số của đồ thị hai phía 3 đỉnh trái, 3 đỉnh phải X1 - Y X2 - Y2. - Như vậy dọc trên đường pha, các 0_cạnh chưa ghép và những Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 275 0_cạnh đã ghép xen kẽ nhau. - Lặp lại thủ tục tìm kiếm trên đồ thị thử tìm đường mở xuất phát ở x* cho tới khi tìm ra đường mở. - X3, tìm thấy đường mở 2 1 2 1 X3 → Y3 Tăng căp Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị X = X4, không thấy đường * mở 2 2 VisitedX = {X3, X4} 2 2 VisitedY = {Y Giá trị xoay. - 0) Bước 2: Với mọi đỉnh x*∈X, ta tìm cách ghép x* như sau: Bắt đầu từ đỉnh x*, thử tìm đường mở bắt đầu ở x* bằng thuật toán tìm kiếm trên đồ thị (BFS hoặc DFS). - var Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 281 c: array[1..max, 1..max] of Integer. - {Khởi gán nơi xuất phát đường mở, finish = 0 nghĩa là chưa tìm thấy đường mở} Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 283 repeat FindAugmentingPath. - Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 287 for i. - Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 289 x f x f begin repeat x. - BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI TRÊN ĐỒ THỊ 13.1. - Thuật toán đó được xây dựng bằng cách kết hợp một thuật toán tìm kiếm trên đồ thị với phép chập Blossom. - var Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 297 i, m, u, v: Integer. - if (v = start) or (T[match[v]] 0) then BlossomShrink(u, v) else {Nếu không thì ghi vết đường đi, thăm v, thăm luôn cả match[v] và đẩy tiếp match[v] vào Queue} Đại học Sư phạm Hà Nội Các thuật toán trên đồ thị 299 begin T[v. - Một cuốn sách chuyên về Lý thuyết đồ thị. - Bài báo nói về các thuật toán tìm bộ ghép trên đồ thị tổng quát, cả trong trường hợp đồ thị có trọng số [5] Eva Milková