›
›

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

Download
Bài toán ghép cặp  
Graph Matching  
Graph Matching  
1
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.  
Graph Matching  
2
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).  
Graph Matching  
3
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  
Graph Matching  
4
Ví dụ  
12  
x1  
x2  
y1  
y2  
3
4
8
3
x3  
x4  
y3  
y4  
2
4
6
Cặp ghép lớn nhất:  
M = {(x1, y1), (x2, y3), (x3, y2), (x4, y4)}  
Có trọng lượng 29.  
Graph Matching  
5
Bµi to¸n cÆp ghÐp cùc ®¹i  
trªn ®å thÞ hai phÝa  
1
6
7
XÐt ®å thÞ hai phÝa  
G = (X Y, E).  
2
CÆp ghÐp lµ tËp c¹nh mµ  
kh«ng cã hai c¹nh nµo cã  
3
4
5
8
9
chung ®Ønh  
Bµi to¸n: T×m cÆp ghÐp  
kÝch thíc lín nhÊt  
10  
Graph Matching  
6
Qui vÒ Bµi to¸n luång cùc ®¹i  
1
2
6
7
s
3
4
5
8
9
t
10  
Mỗi cạnh được  
thay thế bởi  
cung có kntq 1.  
Mỗi cung (s, i) có kntq 1.  
Mỗi cung (j, t) có kntq 1.  
Graph Matching  
7
Tìm luồng cực đại  
1
2
6
7
s
3
4
5
8
9
t
10  
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.  
Graph Matching  
8
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).  
Graph Matching  
9
Đườ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.  
Graph Matching  
10  
Đị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 nhng vÉn t×m  
®îc ®êng t¨ng cÆp ghÐp  
P x0, y1, x1, y2, ..., xk, y0  
trong ®ã x0 vµ y0 lµ c¸c ®Ønh tù do.  
Gäi EP lµ tËp c¸c c¹nh cña ®å thÞ n»m trªn ®êng ®i P  
EP = { (x0,y1), (y1, x1), ..., (xk, y0) }.  
DÔ thÊy sè lîng c¹nh nh¹t trong EP 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 EP cña nã. X©y dùng cÆp ghÐp M’ theo qui t¾c:  
M’ = (MP) \ (MP).  
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.  
Graph Matching  
11  
Định lý Berge  
§iÒu kiÖn ®ñ. Gi¶ sö cÆp ghÐp M cha lµ cÆp ghÐp cùc ®¹i.  
Gäi M* lµ cÆp ghÐp cùc ®¹i. XÐt ®å thÞ G’ = (V, MM*).  
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ú.  
Graph Matching  
12  
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 x0X, kÕt thóc ë ®Ønh tù do y0 Y. T¨ng cÆp  
ghÐp theo qui t¾c  
M:= (MP) \ (MP),  
råi lÆp l¹i bíc lÆp.  
Graph Matching  
13  
Tìm đường tăng  
Tõ ®å thÞ G ta x©y dùng ®å thÞ cã híng GM = (XY, EM) víi  
tËp cung EM ®î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) ME, th× (y,x) EM;  
ii) NÕu (x,y) E \ M, th× (x,y) EM.  
§å thÞ GM 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 x0 X kÕt thóc t¹i mét ®Ønh tù do y0 Y trªn ®å thÞ GM.  
◼ Ngîc l¹i, mét ®êng ®i trªn ®å thÞ GM xuÊt ph¸t tõ mét ®Ønh tù do x0 X  
kÕt thóc t¹i mét ®Ønh tù do y0 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Þ GM b¾t ®Çu tõ c¸c ®Ønh tù do thuéc tËp X.  
Graph Matching  
14  
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(n3), trong ®ã n = max (|X|, |Y|).  
Graph Matching  
15  
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,  
Vo,  
(* Ghi nhận đường đi *)  
(* Vo[x]- đỉnh được ghép với xX *)  
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 *)  
Graph Matching  
16  
Tìm đường tăng  
Procedure Tim(x:Byte);  
Procedure Tim_Duong_Tang;  
begin  
var y: Byte;  
begin  
Fillchar(Truoc,Sizeof(Truoc),0);  
y0:=0;  
For x0:=1 to N do  
begin  
If Vo[x0]=0 then Tim(x0);  
If y0<>0 then exit;  
end;  
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;  
Stop:=true;  
end;  
end;  
end;  
end;  
Graph Matching  
17  
Thủ tục MaxMatching  
Procedure Tang;  
var temp: Byte;  
begin  
Procedure MaxMatching;  
begin  
Stop:=false;  
Inc(Cnt);  
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;  
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;  
end;  
Graph Matching  
18  
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  
wij - 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.  
Graph Matching  
19  
Qui về bài toán cặp ghép lớn nhất  
X©y dùng ®å thÞ hai phÝa ®Çy ®ñ G = (XY, E)  
◼ X={x1, x2,..., xn} t¬ng øng víi c¸c thî,  
◼ Y = {y1, y2,..., yn }- t¬ng øng víi c¸c c«ng viÖc.  
Mçi c¹nh (xi, yj) ®îc g¸n cho träng sè w(xi, yj) = wij.  
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.  
Graph Matching  
20  
Tải về để xem bản đầy đủ
ppt 43 trang Thùy Anh 23140 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pptbai_giang_toan_roi_rac_phan_2_ly_thuyet_do_thi_bai_toan_ghep.ppt