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

Chương này trình bày về Bài toán ghép cặp (Graph Matching) với những nội dung chính sau: Bài toán ghép cặp trên đồ thị, bài toán cặp ghép cực đại trên đồ thị hai phía, qui về bài toán luồng cực đại, đường tăng cặp ghép, thuật toán tìm cặp ghép cực đại,. . | Bài toán ghép cặp Graph Matching 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. 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). 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 Graph Matching Ví dụ Cặp ghép lớn nhất: M = {(x1, y1), (x2, y3), (x3, y2), (x4, y4)} Có trọng lượng 29. y4 y3 y2 y1 x4 x3 x2 x1 12 3 4 8 3 2 4 6 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 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. 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 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ù . | Bài toán ghép cặp Graph Matching 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. 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). 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 .