Bài giảng Toán rời rạc - Phần 2: Lý thuyết đồ thị - Bài toán ghép cặp - Nguyễn Đức Nghĩa

Bài toỏn ghộp cặp 
Graph Matching 
1 
Graph Matching 
Bài toỏn ghộp cặp trờn đồ thị 
Gi ả sử G =( V,E ) là đ ồ thị vô hướng , trong đó mỗi cạnh ( v,w ) đư ợc gán với một số thực c ( v,w ) gọi là trọng số của nó . 
Đ ịnh nghĩa . Cặp ghép M trên đ ồ thị G là tập các cạnh của đ ồ thị trong đ ó không có hai cạnh nào có đ ỉnh chung . 
Số cạnh trong M - kích thước , 
Tổng trọng số của các cạnh trong M - trọng lượng của cặp ghép . 
Cặp ghép với kích thước lớn nhất đư ợc gọi là cặp ghép cực đại. 
Cặp ghép với trọng lượng lớn nhất đư ợc gọi là cặp ghép lớn nhất . 
 Cặp ghép đư ợc gọi là đ ầy đủ ( hoàn hảo ) nếu mỗi đ ỉnh của đ ồ thị là đ ầu mút của ít nhất một cạnh trong cặp ghép . 
2 
Graph Matching 
Hai bài toỏn 
Bài toán cặp ghép cực đại : Tìm cặp ghép với kích thước lớn nhất trong đ ồ thị G. 
Bài toán cặp ghép lớn nhất : Tìm cặp ghép với trọng lượng lớn nhất trong đ ồ thị G. 
Ta hạn chế xét các bài toán đ ặt ra trên đ ồ thị hai phía G = ( X  Y, E ) . 
3 
Graph Matching 
Vớ dụ 
Cặp ghộp cực đại Cặp ghộp khụng là cặp ghộp 
Cặp ghộp Cặp ghộp hoàn hảo 
4 
Graph Matching 
Vớ dụ 
Cặp ghộp lớn nhất : 
 M = {( x 1 , y 1 ), ( x 2 , y 3 ), ( x 3 , y 2 ), ( x 4 , y 4 )} 
Cú trọng lượng 29. 
y 4 
y 3 
y 2 
y 1 
x 4 
x 3 
x 2 
x 1 
12 
3 
4 
8 
3 
2 
4 
6 
5 
Graph Matching 
Bài toán cặp ghép cực đại  trên đ ồ thị hai phía 
Xét đ ồ thị hai phía  G = ( X  Y, E ) . 
Cặp ghép là tập cạnh mà không có hai cạnh nào có chung đ ỉnh 
Bài toán : Tìm cặp ghép kích thước lớn nhất 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
6 
Graph Matching 
Qui về Bài toán luồng cực đại 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
s 
t 
Mỗi cung (s, i) cú kntq 1. 
Mỗi cung (j, t) cú kntq 1. 
Mỗi cạnh được thay thế bởi cung cú kntq 1. 
7 
Graph Matching 
Tỡm luồng cực đại 
Luồng cực đại từ s->t cú giỏ trị 4. 
Cặp ghộp cực đại cú kớch thước 4. 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
s 
t 
8 
Graph Matching 
Bài toán cặp ghép cực đại  trên đ ồ thị hai phía 
Gi ả sử M là một cặp ghép trên G . 
Nếu cạnh e = ( x, y ) M , ta nói e là cạnh của cặp ghép (hay cạnh đ ậm ) và các đ ỉnh x, y là các đ ỉnh đ ậm (hay không tự do). 
Nếu cạnh e = ( x, y ) M , th ì ta nói e là cạnh nhạt còn các đ ỉnh x, y là các đ ỉnh nhạt (hay tự do). 
9 
Graph Matching 
Đường tăng cặp ghộp 
Một đư ờng đi trên đ ồ thị G mà trong đ ó hai cạnh liên tiếp là không cùng đ ậm hay nhạt sẽ đư ợc gọi là đư ờng đi luân phiên đậm/nhạt ( hay gọi ngắn gọn là đư ờng đi luân phiên ) . 
Đư ờng đi luân phiên bắt đ ầu từ một đ ỉnh tự do thuộc tập X và kết thúc ở một đ ỉnh tự do thuộc tập Y đư ợc gọi là đư ờng tăng cặp ghép . 
10 
Graph Matching 
Định lý Berge 
Đ ịnh lý 1 (Berge C). Cặp ghép M là cực đại khi và chỉ khi không tìm đư ợc đư ờng tăng cặp ghép . 
CM : 
Đ iều kiện cần . Bằng phản chứng . Gi ả sử M là cặp ghép cực đại nhưng vẫn tìm đư ợc đư ờng tăng cặp ghép 
	P  x 0 , y 1 , x 1 , y 2 , ..., x k , y 0 
 trong đ ó x 0 và y 0 là các đ ỉnh tự do. 
 Gọi E P là tập các cạnh của đ ồ thị nằm trên đư ờng đi P 
	 E P = { ( x 0 ,y 1 ) , ( y 1 , x 1 ) , ..., ( x k , y 0 ) } . 
 Dễ thấy số lượng cạnh nhạt trong E P là bằng số lượng cạnh đ ậm của nó cộng với 1 . Để đơn giản trong phần dưới đây ta đ ồng nhất ký hiệu đư ờng đi P với tập cạnh E P của nó . Xây dựng cặp ghép M’ theo qui tắc: 
	M’ = ( M  P ) \ ( M  P ) . 
	Dễ thấy M’ cũng là cặp ghép và rõ ràng | M’ | = | M | + 1 . Mâu thuẫn thu đư ợc đã chứng minh đ iều kiện cần . 
