Bài giảng Bài toán liệt kê

á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:
1 2
u=3 v=4
x
T:1
S:2
1 2
u=3 v=4
x
T:1
S:2 T:3
Tìm thấy đường mở
Trường hợp 2: v chưa thăm và đã ghép
1 2
u=3 v=4
x
T:1
S:2
5
1 2
u=3 v=4
x
T:1
S:2 T:3
5
S:4
Thăm cả v lẫn match[v], gán nhãn T[v] và S[match[v]]
Lý thuyết đồ thị
Lê Minh Hoàng
\ 115 [
Trường hợp 3: v đã thăm, là đỉnh đậm thuộc cùng blossom với u
1 2x
T:1
3
S:2
u=4
6
5
v=7
T:3
S:7
T:5
S:6
T:7
S:4
T:3
S:5
b=3
Không xét, bỏ qua
Trường hợp 4: v đã thăm, là đỉnh đậm và b[u] ≠ b[v]
1 2x
T:1
3
S:2
4
6
u=5
v=7
T:3 S:6
S:4T:3
1 2x
T:1
3
S:2
4
6
u=5
v=7
T:3
S:7
T:5
S:6
T:7
S:4
T:3
S:5
a
8 8
b=3
Tìm đỉnh cơ sở a = 3, gán lại nhãn S và T dọc chu trình pha, chập Blossom.
Đẩ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.
IV. 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 chứa bộ ghép cực đại tìm được
Lý thuyết đồ thị
Lê Minh Hoàng
\ 116 [
GMATCH.INP GMATCH.OUT
9 5 6
1
3 4
2
10
87 10 11
1 2
1 6
2 4
2 8
3 4
3 6
5 6
5 9
5 10
7 8
7 9
1 6
2 8
3 4
5 10
7 9
Number of matched edges: 5
Trong chương trình này, ta sẽ 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ở.
PROG13_1.PAS * Phương pháp Lawler áp dụng cho thuật toán Edmonds
program MatchingInGeneralGraph;
const
 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; {Nhập dữ liệu, từ thiết bị nhập chuẩn (Input)}
var
 i, m, u, v: Integer;
begin
 FillChar(a, SizeOf(a), 0);
 ReadLn(n, m);
 for i := 1 to m do
 begin
 ReadLn(u, v);
 a[u, v] := True;
 a[v, u] := True;
 end;
end;
procedure Init; {Khởi tạo bộ ghép rỗng}
Lý thuyết đồ thị
Lê Minh Hoàng
\ 117 [
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ốt 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;
Lý thuyết đồ thị
Lê Minh Hoàng
\ 118 [
 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;
Lý thuyết đồ thị
Lê Minh Hoàng
\ 119 [
 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;
begin
 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(u, ' ', match[u]);
 end;
 WriteLn('Number of matched edges: ', count);
end;
begin
 Assign(Input, 'GMATCH.INP'); Reset(Input);
 Assign(Output, 'GMATCH.OUT'); Rewrite(Output);
 Enter;
 Init;
 Solve;
 Result;
 Close(Input);
 Close(Output);
end.