›
›

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 26/04/2022 7220
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