11 
Graph Matching 
Định lý Berge 
Đ iều kiện đủ. Gi ả sử cặp ghép M chưa là cặp ghép cực đại. Gọi M * là cặp ghép cực đại. Xét đ ồ thị G ’ = ( V , M  M *). Rõ ràng hai cạnh liên tiếp trong mỗi đư ờng đi cũng nh ư mỗi chu trình trong G’ không thể thuộc cùng một cặp ghép M hoặc M *. Vì vậy , mỗi đư ờng đi cũng nh ư mỗi chu trình trong G ’ đ ều là đư ờng luân phiên M / M *. Do | M *| > | M |, nên rõ ràng là luôn tìm đư ợc ít nhất một đư ờng đi luân phiên M / M * mà trong đ ó số lượng cạnh thuộc M * là lớn hơn số lượng cạnh thuộc M. Đư ờng đi đ ó chính là đư ờng tăng cặp ghép trên đ ồ thị G . 
Đ ịnh lý đư ợc chứng minh . 
Chú ý: Trong chứng minh đ ịnh lý ta không sử dụng tính hai phía của G . Do đ ó , Đ ịnh lý 1 là đ úng với đ ồ thị vô hướng bất kỳ . 
12 
Graph Matching 
Thuật toán tìm cặp ghép cực đại 
Đ ầu vào : Đ ồ thị vô hướng G = ( V, E ). 
Bước khởi tạo. Xây dựng cặp ghép M trong đ ồ thị G ( có thể bắt đ ầu từ M =  ). 
Bước lặp . 
Kiểm tra tiêu chuẩn tối ưu: Nếu đ ồ thị G không chứa đư ờng tăng cặp ghép th ì M là cặp ghép cực đại, thuật toán kết thúc . 
Ngược lại, gọi P là một đư ờng tăng cặp ghép xuất phát từ đ ỉnh tự do x 0 X , kết thúc ở đ ỉnh tự do y 0 Y . Tăng cặp ghép theo qui tắc 
 M := ( M  P ) \ ( M  P ), 
 rồi lặp lại bước lặp . 
13 
Graph Matching 
Tỡm đường tăng 
Từ đ ồ thị G ta xây dựng đ ồ thị có hướng G M = ( X  Y , E M ) với tập cung E M đư ợc bằng cách đ ịnh hướng lại các cạnh của G theo quy tắc sau : 
	i) Nếu ( x,y ) M  E , th ì ( y,x ) E M ; 
	ii) Nếu ( x,y ) E \ M , th ì ( x,y ) E M . 
 Đ ồ thị G M sẽ đư ợc gọi là đ ồ thị tăng cặp ghép . 
