Bài giảng Toán rời rạc - Bài 7: Ghép cặp trên đồ thị hai phần - Trần Vĩnh Đức

Ghép cặp trên đồ thị hai phần Trần Vĩnh Đức HUST Ngày 24 tháng 7 năm 2018 1 / 39 Ghép cặp trên đồ thị hai phần ▶ Eric Lehman, F Thomson Leighton & Albert R Meyer, Mathematics for Computer Science, 2013 (Miễn phí) ▶ Albert R Meyer’s slides 2 / 39 Tìm bạn nhảy ▶ Tối thứ bảy, hội sinh viên tổ chức tiệc. ▶ Có 300 sinh viên tham gia. ▶ Họ không quen hết nhau! ▶ Trong 6 người luôn có ba người đôi một quen nhau hoặc ba người đôi một lạ nhau! 3 / 39 Tìm bạn nhảy ▶ Tối thứ bảy, hội sinh viên tổ chức tiệc. ▶ Có 300 sinh viên tham gia. ▶ Họ không quen hết nhau! ▶ Nhưng mỗi cô gái quen đúng 50 chàng trai, và mỗi chàng trai quen đúng 50 cô gái! ▶ Liệu mọi sinh viên có thể nhảy đồng thời sao cho hai người nhảy cùng nhau phải biết nhau? 4 / 39 Nội dung Ghép cặp Nam & Nữ Định lý Hall Làm thế nào để tìm ghép cặp cực đại? Đồ thị Nam & Nữ Albert R Meyer. April 3, 2013 Nam & Nữ hợp nhau G B Hợp nhau bipartite.2 6 / 39 Đồ thị Nam & Nữ Albert R Meyer. April 3, 2013 G B bipartite.3 Compatible Boys & Girls Hãy tìm cách ghép cặp mỗi cô gái với chỉ một chàng trai phù hợp. 7 / 39 Đồ thị Nam & Nữ Albert R Meyer. April 3, 2013 G B bipartite.4 Compatible Boys & Girls Hình: Một ghép cặp 8 / 39 Đồ thị Nam & Nữ Albert R Meyer. April 3, 2013 G B suppose this edge was missing bipartite.5 Compatible Boys & Girls Giả sử không có cạnh này. 9 / 39 Đồ thị Nam & Nữ Albert R Meyer. April 3, 2013 G B bipartite.6 Compatible Boys & Girls suppose this edge was missing Giả sử không có cạnh này. 10 / 39 Đồ thị Nam & Nữ Albert R Meyer. April 3, 2013 G B bipartite.7 3 Compatible Boys & Girls 11 / 39 Không đủ số Nam Albert R Meyer. April 3, 2013 G B bipartite.8 3 2 like only 2 boys 3 girls Compatible Boys & Girls Not enough b s for these girls! Có 3 cô gái nhưng chỉ có 2 chàng trai phù hợp. 12 / 39 Không tồn tại cặp ghép cho Nữ Albert R Meyer. April 3, 2013 G B bipartite.9 3 2 No match is possible! S E(S) |S| = 3 > 2 = |E(S)| 13 / 39 Tắc nghẽn Albert R Meyer. April 3, 2013 No match is possible! a bottleneck G B bipartite.10 S E(S) |S| > |E(S)| 14 / 39 Tắc nghẽn ▶ Tắc nghẽn là một tập Nữ S không có đủ số Nam phù hợp. E(S) ::= {chàng trai w | w kề với ít nhất một cô cái trong S} ▶ Tập S là tắc nghẽn |S| > |E(S)| 15 / 39 Bổ đề (Tắc nghẽn) Nếu tồn tại tắc nghẽn, vậy không tồn tại cặp ghép. 16 / 39 Định lý (Hall) Ngược lại, nếu không có tắc nghẽn, vậy có tồn tại cặp ghép. 17 / 39 Bài tập Tại sao đồ thị dưới đây không có cặp ghép nào phủ tập V1? 114 Matching, marriage and Menger's theorem COROLLARY 25.2. Let G = G(V], V2) be a bipartite graph, and for each subset A of'V\, let (p(A) be the set of vertices ofVi that are adjacent to at least one vertex of A. Then a complete matching from V\ to V2 exists if and only if jAj S l<p(A)/\ for each subset A ofV\. Proof. The proof of this corollary is a translation into graph terminology of the above proof. // Exercises 25 25.1s Suppose that three boys a, b, c know four girls w, x, y, z as in Fig 25.3: boy a b c girls known by boy w y z x z x y Fig. 25.3 (i) Draw the bipartite graph corresponding to this table of relationships, (ii) Find five different solutions of the corresponding marriage problem, (iii) Check the marriage condition for this problem. 25.2 A building contractor advertises for a bricklayer, a carpenter, a plumber and a tool- maker, and receives five applicants - one for the job of bricklayer, one for carpenter, one for bricklayer and plumber, and two for plumber and toolmaker. (i) Draw the corresponding bipartite graph. (ii) Check whether the marriage condition holds for this problem. Can all of the jobs be filled by qualified people? 25.3s Explain why the graph in Fig. 25.4 has no complete matching from V\ to V2- When does the marriage condition fail? Fig. 25.4 25.4 (The 'harem problem') Let B be a set of boys, and suppose that each boy in B wishes to marry more than one of his girl friends. Find a necessary and sufficient condition for the harem problem to have a solution. (Hint: replace each boy by several identical copies of himself, and then use Hall's theorem.) 18 / 39 Nội dung Ghép cặp Nam & Nữ Định lý Hall Làm thế nào để tìm ghép cặp cực đại? Đồ thị hai phần H Albert R Meyer. April 3, 2013 G B Hall.2 Bipartite graph H L(H) R(H) E(H) 20 / 39 Ghép cặp hai phía Định nghĩa Một cặp ghép là một hàm đơn ánh m : L(H) −→ R(H) thoả mãn: Nếu m(g) = b thì {g, b} là một cạnh của H. 21 / 39 Định lý (Hall) Nếu với mọi tập S ⊆ L(H) ta đều có |S| ≤ |E(S)| vậy có tồn tại một cặp ghép. 22 / 39 Chứng minh định lý Hall Bổ đề Giả sử không có tắc nghẽn. Hơn nữa, nếu S là một tập những cô gái thoả mãn |S| = |E(S)|. Vậy không có tắc nghẽn giữa S và E(S). 23 / 39 Albert R Meyer. April 3, 2013 T s E(S) E(S) S Tắc nghẽn Hall.13 Vậy S ∪ T là một tắc nghẽn. 7 24 / 39 Chứng minh định lý Hall ▶ Chứng minh bằng quy nạp mạnh theo số Nữ. ▶ Nếu chỉ có 1 Nữ. Định lý hiển nhiên đúng. ▶ Với số Nữ nhiều hơn 1. Ta xét hai trường hợp. 25 / 39 Trường hợp 1 ▶ Có một tập con những cô gái S mà |S| = |E(S)|. ▶ Vậy theo bổ đề trước, không có tắc nghẽn trong cả hai đồ thị hai phần (S,E(S)) và (S,E(S)) ▶ Theo quy nạp, ta có thể ghép cặp hai đồ thị này riêng biệt.3. 26 / 39 Trường hợp 2 ▶ Nếu với mọi tập không rỗng những cô gái S ta đều có |S| < |E(S)| ▶ Chọn lấy một cô gái g. Cô ấy phải hợp với một chàng trai b nào đó. Tại sao? ▶ Ghép cặp g với b. ▶ Loại bỏ g và b. ▶ Ta vẫn không có tắc nghẽn đối với các cô gái và chàng trai còn lại. Tại sao? ▶ Theo quy nạp, ta có thể ghép cặp cho những người còn lại. 3 27 / 39 Kiểm tra tắc nghẽn? Mệnh đề Nếu mỗi cô gái đều thích ≥ d chàng trai, và mỗi chàng trai đều thích ≤ d cô gái, vậy không có tắc nghẽn. 28 / 39 Chứng minh. Xét tập các cô gái S và e là số cạnh liên thuộc với S. Ta có e = ∑ g∈S deg(g) ≥ ∑ g∈S d = d · |S| e ≤ ∑ b∈E(S) deg(b) ≤ ∑ b∈E(S) d = d · |E(S)| Vậy ta có d · |S| ≤ e ≤ d · |E(S)|. Vậy |S| ≤ |E(S)|. 29 / 39 Tìm bạn nhảy ▶ Tối thứ bảy, hội sinh viên tổ chức tiệc. ▶ Có 300 sinh viên tham gia. ▶ Họ không quen hết nhau! ▶ Nhưng mỗi cô gái quen đúng 50 chàng trai, và mỗi chàng trai quen đúng 50 cô gái! ▶ Liệu mọi sinh viên có thể nhảy đồng thời sao cho hai người nhảy cùng nhau phải biết nhau? 30 / 39 Nội dung Ghép cặp Nam & Nữ Định lý Hall Làm thế nào để tìm ghép cặp cực đại? Đường mở Định nghĩa Xét đồ thị hai phần G và M là một ghép cặp trong G. Ta nói rằng đường đi P là một đường mở (cho M) nếu: ▶ P bắt đầu và kết thúc ở hai đỉnh u, v nào đó chưa được ghép cặp; và ▶ Các cạnh trong P luân phiên thuộc M và không thuộc M. 32 / 39 Tính chất của đường mở 10.4 How to Find a Perfect Matching 173 10.4.1 Show by an example that it may happen that a bipartite graph G has a perfect matching, but if we are unlucky, the greedy matching M constructed above is not perfect. 10.4.2 Prove that if G has a perfect matching, then every greedy matching matches up at least half of the nodes. So suppose that we have constructed a matching M that is not perfect. We have to try to increase its size by “backtracking,” i.e., by deleting some of its edges and replacing them by more edges. But how do we find the edges we want to replace? The trick is the following. We look for a path P in G of the following type: P starts and ends at nodes u and v that are unmatched by M ; and every second edge of P belongs to M (Figure 10.6). Such a path is called an augmenting path. It is clear that an augmenting path P contains an odd number of edges, and in fact, the number of its edges not inM is one larger than the number of its edges in M . vu M PM not in Edges inEdges in FIGURE 10.6. An augmenting path in a bipartite graph. ▶ đường mở P chứa một số lẻ cạnh. ▶ Số cạnh không thuộc M lớn hơn 1 so với số cạnh trong M. 33 / 39 Tăng kích thước ghép cặp dùng đường mở Hình: Nếu tìm được một đường mở P, ta có thể xóa các cạnh trong M và thay bằng các cạnh P không thuộc M. 34 / 39 Chiến lược tìm ghép cặp cực đại 1. Bắt đầu với một ghép cặp M bất kỳ (có thể chỉ dùng 1 cạnh). 2. Tìm một đường mở cho M. 3. Nếu tìm thấy một đường mở, xây dựng một ghép cặp tốt hơn M′. 4. Nếu không tìm thấy đường mở nào, thì dừng; M là ghép cặp cực đại. 35 / 39 Tại sao chiến lược này đúng? Định lý Nếu ghép cặp M trong đồ thị hai phần G không phải ghép cặp cực đại, thì G chứa một đường mở cho M. 36 / 39 Chứng minh ▶ Xét M∗ là một ghép cặp cực đại; ▶ đặt F là tập mọi cạnh thuộc M hoặc M∗, nhưng không thuộc cả hai. ▶ Tập cạnh F và các đỉnh tạo thành đồ thị với các đỉnh chỉ có bậc 1 hoặc 2. Tại sao? ▶ Vậy mỗi thành phần liên thông của đồ thị chỉ là đường đi hoặc chu trình; ▶ và trong mỗi đường đi hoặc chu trình này, các cạnh thuộc M luân phiên với các cạnh không thuộc M. 37 / 39 Chứng minh (tiếp) ▶ Vậy thì, trong các chu trình, số cạnh thuộc M bằng với số cạnh không thuộc M. ▶ Vì |M∗| > |M|, phải có ít nhất một thành phần liên thông là đường đi, ▶ và đây chính là đường mở. 38 / 39 Bài tập Hãy tìm ghép cặp cực đại cho cho đồ thị hai phần sau và chứng minh nó là ghép cặp cực đại. 10.4HowtoFindaPerfectMatching177 FIGURE10.9.Agraphfortryingoutthealgorithm. 10.4.8Nowsupposethatwehavetheweakerconditionthateverynonempty subsetAonthelefthasatleast|A|−1neighborsontheright.ProvethatG containsamatchingthatmatchesupallbutonenodeoneachside. 10.4.9LetGbeabipartitegraphwithmnodesonbothsides.Provethatif eachnodehasdegreelargerthanm/2,thenithasaperfectmatching. 10.4.10DoesthegraphinFigure10.10haveaperfectmatching? FIGURE10.10.Atruncatedchessboard. 10.4.11Drawagraphwhosenodesarethesubsetsof{a,b,c},andforwhich twonodesareadjacentifandonlyiftheyaresubsetsthatdifferinexactlyone element. (a)Whatisthenumberofedgesandnodesinthisgraph?Canyounamethis graph? (b)Isthisgraphconnected?Doesithaveaperfectmatching?Doesithavea Hamiltoncycle? 39 / 39