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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:39

Thêm vào BST

Báo xấu

17
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Toán rời rạc: Ghép cặp trên đồ thị hai phần cung cấp cho người học những nội dung kiến thức như: Ghép cặp Nam & Nữ, định lý Hall, làm thế nào để tìm ghép cặp cực đại? Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc: 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt 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! CuuDuongThanCong.com https://fb.com/tailieudientucntt 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? CuuDuongThanCong.com https://fb.com/tailieudientucntt 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? CuuDuongThanCong.com https://fb.com/tailieudientucntt
Đồ thị Nam & Nữ Nam & Nữ hợp nhau G B Hợp nhau Albert R Meyer. April 3, 2013 bipartite.2 CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 / 39
Đồ thị Nam & Nữ Compatible Boys & Girls G B Albert R Meyer. April 3, 2013 bipartite.3 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. CuuDuongThanCong.com https://fb.com/tailieudientucntt 7 / 39
Đồ thị Nam & Nữ Compatible Boys & Girls G B Albert R Meyer. April 3, 2013 bipartite.4 Hình: Một ghép cặp CuuDuongThanCong.com https://fb.com/tailieudientucntt 8 / 39
Đồ thị Nam & Nữ Compatible Boys & Girls G B suppose this edge was missing Albert R Meyer. April 3, 2013 bipartite.5 Giả sử không có cạnh này. CuuDuongThanCong.com https://fb.com/tailieudientucntt 9 / 39
Đồ thị Nam & Nữ Compatible Boys & Girls G B suppose this edge was missing Albert R Meyer. April 3, 2013 bipartite.6 Giả sử không có cạnh này. CuuDuongThanCong.com https://fb.com/tailieudientucntt 10 / 39
Đồ thị Nam & Nữ Compatible Boys & Girls G B 3 Albert R Meyer. April 3, 2013 bipartite.7 CuuDuongThanCong.com https://fb.com/tailieudientucntt 11 / 39
Không đủ số Nam NotCompatible enough boys Boys &for these girls! Girls G B 3 2 3 girls like only 2 boys Albert R Meyer. April 3, 2013 bipartite.8 Có 3 cô gái nhưng chỉ có 2 chàng trai phù hợp. CuuDuongThanCong.com https://fb.com/tailieudientucntt 12 / 39
Không tồn tại cặp ghép cho Nữ No match is possible! G B 2 E(S) S 3 Albert R Meyer. April 3, 2013 bipartite.9 |S| = 3 > 2 = |E(S)| CuuDuongThanCong.com https://fb.com/tailieudientucntt 13 / 39
Tắc nghẽn a bottleneck No match is possible! G B E(S) S |S| > |E(S)| Albert R Meyer. April 3, 2013 bipartite.10 CuuDuongThanCong.com https://fb.com/tailieudientucntt 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)| CuuDuongThanCong.com https://fb.com/tailieudientucntt 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. CuuDuongThanCong.com https://fb.com/tailieudientucntt 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. CuuDuongThanCong.com https://fb.com/tailieudientucntt 17 / 39
for bricklayer and plumber, and two for plumber and toolmaker. Bài(i)tậpDraw the corresponding bipartite graph. (ii) Check whether the marriage condition holds for this problem. Can all of the jobs be filled by qualified people? Tại sao đồ thị dưới đây không có cặp ghép nào phủ tập V ? s Explain why the graph in Fig. 25.4 has no complete matching from1 V\ to V2- Whe the marriage condition fail? 25.4 (The 'harem problem') Let B be a set of boys, and suppose that each boy in B wish marry more than one of his girl friends. Find a necessary and sufficient condition fo CuuDuongThanCong.com https://fb.com/tailieudientucntt 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? CuuDuongThanCong.com https://fb.com/tailieudientucntt
Đồ thị hai phần H Bipartite graph H G B E(H) L(H) R(H) Albert R Meyer. April 3, 2013 Hall.2 CuuDuongThanCong.com https://fb.com/tailieudientucntt 20 / 39