Dễ thấy : 
Đường tăng cặp ghép tương ứng với một đư ờng đi xuất phát từ một đ ỉnh tự do x 0 X kết thúc tại một đ ỉnh tự do y 0 Y trên đ ồ thị G M . 
Ngược lại, một đư ờng đi trên đ ồ thị G M xuất phát từ một đ ỉnh tự do x 0 X kết thúc tại một đ ỉnh tự do y 0 Y sẽ tương ứng với một đư ờng tăng cặp ghép trên đ ồ thị G. 
Vì vậy , để xét xem đ ồ thị G có chứa đư ờng tăng cặp ghép hay không , có thể thực hiện thuật toán tìm kiếm theo chiều rộng trên đ ồ thị G M bắt đ ầu từ các đ ỉnh tự do thuộc tập X . 
14 
Graph Matching 
Thuật toỏn 
Sử dụng cách tìm đư ờng tăng cặp ghép theo nhận xét vừa nêu , từ sơ đ ồ tổng quát dễ dàng xây dựng thuật toán để giải bài toán tìm cặp ghép cực đại trên đ ồ thị hai phía với thời gian tính O ( n 3 ), trong đ ó n = max (| X |, | Y |). 
15 
Graph Matching 
Cài đặt 
Cấu trỳc dữ liệu 
Var 
 A : Array[1..100,1..100] of Byte; (* Ma trận kề của đồ thi hai phớa G *) 
 Truoc ,	 (* Ghi nhận đường đi *) 
 Vo, (* Vo[x ]- đỉnh được ghộp với x X *) 
 Chong : Array[1..100] of Byte; (* Chong[y]-đỉnh được ghộp với y Y *) 
 N, x0, y0, Cnt : Byte; 
 Stop : Boolean; 
(* Nếu (x, y) M thỡ Vo[x ]=y; Chong[y ]=x. 
 Vo[x ]=0 => x là đỉnh nhạt ; Chong[y ]=0 => y là đỉnh nhạt *) 
16 
Graph Matching 
Tỡm đường tăng 
Procedure Tim(x:Byte ); 
 var y: Byte; 
 begin 
 For y:=1 to N do 
 If ( A[x,y ]=1)and(Truoc[y]=0)and(y0=0) then 
 begin 
 Truoc[y ]:=x; 
 If Chong[y ]0 then Tim(Chong[y ]) 
 else 
 begin 
 y0:=y; 
 Exit; 
 end; 
 end; 
 end; 
Procedure Tim_Duong_Tang ; 
begin 
 Fillchar(Truoc,Sizeof(Truoc),0); 
 y0:=0; 
 For x0:=1 to N do 
 begin 
 If Vo[x0]=0 then Tim(x0); 
 If y00 then exit; 
 end; 
 Stop:=true; 
end; 
17 
Graph Matching 
Thủ tục MaxMatching 
Procedure Tang; 
var temp: Byte; 
begin 
 Inc(Cnt ); 
 While Truoc[y0]x0 do 
 begin 
 Chong[y0]:=Truoc[y0]; 
 Temp:=Vo[Truoc[y0]]; 
 Vo[Truoc[y0]]:=y0; 
 y0:=Temp; 
 end; 
 Chong[y0]:=x0; 
 Vo[x0]:=y0; 
end; 
Procedure MaxMatching ; 
begin 
 Stop:=false; 
 Fillchar(Vo,Sizeof(Vo),0); 
 Fillchar(Chong,Sizeof(Chong),0); 
 Cnt :=0; 
 While not Stop do 
 begin 
 Tim_duong_tang ; 
 If not Stop then Tang; 
 end; 
