Giáo trình 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,
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ữ
B
G
Hợp nhau
6 / 39
Đồ thị Nam & Nữ
B
G
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ữ
B
G
Hình: Một ghép cặp
8 / 39
Đồ thị Nam & Nữ
B
G
Giả sử không có cạnh này.
9 / 39
Đồ thị Nam & Nữ
B
G
Giả sử không có cạnh này.
10 / 39
Đồ thị Nam & Nữ
B
G
3
11 / 39
Không đủ số Nam
B
G
2
3
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ữ
B
G
E(S)
S
|S| = 3 > 2 = |E(S)|
13 / 39
Tắc nghẽn
B
G
E(S)
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?
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
B
G
E(H)
R(H)
L(H)
20 / 39
Tải về để xem bản đầy đủ
39 trang
20960
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc - Bài 7: Ghép cặp trên đồ thị hai phần - Trần Vĩnh Đức", để 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:
- giao_trinh_toan_roi_rac_bai_7_ghep_cap_tren_do_thi_hai_phan.pdf
