Giải thuật và lập trình

PHN 1999-2004 
u
1 2x
T:1
S:2
v u
1 2
3 4
x
T:1
v
S:2 T:3
3 4 5 5
S:4
⇒ 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 
u
1 2x
T:1
v
3
5
6
S:2
T:3
S:5
T:7
S:4
T:5
S:6
T:3
S:7
b[.] = 3
7
4
⇒ 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
8
T:3 S:4
S:6T:3
5
7
1 2x
T:1
3
S:2
4
6
8
T:3
S:5
T:7
S:4
T:5
S:6
T:3
S:7
5
7
a
⇒ 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 
Lý thuyết đồ thị ] 313 ^ 
Lê Minh Hoàng 
™ 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 ≤ 1000) 
™ 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 
9 5 6
1 2
43
10
7 8
GMATCH.INP 
10 11 
1 2 
1 6 
2 4 
2 8 
3 4 
3 6 
5 6 
5 9 
5 10 
7 8 
7 9 
GMATCH.OUT 
1) 1 6 
2) 2 8 
3) 3 4 
4) 5 10 
5) 7 9 
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 nếu và chỉ nếu v = x hoặc match[v] là một đỉnh nhạt, vậy để kiểm tra 
một đỉnh v có phải đỉnh đậm hay không ta có thể kiểm tra bằng biểu thức: 
(v = x) or (match[v] 0) and (T[match[v]] 0) = TRUE 
™ Nếu v là đỉnh đậm thì S[v] = match[v] 
Các biến được sử dụng 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 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 
{$MODE DELPHI} (*This program uses 32-bit Integer [-231..231 - 1]*) 
program MatchingInGeneralGraph; 
const 
 InputFile = 'GMATCH.INP'; 
 OutputFile = 'GMATCH.OUT'; 
 max = 1000; 
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, Front, Rear, start, finish: Integer; 
procedure Enter; 
var 
 i, m, u, v: Integer; 
 f: Text; 
begin 
 Assign(f, InputFile); Reset(f); 
] 314 ^ Chuyên đề 
ĐHSPHN 1999-2004 
 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} 
 Front := 1; Rear := 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 được khởi tạo 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(Rear); 
 Queue[Rear] := 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[Front]; 
 Inc(Front); 
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; 
Lý thuyết đồ thị ] 315 ^ 
Lê Minh Hoàng 
 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] được khởi tạo là chưa bị đánh dấu} 
 NewBase := FindCommonAncestor(p, q); {xác định nút cơ sở} 
 ResetTrace(p); ResetTrace(q); {Gán lại nhãn} 
 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] cho đỉnh 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 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; {Rút một đỉnh đậm u ra khỏi hàng đợi} 
 {Xét những đỉnh v kề u qua một cạnh nhạt mà v không nằm cùng blossom với u} 
 for v := 1 to n do 
 if (a[u, v]) and (match[u] v) and (b[u] b[v]) then 
 if (v = start) or (match[v] 0) and (T[match[v]] 0) then {Nếu v là đỉnh đậm} 
 BlossomShrink(u, v) {thì gán lại vết, chập blossom...} 
 else 
 if T[v] = 0 then {Nếu v là đỉnh nhạt chưa thăm tới} 
 if match[v] = 0 then {Nếu v chưa ghép nghĩa tìm được đường mở kết thúc ở v, thoát} 
 begin 
 T[v] := u; 
 finish := v; 
 Exit; 
 end 
 else {Nếu v đã ghép thì ghi vết đường đi, thăm v, thăm luôn cả match[v] và đẩy match[v] vào Queue} 
 begin 
 T[v] := u; 
 Push(match[v]); 
] 316 ^ Chuyên đề 
ĐHSPHN 1999-2004 
 end; 
 until Front > Rear; 
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 in lặp cạnh (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). 
Lý thuyết đồ thị ] 317 ^ 
Lê Minh Hoàng 
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à Vazizani (1980), nó có độ phức tạp tính toán là ( )O n.m . Bạn có 
thể tham khảo trong các tài liệu khác. 
TÀI LIỆU ĐỌC THÊM 
Dưới đây là hai cuốn sách có thể nói là kinh điển mà hầu hết các tài liệu về thuật toán đều 
trích dẫn ít nhiều từ hai cuốn sách này. Các bạn nên tìm mọi cách để đọc. 
Title: The Art of Computer Programming, 3rd edition 
Author: Donald E. Knuth 
Volume 1: Fundamental Algorithms, ISBN: 0-201-89683-4 
Volume 2: Seminumerical Algorithms, ISBN: 0-201-89684-2 
Volume 3: Sorting and Searching, ISBN: 0-201-89685-0 
Volume 4: Combinatorial Algorithms (in preparation) 
Volume 5: Syntactic Algorithms (in preparation) 
Publisher: Addison-Wesley, 1998 
Title: Introduction to Algorithms, 2nd edition, ISBN: 0262032937 
Authors: Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest 
Publisher: The MIT Press, 2001 
Ngoài ra bạn có thể tham khảo thêm những cuốn sách sau đây: 
™ Alfred V. Aho, Jeffrey D. Ullman, John E. Hopcroft. Data Structures and Algorithms, 
ISBN: 0201000237, Addison Wesley, 1983. 
™ Robert Sedgewick. Algorithms 2nd edition, ISBN: 0201066734, Addison Wesley, 1988. 
™ Mikhail J. Atallah Ed. Algorithms and Theory of Computation Handbook, ISBN: 
0849326494, CRC Press, 1998.