end; 
18 
Graph Matching 
Bài toán phân công 
 Có n công việc và n thợ . Mỗi thợ đ ều có kh ả năng thực hiện tất cả các công việc . Biết 
	 w ij - hiệu qu ả phân công thợ i làm việc j , 
 ( i, j = 1, 2,..., n ). 
 Cần tìm cách phân công thợ thực hiện các công việc sao cho mỗi thợ chỉ thực hiện một việc và mỗi việc chỉ do một thợ thực hiện , đ ồng thời tổng hiệu qu ả thực hiện các công việc là lớn nhất . 
19 
Graph Matching 
Qui về bài toỏn cặp ghộp lớn nhất 
Xây dựng đ ồ thị hai phía đ ầy đủ G = ( X  Y , E ) 
X ={ x 1 , x 2 ,..., x n } tương ứng với các thợ , 
Y = { y 1 , y 2 ,..., y n }- tương ứng với các công việc . 
Mỗi cạnh ( x i , y j ) đư ợc gán cho trọng số w ( x i , y j ) = w ij . 
Khi đ ó trong ngôn ng ữ đ ồ thị , bài toán phân công có thể phát biểu nh ư sau : Tìm trong đ ồ thị G cặp ghép đ ầy đủ có tổng trọng số là lớn nhất . Cặp ghép nh ư vậy đư ợc gọi là cặp ghép tối ưu. 
20 
Graph Matching 
Cơ sở thuật toán 
 Ta gọi một phép gán nhãn chấp nhận đư ợc cho các đ ỉnh của đ ồ thị G= ( X  Y,E ) là một hàm số f xác đ ịnh trên tập đ ỉnh X  Y: f: X  Y R, tho ả mãn 
	 f ( x ) + f ( y ) w ( x,y ) ,  x X,  y Y. 
 Một phép gán nhãn chấp nhận đư ợc nh ư vậy dễ dàng có thể tìm đư ợc , chẳng hạn phép gán nhãn sau đây là chấp nhận đư ợc 
	 f ( x ) = max { w ( x,y ): y Y },	 x X , 
 	 f ( y ) = 0 , y Y . 
21 
Graph Matching 
Đồ thị cõn bằng 
Gi ả sử có f là một phép gán nhãn chấp nhận đư ợc , ký hiệu 
	 E f = {( x,y ) E : f ( x ) + f ( y ) = w ( x,y )}. 
Ký hiệu G f là đ ồ thị con của G sinh bởi tập đ ỉnh X  Y và tập cạnh E f . Ta sẽ gọi G f là đ ồ thị cân bằng . 
22 
Graph Matching 
Tiờu chuẩn tối ưu 
Đ ịnh lý 2. Gi ả sử f là phép gán nhãn chấp nhận đư ợc . Nếu G f chứa cặp ghép đ ầy đủ M*, th ì M* là cặp ghép tối ưu. 
Chứng minh . 
 Gi ả sử G f chứa cặp ghép đ ầy đủ M *. Khi đ ó từ đ ịnh nghĩa G f suy ra M * cũng là cặp ghép đ ầy đủ của đ ồ thị G . Gọi w ( M *) là trọng lượng của M *: 
 Do mỗi cạnh e M * đ ều là cạnh của G f và mỗi đ ỉnh của G kề với đ úng một cạnh của M *, nên 
 Gi ả sử M là một cặp ghép đ ầy đủ tuỳ ý của G , khi đ ó 
 Suy ra w ( M *) w ( M ). Vậy M * là cặp ghép tối ưu. 
