Bài giảng Ghép cặp trên đồ thị hai phần - Toán rời rạc thầy Trần Vĩnh Đức | Trường Đại học Bách khoa Hà Nội

Kiểm tra tắc nghẽn? 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. Bài giảngTài liệu được sưu tầm, giúp bạn ôn tập và đạt kết quả cao. Mời bạn đọc đón xem!

7 4 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Toán rời rạc (BKHN)

Trường: Đại học Bách Khoa Hà Nội

Thông tin:

39 trang 2 tháng trước

Tác giả:

Profile Lân Nguyễn
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 boys 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
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 V
1
?
114 Matching, marriage and Menger's theorem
COROLLARY 25.2.
Let G = G(V
]
, V
2
) 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 V
2
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.1
s
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.3
s
Explain why the graph
in
Fig. 25.4 has
no
complete matching from V\
to
V
2
-
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
| 1/39
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

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ữ
Nam & Nữ hợp nhau G B Hợp nhau Albert R Meyer. April 3, 2013 bipartite.2 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. 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 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. 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. 10 / 39 Đồ thị Nam & Nữ
Compatible Boys & Girls G B 3 Albert R Meyer. April 3, 2013 bipartite.7 11 / 39 Không đủ số Nam No Compat t eno i u b gle B h boys & oys Gi fo r r ls these 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. 12 / 39
Không tồn tại cặp ghép cho Nữ No match is possible! G B 3 2 S E(S) Albert R Meyer. April 3, 2013 bipartite.9
|S| = 3 > 2 = |E(S)| 13 / 39 Tắc nghẽn No match is possible! a bottleneck G B S E(S) |S| > |E(S)| Albert R Meyer. April 3, 2013 bipartite.10 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 Bipartite graph H G B E(H) L(H) R(H) Albert R Meyer. April 3, 2013 Hall.2 20 / 39