- Trang Chủ
- Toán học
- 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
Xem mẫu
- 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
nguon tai.lieu . vn