23 
Graph Matching 
Sơ đồ thuật toỏn 
Ta sẽ bắt đ ầu từ một phép gán nhãn chấp nhận đư ợc f . Xây dựng đ ồ thị G f . Bắt đ ầu từ một cặp ghép M nào đ ó trong G f ta xây dựng cặp ghép đ ầy đủ trong G f . Nếu tìm đư ợc cặp ghép đ ầy đủ M *, th ì nó chính là cặp ghép tối ưu. Ngược lại, ta sẽ tìm đư ợc cặp ghép cực đại không đ ầy đủ M '. Từ M ' ta sẽ tìm cách sửa phép gán nhãn thành f ' sao cho M ' vẫn là cặp ghép của G f ' và có thể tiếp tục phát triển M ' trong G f '., v.v ... 
Qu á trình đư ợc tiếp tục cho đ ến khi thu đư ợc cặp ghép đ ầy đủ trong đ ồ thị cân bằng . 
24 
Graph Matching 
Điều chỉnh nhón 
Gi ả sử M là cặp ghép cực đại trong đ ồ thị G f và M chưa là cặp ghép đ ầy đủ của G . Ta cần tìm cách đ iều chỉnh phép gán nhãn f tho ả mãn các yêu cầu đ ặt ra . 
Thực hiện tìm kiếm theo chiều rộng từ các đ ỉnh tự do trong X . Gọi S là các đ ỉnh đư ợc thăm trong X , còn T là các đ ỉnh đư ợc thăm trong Y trong qu á trình thực hiện tìm kiếm . Ký hiệu 
| S | > | T | (do mỗi đ ỉnh trong T đạt đư ợc từ một đ ỉnh nào đ ó trong S ). 
. 
25 
Graph Matching 
Điều chỉnh nhón 
Từ tính chất của thuật toán tìm kiếm theo chiều rộng , rõ ràng , không có cạnh nào từ S đ ến T * . Để sửa chữa nhãn , chúng ta sẽ tiến hành giảm đ ồng loạt các nhãn trong S đi cùng một gi á trị  nào đ ó , và đ ồng thời sẽ tăng đ ồng loạt nhãn của các đ ỉnh trong T lên  . Đ iều đ ó đảm bảo các cạnh từ S sang T ( nghĩa là những cạnh mà một đ ầu mút thuộc S còn một đ ầu mút thuộc T ) không bị loại bỏ khỏi đ ồ thị cân bằng 
Các tập S và T trong thực hiện thuật toán . Chỉ vẽ các cạnh trong G f . 
S * T * 
26 
Graph Matching 
Điều chỉnh nhón 
Khi các nhãn trong S bị giảm , các cạnh trong G từ S sang T * sẽ có kh ả năng gia nhập vào đ ồ thị cân bằng G f . Ta sẽ tăng  đ ến khi có thêm ít nhất một cạnh mới gia nhập đ ồ thị cân bằng . Có hai kh ả năng : 
Nếu cạnh mới gia nhập đ ồ thị cân bằng giúp ta thăm đư ợc một đ ỉnh không tự do y T * th ì từ nó ta sẽ thăm đư ợc một đ ỉnh đư ợc ghép với nó trong cặp ghép x S * , và cả hai đ ỉnh này đư ợc bổ sung vào S và T tương ứng , và nh ư vậy việc tìm kiếm đư ờng tăng sẽ đư ợc tiếp tục mở rộng . 
Nếu cạnh mới gia nhập đ ồ thị cân bằng cho phép thăm đư ợc một đ ỉnh tự do y T * th ì ta tìm đư ợc đư ờng tăng cặp ghép , và kết thúc một pha đ iều chỉnh nhãn . 
27 
Graph Matching 
Điều chỉnh nhón 
 Ta gọi một pha đ iều chỉnh là tất cả các lần sửa nhãn cần thiết để tăng đư ợc kích thước của cặp ghép M . 
