Giải thuật và lập trình: §13. Bài toán tìm bộ ghép cực đại trên đồ thị
13.1. CÁC KHÁI NIỆM
Xét đồ thị G = (V, E), một bộ ghép trên đồ thị G là một tập các cạnh đôi một không có đỉnh chung.
Bài toán tìm bộ ghép cực đại trên đồ thị tổng quát phát biểu như sau:
Cho một đồ thị G, phải tìm một bộ ghép cực đại trên G (bộ ghép có nhiều cạnh nhất).
Với một bộ ghép M của đồ thị G, ta gọi:
Những cạnh thuộc M được gọi là cạnh đã ghép hay cạnh đậm.
Những cạnh không thuộc M được gọi là cạnh chưa ghép hay cạnh nhạt.
Những đỉnh đầu mút của các cạnh đậm được gọi là đỉnh đã ghép, những đỉnh còn lại gọi là đỉnh chưa ghép.
Một đường đi cơ bản (đường đi không có đỉnh lặp lại) được gọi là đường pha nếu nó bắt đầu bằng một cạnh nhạt và tiếp theo là các cạnh đậm, nhạt nằm nối tiếp xen kẽ nhau.
Một chu trình cơ bản (chu trình không có đỉnh trong lặp lại) được gọi là một Blossom nếu nó đi qua ít nhất 3 đỉnh, bắt đầu và kết thúc bằng cạnh nhạt và dọc trên chu trình, các cạnh đậm, nhạt nằm nối tiếp xen kẽ nhau. Đỉnh xuất phát của chu trình (cũng là đỉnh kết thúc) được gọi là đỉnh cơ sở (base) của Blossom.
Đường mở là một đường pha bắt đầu ở một đỉnh chưa ghép và kết thúc ở một đỉnh chưa ghép.
Ví dụ: Với đồ thị G và bộ ghép M trong hình dưới đây:
Đường (8, 1, 2, 5, 6, 4) là một đường pha
Chu trình (2, 3, 4, 6, 5, 2) là một Blossom
Đường (8, 1, 2, 3, 4, 6, 5, 7) là một đường mở
Đường (8, 1, 2, 3, 4, 6, 5, 2, 1, 9) tuy có các cạnh đậm/nhạt xen kẽ nhưng không phải đường pha (và tất nhiên không phải đường mở) vì đây không phải là đường đi cơ bản.
Đồ thị G và một bộ ghép M
Ta dễ dàng suy ra được các tính chất sau:
Đường mở cũng như Blossom đều là đường đi độ dài lẻ với số cạnh nhạt nhiều hơn số cạnh đậm đúng 1 cạnh.
Trong mỗi Blossom, những đỉnh không phải đỉnh cơ sở đều là đỉnh đã ghép và đỉnh ghép với đỉnh đó cũng phải thuộc Blossom.
Vì Blossom là một chu trình nên trong mỗi Blossom, những đỉnh không phải đỉnh cơ sở đều tồn tại hai đường pha từ đỉnh cơ sở đi đến nó, một đường kết thúc bằng cạnh đậm và một đường kết thúc bằng cạnh nhạt, hai đường pha này được hình thành bằng cách đi dọc theo chu trình theo hai hướng ngược nhau. Như ví dụ ở Hình trên, đỉnh 4 có hai đường pha đi đỉnh cơ sở 2 đi tới: (2, 3, 4) là đường pha kết thúc bằng cạnh đậm và (2, 5, 6, 4) là đường pha kết thúc bằng cạnh nhạt.
13.2. Thuật toán Edmonds (1965)
Cơ sở của thuật toán là định lý (C.Berge): Một bộ ghép M của đồ thị G là cực đại khi và chỉ khi không tồn tại đường mở đối với M.
Thuật toán Edmonds:
M := ∅; for (∀ đỉnh u chưa ghép) do if <Tìm đường mở xuất phát từ u> then < Dọc trên đường mở: Loại bỏ những cạnh đậm khỏi M; Thêm vào M những cạnh nhạt; > Result: M là bộ ghép cực đại trên G
Điều khó nhất trong thuật toán Edmonds là phải xây dựng thuật toán tìm đường mở xuất phát từ một đỉnh chưa ghép. 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.
Xét những đường pha xuất phát từ một đỉnh x chưa ghép. Những đỉnh có thể đến được từ x bằng một đường pha kết thúc là cạnh nhạt được gán nhãn "nhạt", những đỉnh có thể đến được từ x bằng một đường pha kết thúc là cạnh đậm được gán nhãn "đậm".
Với một Blossom, ta định nghĩa phép chập (shrink) là phép thay thế các đỉnh trong Blossom bằng một đỉnh duy nhất. Những cạnh nối giữa một đỉnh thuộc Blossom tới một đỉnh v nào đó không thuộc Blossom được thay thế bằng cạnh nối giữa đỉnh chập này với v và giữ nguyên tính đậm/nhạt.
Dễ thấy rằng sau mỗi phép chập, các cạnh đậm vẫn được đảm bảo là bộ ghép trên đồ thị mới:
Phép chập Blossom
Thuật toán tìm đường mở có thể phát biểu như sau:
Trước hết đỉnh xuất phát x được gán nhãn đậm.
Tiếp theo là thuật toán tìm kiếm trên đồ thị bắt đầu từ x, theo nguyên tắc: từ đỉnh đậm chỉ được phép đi tiếp theo cạnh nhạt và từ đỉnh nhạt chỉ được đi tiếp theo cạnh đậm. Mỗi khi thăm tới một đỉnh, ta gán nhãn đậm/nhạt cho đỉnh đó và tiếp tục thao tác tìm kiếm trên đồ thị như bình thường.
Cũng trong quá trình tìm kiếm, mỗi khi phát hiện thấy một cạnh nhạt nối hai đỉnh đậm, ta dừng lại ngay vì nếu gán nhãn tiếp sẽ gặp tình trạng một đỉnh có cả hai nhãn đậm/nhạt, trong trường hợp này, Blossom được phát hiện (xem tính chất của Blossom) và bị chập thành một đỉnh, thuật toán được bắt đầu lại với đồ thị mới cho tới khi trả lời được câu hỏi: "có tồn tại đường mở xuất phát từ x hay không?"
Nếu đường mở tìm được không đi qua đỉnh chập nào thì ta chỉ việc tăng cặp dọc theo đường mở.
Nếu đường mở có đi qua một đỉnh chập thì ta lại nở đỉnh chập đó ra thành Blossom để thay đỉnh chập này trên đường mở bằng một đoạn đường xuyên qua Blossom:
Nở Blossom để dò đường xuyên qua Blossom
Lưu ý rằng không phải Blossom nào cũng bị chập, chỉ những Blossom ảnh hưởng tới quá trình tìm đường mở mới phải chập để đảm bảo rằng đường mở tìm được là đường đi cơ bản. Tuy nhiên việc cài đặt trực tiếp các phép chập Blossom và nở đỉnh khá rắc rối, đòi hỏi một chương trình với độ phức tạp O(n4).
Dưới đây ta sẽ trình bày một phương pháp cài đặt hiệu quả hơn với độ phức tạp O(n3), phương pháp này cài đặt không phức tạp, nhưng yêu cầu phải hiểu rất rõ bản chất thuật toán.
13.3. Phương pháp Lawler (1973)
Trong phương pháp Edmonds, sau khi chập mỗi Blossom thành một đỉnh thì đỉnh đó hoàn toàn lại có thể nằm trên một Blossom mới và bị chập tiếp. Phương pháp Lawler chỉ quan tâm đến đỉnh chập cuối cùng, đại diện cho Blossom ngoài nhất (Outermost Blossom), đỉnh chập cuối cùng này được định danh (đánh số) bằng đỉnh cơ sở của Blossom ngoài nhất.
Cũng chính vì thao tác chập/nở nói trên mà ta cần mở rộng khái niệm Blossom, có thể coi một Blossom là một tập đỉnh nở ra từ một đỉnh chập chứ không đơn thuần chỉ là một chu trình pha cơ bản nữa.
Xét một Blossom B có đỉnh cơ sở là đỉnh r. Với ∀v∈B, v ≠ r, ta lưu lại hai đường pha từ r tới v, một đường kết thúc bằng cạnh đậm và một đường kết thúc bằng cạnh nhạt, như vậy có hai loại vết gãn cho mỗi đỉnh v (hai vết này được cập nhật trong quá trình tìm đường):
S[v] là đỉnh liền trước v trên đường pha kết thúc bằng cạnh đậm, nếu không tồn tại đường pha loại này thì S[v] = 0.
T[v] là đỉnh liền trước v trên đường pha kết thúc bằng cạnh nhạt, nếu không tồn tại đường pha loại này thì T[v] = 0.
Bên cạnh hai nhãn S và T, mỗi đỉnh v còn có thêm.
Nhãn b[v] là đỉnh cơ sở của Blossom chứa v. Hai đỉnh u và v thuộc cùng một Blossom ⇔ b[u] = b[v].
Nhãn match[v] là đỉnh ghép với đỉnh v. Nếu v chưa ghép thì match[v] = 0.
Khi đó thuật toán tìm đường mở bắt đầu từ đỉnh x chưa ghép có thể phát biểu như sau:
Bước 1: (Init)
Hàng đợi Queue dùng để chứa những đỉnh đậm chờ duyệt, ban đầu chỉ gồm một đỉnh đậm x.
Với mọi đỉnh u, khởi gán b[u] = u và match[u] = 0 với ∀u.
Gán S[x] ≠ 0; Với ∀u≠x, gán S[u] = 0;Với ∀v: gán T[v] = 0
Bước 2: (BFS)
Lặp lại các bước sau cho tới khi hàng đợi rỗng:
Với mỗi đỉnh đậm u lấy ra từ Queue, xét những cạnh nhạt (u, v):
Nếu v chưa thăm:
Nếu v là đỉnh chưa ghép ⇒ Tìm thấy đường mở kết thúc ở v, dừng.
Nếu v là đỉnh đã ghép ⇒ thăm v ⇒ thăm luôn match[v] và đẩy match[v] vào Queue.
Sau mỗi lần thăm, chú ý việc lưu vết (hai nhãn S và T)
Nếu v đã thăm
Nếu v là đỉnh nhạt hoặc b[v] = b[u] ⇒ bỏ qua
Nếu v là đỉnh đậm và b[v] ≠ b[u] ta phát hiện được blossom mới chứa u và v, khi đó:
Phát hiện đỉnh cơ sở: Truy vết đường đi ngược từ hai đỉnh đậm u và v theo hai đường pha
về nút gốc, chọn lấy đỉnh a là đỉnh đậm chung gặp đầu tiên trong quá trình truy vết ngược.
Khi đó Blossom mới phát hiện sẽ có đỉnh cơ sở là a.
Gán lại vết: Gọi (a = i1, i2, ..., ip = u) và (a = j1, j2, ..., jq = v) lần lượt là hai đường pha dẫn từ a tới u và v. Khi đó (a = i1, i2, ..., ip = u, jq = v, jq-1, ..., j1 = a) là một chu trình pha đi từ a tới u và v rồi quay trở về a. Bằng cách đi dọc theo chu trình này theo hai hướng ngược nhau, ta có thể gán lại tất cả các nhãn S và T của những đỉnh trên chu trình. Lưu ý rằng không được gán lại nhãn S và T cho những đỉnh k mà b[k] = a, và với những đỉnh k có b[k] ≠ a thì bắt buộc phải gán lại nhãn S và T theo chu trình này bất kể S[k] và T[k] trước đó đã có hay chưa.
Chập Blossom: Xét những đỉnh v mà b[v]∈{b[i1], b[i2], ..., b[ip], b[j1], b[j2], ..., b[jq]}, gán lại b[v] = a. Nếu v là đỉnh đậm (có nhãn S[v] ≠ 0) mà chưa được duyệt tới (chưa bao giờ được đẩy vào Queue) thì đẩy v vào Queue chờ duyệt tiếp tại những bước sau.
Nếu quá trình này chỉ thoát khi hàng đợi rỗng thì tức là không tồn tại đường mở bắt đầu từ x.
Sau đây là một số ví dụ về các trường hợp từ đỉnh đậm u xét cạnh nhạt (u, v):
Trường hợp 1: v chưa thăm và chưa ghép:
⇒ Tìm thấy đường mở
Trường hợp 2: v chưa thăm và đã ghép:
⇒ Thăm cả v lẫn match[v], gán nhãn T[v] và S[match[v]]
Trường hợp 3: v đã thăm, là đỉnh đậm thuộc cùng blossom với u:
⇒ Không xét, bỏ qua
Trường hợp 4: v đã thăm, là đỉnh đậm và b[u] ≠ b[v]:
⇒ Phát hiện Blossom, tìm đỉnh cơ sở a = 3, gán lại nhãn S và T dọc chu trình pha. Đẩy hai đỉnh đậm mới 4, 6 vào hàng đợi, Tại những bước sau, khi duyệt tới đỉnh 6, sẽ tìm thấy đường mở kết thúc ở 8, truy vết theo nhãn S và T tìm được đường (1, 2, 3, 4, 5, 7, 6, 8)
Tư tưởng chính của phương pháp Lawler là dùng các nhãn b[v] thay cho thao tác chập trực tiếp Blossom, dùng các nhãn S và T để truy vết tìm đường mở, tránh thao tác nở Blossom. Phương pháp này dựa trên một nhận xét: Mỗi khi tìm ra đường mở, nếu đường mở đó xuyên qua một Blossom ngoài nhất thì chắc chắn nó phải đi vào Blossom này từ nút cơ sở và thoát ra khỏi Blossom bằng một cạnh nhạt.
13.4. Cài đặt
Ta sẽ cài đặt phương pháp Lawler với khuôn dạng Input/Output như sau:
Input: file văn bản GMATCH.INP
• Dòng 1: Chứa hai số n, m lần lượt là số cạnh và số đỉnh của đồ thị cách nhau ít nhất một dấu cách (n ≤ 100)
• m dòng tiếp theo, mỗi dòng chứa hai số u, v tượng trưng cho một cạnh (u, v) của đồ thị
Output: file văn bản GMATCH.OUT, ghi bộ ghép cực đại tìm được.
Chương trình này sửa đổi một chút mô hình cài đặt trên dựa vào nhận xét:
v là một đỉnh đậm ⇔ v = x hoặc match[v] là một đỉnh nhạt.
Nếu v là đỉnh đậm thì S[v] = match[v]
Vậy thì ta không cần phải sử dụng riêng một mảng nhãn S[v], tại mỗi bước sửa vết, ta chỉ cần sửa nhãn vết T[v] mà thôi. Để kiểm tra một đỉnh v ≠ x có phải đỉnh đậm hay không, ta có thể kiểm tra bằng điều kiện: match[v] có là đỉnh nhạt hay không, hay T[match[v]] có khác 0 hay không.
Chương trình sử dụng các biến với vai trò như sau:
match[v] là đỉnh ghép với đỉnh v
b[v] là đỉnh cơ sở của Blossom chứa v
T[v] là đỉnh liền trước v trên đường pha từ đỉnh xuất phát tới v kết thúc bằng cạnh nhạt, T[v] = 0 nếu quá trình BFS chưa xét tới đỉnh nhạt v.
InQueue[v] là biến Boolean, InQueue[v] = True ⇔ v là đỉnh đậm đã được đẩy vào Queue để chờ duyệt.
start và finish: Nơi bắt đầu và kết thúc đường mở.
P_4_13_1.PAS * Phương pháp Lawler áp dụng cho thuật toán Edmonds program MatchingInGeneralGraph; const InputFile = 'GMATCH.INP'; OutputFile = 'GMATCH.OUT'; max = 100; var a: array[1..max, 1..max] of Boolean; match, Queue, b, T: array[1..max] of Integer; InQueue: array[1..max] of Boolean; n, first, last, start, finish: Integer; procedure Enter; var i, m, u, v: Integer; f: Text; begin Assign(f, InputFile); Reset(f); FillChar(a, SizeOf(a), False); ReadLn(f, n, m); for i := 1 to m do begin ReadLn(f, u, v); a[u, v] := True; a[v, u] := True; end; Close(f); end; procedure Init; {Khởi tạo bộ ghép rỗng} begin FillChar(match, SizeOf(match), 0); end; procedure InitBFS; {Thủ tục này được gọi để khởi tạo trước khi tìm đường mở xuất phát từ start} var i: Integer; begin {Hàng đợi chỉ gồm một đỉnh đậm start} first := 1; last := 1; Queue[1] := start; FillChar(InQueue, SizeOf(InQueue), False); InQueue[start] := True; {Các nhãn T được khởi gán = 0} FillChar(T, SizeOF(T), 0); {Nút cơ sở của outermost blossom chứa i chính là i} for i := 1 to n do b[i] := i; finish := 0; {finish = 0 nghĩa là chưa tìm thấy đường mở} end; procedure Push(v: Integer); {Đẩy một đỉnh đậm v vào hàng đơi} begin Inc(last); Queue[last] := v; InQueue[v] := True; end; function Pop: Integer; {Lấy một đỉnh đậm khỏi hàng đợi, trả về trong kết quả hàm} begin Pop := Queue[first]; Inc(first); end; {Khó nhất của phương pháp Lawler là thủ tục này: Thủ tục xử lý khi gặp cạnh nhạt nối hai đỉnh đậm p, q} procedure BlossomShrink(p, q: Integer); var i, NewBase: Integer; Mark: array[1..max] of Boolean; {Thủ tục tìm nút cơ sở bằng cách truy vết ngược theo đường pha từ p và q} function FindCommonAncestor(p, q: Integer): Integer; var InPath: array[1..max] of Boolean; begin FillChar(InPath, SizeOf(Inpath), False); repeat {Truy vết từ p} p := b[p]; {Nhảy tới nút cơ sở của Blossom chứa p, phép nhảy này để tăng tốc độ truy vết} Inpath[p] := True; {Đánh dấu nút đó} if p = start then Break; {Nếu đã truy về đến nơi xuất phát thì dừng} p := T[match[p]]; {Nếu chưa về đến start thì truy lùi tiếp hai bước, theo cạnh đậm rồi theo cạnh nhạt} until False; repeat {Truy vết từ q, tương tự như đối với p} q := b[q]; if InPath[q] then Break; {Tuy nhiên nếu chạm vào đường pha của p thì dừng ngay} q := T[match[q]]; until False; FindCommonAncestor := q; {Ghi nhận đỉnh cơ sở mới} end; procedure ResetTrace(x: Integer); {Gán lại nhãn vết dọc trên đường pha từ start tới x} var u, v: Integer; begin v := x; while b[v] <> NewBase do {Truy vết đường pha từ start tới đỉnh đậm x} begin u := match[v]; Mark[b[v]] := True; {Đánh dấu nhãn blossom của các đỉnh trên đường đi} Mark[b[u]] := True; v := T[u]; if b[v] <> NewBase then T[v] := u; {Chỉ đặt lại vết T[v] nếu b[v] không phải nút cơ sở mới} end; end; begin {BlossomShrink} FillChar(Mark, SizeOf(Mark), False); {Tất cả các nhãn b[v] đều chưa bị đánh dấu} NewBase := FindCommonAncestor(p, q); {xác định nút cơ sở} {Gán lại nhãn} ResetTrace(p); ResetTrace(q); if b[p] <> NewBase then T[p] := q; if b[q] <> NewBase then T[q] := p; {Chập blossom ⇔ gán lại các nhãn b[i] nếu blossom b[i] bị đánh dấu} for i := 1 to n do if Mark[b[i]] then b[i] := NewBase; {Xét những đỉnh đậm i chưa được đưa vào Queue nằm trong Blossom mới, đẩy i và Queue để chờ duyệt tiếp tại các bước sau} for i := 1 to n do if not InQueue[i] and (b[i] = NewBase) then Push(i); end; {Thủ tục tìm đường mở} procedure FindAugmentingPath; var u, v: Integer; begin InitBFS; {Khởi tạo} repeat {BFS} u := Pop; {Xét những đỉnh v chưa duyệt, kề với u, không nằm cùng Blossom với u, dĩ nhiên T[v] = 0 thì (u, v) là cạnh nhạt rồi} for v := 1 to n do if (T[v] = 0) and (a[u, v]) and (b[u] <> b[v]) then begin if match[v] = 0 then {Nếu v chưa ghép thì ghi nhận đỉnh kết thúc đường mở và thoát ngay} begin T[v] := u; finish := v; Exit; end; {Nếu v là đỉnh đậm thì gán lại vết, chập Blossom ...} 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} begin T[v] := u; Push(match[v]); end; end; until first > last; end; procedure Enlarge; {Nới rộng bộ ghép bởi đường mở bắt đầu từ start, kết thúc ở finish} var v, next: Integer; begin repeat v := T[finish]; next := match[v]; match[v] := finish; match[finish] := v; finish := next; until finish = 0; end; procedure Solve; {Thuật toán Edmonds} var u: Integer; begin for u := 1 to n do if match[u] = 0 then begin start := u; {Với mỗi đỉnh chưa ghép start} FindAugmentingPath; {Tìm đường mở bắt đầu từ start} if finish <> 0 then Enlarge; {Nếu thấy thì nới rộng bộ ghép theo đường mở này} end; end; procedure Result; {In bộ ghép tìm được} var u, count: Integer; f: Text; begin Assign(f, OutputFile); Rewrite(f); count := 0; for u := 1 to n do if match[u] > u then {Vừa tránh sự trùng lặp (u, v) và (v, u), vừa loại những đỉnh không ghép được (match=0)} begin Inc(count); WriteLn(f, count, ') ', u, ' ', match[u]); end; Close(f); end; begin Enter; Init; Solve; Result; end.
13.5. Độ phức tạp tính toán
Thủ tục BlossomShrink có độ phức tạp O(n). Thủ tục FindAugmentingPath cần không quá n lần gọi thủ tục BlossomShrink, cộng thêm chi phí của thuật toán tìm kiếm theo chiều rộng, có độ phức tạp O(n2). Phương pháp Lawler cần không quá n lần gọi thủ tục FindAugmentingPath nên có độ phức tạp tính toán là O(n3).
Cho đến nay, phương pháp tốt nhất để giải bài toán tìm bộ ghép tổng quát trên đồ thị được biết đến là của Micali và Varizani (1980), nó có độ phức tạp tính toán là O . B ( n.m) ạn có thể tham khảo trong các tài liệu khác.