Vì sau mỗi pha đ iều chỉnh kích thước của cặp ghép tăng lên 1, nên ta phải thực hiện nhiều nhất n pha đ iều chỉnh . 
Trong mỗi pha đ iều chỉnh , do sau mỗi lần sửa nhãn có ít nhất hai đ ỉnh mới đư ợc bổ sung vào danh sách các đ ỉnh đư ợc thăm , nên ta phải thực hiện việc sửa nhãn không qu á n lần . Mặt khác , trong thời gian O ( n 2 ) ta có thể xác đ ịnh đư ợc cạnh nào từ S sang T * là cạnh gia nhập đ ồ thị cân bằng ( bằng việc duyệt hết các cạnh). Từ đ ó suy ra đá nh gi á thời gian tính của thuật toán là O ( n 4 ). 
28 
Graph Matching 
Thuật toỏn 
Bước 0: Tìm một phép gán nhãn chấp nhận đư ợc f . 
Bước 1: Xây dựng đ ồ thị cân bằng G f . 
Bước 2: Tìm cặp ghép cực đại M trong G f . 
Bước 3: Nếu M là cặp ghép đ ầy đủ th ì nó là cặp ghép lớn nhất cần tìm . Thuật toán kết thúc . 
Bước 4: Gọi S là tập các đ ỉnh tự do trong X . Thực hiện tìm kiếm từ các đ ỉnh trong S . Gọi T là tập các đ ỉnh của Y đư ợc thăm trong qu á trình tìm kiếm . Bổ sung các đ ỉnh trong X đư ợc thăm trong qu á trình tìm kiếm vào S . 
Bước 5: Tiến hành đ iều chỉnh nhãn f ta sẽ bổ sung đư ợc các cạnh vào G f cho đ ến khi tìm đư ợc đư ờng tăng , bổ sung các đ ỉnh mới đư ợc thăm vào S và T tương ứng nh ư đã mô tả ở trên . Tăng cặp ghép M và quay lại bước 3. 
29 
Graph Matching 
Tăng hiệu quả 
Để có đư ợc thuật toán với đá nh gi á thời gian tính tốt hơn , vấn đề đ ặt ra là làm thế nào có thể tính đư ợc gi á trị  tại mỗi lần sửa nhãn của pha đ iều chỉnh một cách nhanh chóng . 
Ta xác đ ịnh độ lệch của các cạnh theo công thức 
 slack ( x , y ) = f ( x ) + f ( y ) – c ( x , y ). 
30 
Graph Matching 
Tăng hiệu quả 
Khi đ ó 
Rõ ràng việc tính trực tiếp  theo công thức đ òi hỏi thời gian O ( n 2 ). Bây giờ , nếu với mỗi đ ỉnh trong T * ta ghi nhận lại cạnh với độ lệch nhỏ nhất 
31 
Graph Matching 
Tăng hiệu quả 
Việc tính gi á trị độ lệch slack ( y j ) đ òi hỏi thời gian O ( n 2 ) ở đ ầu pha đ iều chỉnh . Khi tiến hành pha đ iều chỉnh ta có thể sửa lại tất cả các độ lệch trong thời gian O ( n ) do chúng bị thay đ ổi cùng một gi á trị (do nhãn của các đ ỉnh trong S giảm đ ồng loạt đi cùng một gi á trị  ). Khi một đ ỉnh x đư ợc chuyển từ S * sang S ta cần tính lại các độ lệch của các đ ỉnh trong T * , việc đ ó đ òi hỏi thời gian O ( n ). Tuy nhiên sự kiện một đ ỉnh đư ợc chuyển từ S * sang S chỉ xảy ra nhiều nhất n lần . 
Nh ư vậy , mỗi pha đ iều chỉnh có thể cài đ ặt với thời gian O ( n 2 ). Do có không qu á n pha đ iều chỉnh trong thuật toán , nên cách cài đ ặt này cho ta thuật toán với thời gian tính O ( n 3 ). 
32 
Graph Matching 
Vớ dụ 
Xột bài toỏn với ma trận hiệu quả 
33 
Graph Matching 
Vớ dụ 
Bắt đầu từ phộp gỏn nhón 
Đồ thị cõn bằng G f 
Cặp ghép cực đại tìm đư ợc 
	 M = {( x 1 , y 2 ), ( x 2 , y 1 ), ( x 4 , y 4 ) }. 
Tìm kiếm theo chiều rộng bắt đ ầu từ đ ỉnh tự do x 3 ta có 
	 S = { x 2 , x 3 }, T = { y 1 } 
34 
Graph Matching 
Vớ dụ 
Tính 
  = min { f ( x )+ f ( y )- w ( x,y ): x { x 2 , x 3 }, y { y 2 , y 3 , y 4 } } = 1. 
Tiến hành sửa nhãn , ta đi đ ến phép gán nhãn mới 
35 
Graph Matching 
Vớ dụ 
Theo đư ờng tăng cặp ghép 
 x 3 , y 3 , x 4 , y 4 
 ta tăng cặp ghép M thành cặp ghép đ ầy đủ 
	 M ={( x 1 , y 2 ), ( x 3 , y 1 ), ( x 2 , y 3 ), ( x 4 , y 4 )}, 
 đ ồng thời là cặp ghép tối ưu với trọng lượng 
	 	 w ( M ) = 4 + 2 + 5 + 2 = 13. 
36 
Graph Matching 
Cài đặt trờn Pascal 
const maxn = 170; 
type data1=array [1..maxn,1..maxn] of integer; 
 data2=array [1..2* maxn ] of integer; 
 data3=array [1..2* maxn ] of longint ; 
var c: data1; 
 px , py , q, queue: data2; 
 a, b, f: data3; 
 n, n2, k, u, z: integer; 
37 
Graph Matching 
Khởi tạo 
procedure init; 
var i, j: integer; 
begin 
 n2:= n+n ; fillchar(f,sizeof(f),0); 
 for i:=1 to n do 
 for j:=1 to n do 
 if f[i ]< c(i,j ) then f[i ]:= c(i,j ); 
 k:=0; 
 fillchar(px,sizeof(px),0); fillchar(py,sizeof(py),0); 
 for i:=1 to n do 
 for j:=1 to n do 
 if ( py[j ]=0) and ( f[i]+f[j+n ]= c(i,j )) then 
 begin 
 px[i ]:=j; py[j ]:=i; inc(k ); 
 break; 
 end; 
end; 
38 
Graph Matching 
function FoundIncPath : boolean ; 
var dq , cq , v, w: integer; 
begin 
 fillchar(q,sizeof(q),0); 
 dq :=1; cq :=1; queue[dq ]:=u; q[u ]:=u; 
 while dq <= cq do 
 begin 
 v:= queue[dq ]; inc(dq ); 
 if v<=n then 
 begin 
 for w:=n+1 to n2 do 
 if ( f[v]+f[w ]= c(v,w-n )) and ( q[w ]=0) then 
 begin inc(cq ); queue[cq ]:=w; q[w ]:=v; end; 
 end else 
 if ( py[v-n ]=0) then begin FoundIncPath := true;z := v;exit ; end 
 else begin w:= py[v-n ]; inc(cq ); queue[cq ]:=w; q[w ]:=v; end; 
 end; 
 FoundIncPath :=false; 
end; 
Tỡm đường tăng 
39 
Graph Matching 
Tỡm đỉnh tự do 
function FreeNodeFound : boolean ; 
var i:integer ; 
begin 
 for i:=1 to n do 
 if px[i ]=0 then 
 begin 
 u:=i; 
 FreeNodeFound :=true; 
 exit; 
 end; 
 FreeNodeFound :=false; 
end; 
40 
Graph Matching 
Tăng cặp ghộp và Sửa nhón 
procedure Tangcapghep ; 
var i, j: integer; 
 ok: boolean ; 
begin 
 j:=z; ok:=true; 
 while ju do 
 begin 
 i:= q[j ]; 
 if ok then 
 begin 
 px[i ]:= j-n ; 
 py[j-n ]:=i; 
 end; 
 j:=i; 
 ok:= not ok; 
 end; 
 inc(k ); 
end; 
procedure Suanhan ; 
var i, j: integer; 
 d: longint ; 
begin 
 d:= maxlongint ; 
 for i:=1 to n do 
 if q[i ]>0 then 
 for j:=n+1 to n2 do 
 if q[j ]=0 then 
 if d> longint(f[i]+f[j]-c(i,j-n )) then 
 d:= longint(f[i]+f[j]-c(i,j-n )); 
 for i:=1 to n do 
 if q[i ]>0 then dec(f[i],d ); 
 for j:=n+1 to n2 do 
 if q[j ]>0 then inc(f[j],d ); 
end; 
41 
Graph Matching 
Main Procedure 
procedure Solve; 
begin 
 init; 
 while FreeNodeFound do 
 begin 
 while not FoundIncPath do suanhan ; 
 Tangcapghep ; 
 end; 
end; 
42 
Graph Matching 
43 
Graph Matching