Lý thuyết đồ thị - Bài 09: Một số tính chất của đồ thị hai phần

1/37
5.3. MỘT SỐ TÍNH CHẤT CỦA
ĐỒ THỊ HAI PHẦN
Giả sử G = (V1, V2, F) là đồ thị hai phần n đỉnh.
Ký hiệu: k là số phần tử của tập đỉnh tựa bé nhất.

Định lý 5.2:
1) Số ổn định trong của đồ thị hai phần G là bằng n-k.
2) Số phần tử của cặp ghép lớn nhất của G là bằng k.

2/37
5.3. MỘT SỐ TÍNH CHẤT CỦA
ĐỒ THỊ HAI PHẦN (tiếp)
Chứng minh định lý
Từ tính chất: C là tập đỉnh tựa  V C là tập ổn định trong, suy ra:
C là tập đỉnh tựa nhỏ nhất  V C là tập ổn định trong lớn nhất.

Số ổn định trong = |V C| = |V| - |C| = n-k.

3/37
5.3. MỘT SỐ TÍNH CHẤT CỦA
ĐỒ THỊ HAI PHẦN (tiếp)
Chứng minh định lý:
2) Giả sử W là cặp ghép lớn nhất và C là tập tựa nhỏ nhất.
Lập ánh xạ t : W  C như sau:
e  W, t(e) là một đỉnh của e thuộc C.
t(e) tồn tại vì C là tập đỉnh tựa.
Nếu cả hai đỉnh của e đều thuộc C , ta lấy một
trong hai đỉnh đó.



4/37
5.3. MỘT SỐ TÍNH CHẤT CỦA
ĐỒ THỊ HAI PHẦN (tiếp)
Chứng minh định lý:
Nếu u, v  W và u  v thì t(u)  t(v) vì hai cạnh u và v không có đỉnh chung.
Vậy: | W |  | C | = k.

Chứng minh điều ngược lại: k  | W |.



5/37
5.3. MỘT SỐ TÍNH CHẤT CỦA
ĐỒ THỊ HAI PHẦN (tiếp)
Chứng minh định lý:
Ký hiệu: B là tập các đỉnh của W trong V1.
Lập ánh xạ h : B  V2 như sau:
 a  B ,  b  V2 : (a, b)  W ta đặt h(a) = b.
- h(B) chính là tập các đỉnh của W trong V2.
- Nếu a, c  B và a  c thì h(a)  h(c) vì các cạnh trong W chứa a và c không kề nhau.
6/37
5.3. MỘT SỐ TÍNH CHẤT CỦA
ĐỒ THỊ HAI PHẦN (tiếp)
Chứng minh định lý:
Một đường đi trong đồ thị G được gọi là đường đan
nếu nó có dạng < w1 u1 w2 u2 ... wq uq > ,
với w1, w2, ... , wq  W ; u1, u2, ... , uq  W.
Ký hiệu: B1 = { a  B  đường đan đi từ a đến
một đỉnh nào đó nằm ngoài B }.
Đặt B2 = B B1 và C = B2  h(B1).
Ta chứng minh rằng, C là tập đỉnh tựa của đồ thị G.
7/37
5.3. MỘT SỐ TÍNH CHẤT CỦA
ĐỒ THỊ HAI PHẦN (tiếp)
Chứng minh định lý:
Phản chứng: Giả sử rằng tập C không phải tập đỉnh
tựa của đồ thị hai phần G.
Khi đó, có cạnh (a, b) không tựa vào tập C:
a  B2 và b  h(B1).
Vì W là cặp ghép lớn nhất, nên (a, b) phải kề với
cạnh nào đó trong W: a  B hoặc b  h(B).
8/37
5.3. MỘT SỐ TÍNH CHẤT CỦA
ĐỒ THỊ HAI PHẦN (tiếp)
Chứng minh định lý:
Trường hợp: a  B. Suy ra: a  B1.
Tồn tại đường đan (X) = < w1 u1 w2 u2 ... wq uq > dẫn
đỉnh a tới một đỉnh d nào đó nằm ngoài tập B.
- Nếu b  h(B) thì (a, b)  W.
Ta loại w1 , w2 , ... , wq ra khỏi W rồi thay các cạnh
(a, b) , u1 , u2 , ... , uq vào W.
Khi đó, W vẫn là một cặp ghép và số cạnh tăng
thêm 1, trái với giả thiết W là cặp ghép lớn nhất.
9/37
5.3. MỘT SỐ TÍNH CHẤT CỦA
ĐỒ THỊ HAI PHẦN (tiếp)
Chứng minh định lý:
- Nếu b  h(B) thì b  h(B2).
Ký hiệu đỉnh d’ = h-1(b)  B2.
Đường đan: < (d’, b) + (b, a) + (X) > dẫn đỉnh d’ trong B2 tới đỉnh d nằm ngoài B.
Vậy thì: d’  B1. Suy ra mâu thuẫn.
10/37
5.3. MỘT SỐ TÍNH CHẤT CỦA
ĐỒ THỊ HAI PHẦN (tiếp)
Chứng minh định lý:
2) Trường hợp a  B:
Suy ra b  h(B2) vì (a, b) không tựa vào tập C.
Ký hiệu: d’ = h-1(b)  B2.
Đường đan < (d’,b) + (b,a) > dẫn đỉnh d’ tới
đỉnh a ở ngoài tập B. Vậy thì d  B1. Mâu thuẫn.
Vậy C là một tập tựa của đồ thị và |C| = |W|.
Vì k là số phần tử của tập đỉnh tựa nhỏ nhất nên
k  |C| = |W|. Định lý được chứng minh. 
11/37
5.3. MỘT SỐ TÍNH CHẤT CỦA
ĐỒ THỊ HAI PHẦN (tiếp)
Ký hiệu d0 = max { |B| - |F(B)|  B  V1 }.
Vì   V1 và || - |F()| = 0 - 0 = 0 nên d0 luôn là một số không âm.

Định lý 5.3: Số phần tử của tập tựa bé nhất của đồ thị hai phần G = (V1, V2, F) là |V1| - d0 .
12/37
5.3. MỘT SỐ TÍNH CHẤT CỦA
ĐỒ THỊ HAI PHẦN (tiếp)
Chứng minh định lý:
Giả sử C là một tập tựa bất kỳ.
Tách C = C1  C2 , trong đó C1  V1 và C2  V2.
Ký hiệu: C1’ = V1 C1.
Khi đó, F(C1’)  C2 , vì nếu ngược lại thì:
a  C1’ mà đỉnh kề của nó y  C
cạnh (a, y) sẽ không tựa vào tập C  mâu thuẫn.
13/37
5.3. MỘT SỐ TÍNH CHẤT CỦA
ĐỒ THỊ HAI PHẦN (tiếp)
Chứng minh định lý:
C1  F(C1’) là một tập tựa và C1  F(C1’)  C.
Do đó, với mỗi tập tựa có thể thay bằng một tập tựa
dạng C1  F(C1’) với số phần tử không lớn hơn.
Vậy, số phần tử của tập tựa bé nhất là:
min { | C1  F(C1’) |  C1  V1 }
= min { | C1 | + | F(C1’) |  C1  V1}
= | V1| - max { | C1’| - | F(C1’) |  C1’  V1}
= | V1 | - d0. 
14/37
SỐ HỤT CỦA ĐỒ THỊ HAI PHẦN
Từ Định lý 5.3, ta gọi d0 là số hụt của đồ thị.

Hệ quả 5.4:
a) Số ổn định trong của đồ thị hai phần G là
| V2| + d0
b) Số phần tử của cặp ghép lớn nhất của G là
| V1| - d0.
15/37
BÀI TOÁN PHÂN CÔNG NHIỆM VỤ (tiếp)
Giả thiết:
- Mỗi nhân viên đảm nhận được k nhiệm vụ
- Mỗi nhiệm vụ có đúng k nhân viên có thể đảm nhận.
Kết luận: Luôn có thể phân công công việc thích hợp.
16/37
BÀI TOÁN PHÂN CÔNG NHIỆM VỤ (tiếp)
Ký hiệu: V1 - tập nhân viên, |V1| = n
V2 - tập nhiệm vụ, |V2| = m.
Xây dựng độ thị hai phần G = (V1,V2, F) :
xi  F(yj)  xi đảm nhận được nhiệm vụ yj.
Từ giả thiết, mỗi đỉnh kề với k cạnh, do đó số cạnh kề
với F(B)  số cạnh kề với B.
- Số cạnh kề với B là k.| B |
- Số cạnh kề với F(B) là k.| F(B) |.
17/37
BÀI TOÁN PHÂN CÔNG NHIỆM VỤ (tiếp)
Số cạnh kề với F(B)  số cạnh kề với B nên
|B|  |F(B)| , suy ra d0 = 0.
Theo Hệ quả 5.4, lực lượng của cặp ghép lớn nhất là
|V1| - d0 = |V1| . Do đó, có thể phân công n nhân viên
đảm nhân n nhiệm vụ.

Thay đổi vai trò giữa V1 và V2 , suy ra lực lượng của
cặp ghép lớn nhất bằng |V2|, nên |V1| = |V2|.
Bài toán luôn giải được. 
18/37
5.4. ĐỒ THỊ RIÊNG HAI PHẦN
Từ một đồ thị đã cho có trích được một đồ thị riêng hai
phần hay không ?

Định lý 5.5:
Đồ thị vô hướng G = (V, E) với:
- |V| = 2n ,
- bậc của mỗi đỉnh không nhỏ hơn n ;
luôn có đồ thị riêng hai phần G” = (V1, V2, E”) trong đó: | V1 | = |V2 | = | E”| = n và
E’’ là cặp ghép lớn nhất của G.
19/37
5.4. ĐỒ THỊ RIÊNG HAI PHẦN (tiếp)
Chứng minh định lý:
Xây dựng đồ thị riêng hai phần G” = (V1, V2, E”):
Lấy dần vào E’’ các cạnh của G: các đỉnh trên các
cạnh này khác nhau đôi một cho đến khi bất kỳ cạnh
nào còn lại cũng kề với một cạnh trong E”.
Giả sử | E” | = k.
1) Nếu k = n, định lý được chứng minh.
20/37
5.4. ĐỒ THỊ RIÊNG HAI PHẦN (tiếp)
Chứng minh định lý:
2) Nếu k < n thì |V |  2k +2.
Giả sử E” = {(a1, a2), (a3, a4), ..., (a2k-1, a2k)}.
Khi đó có ít nhất hai đỉnh a2k+1, a2k+2 không nằm trên cạnh nào thuộc E”.

Theo cách chọn tập E’’ thì a2k+1, a2k+2 chỉ kề với các đỉnh trên E” và kề với ít nhất n đỉnh trong E”.
21/37
5.4. ĐỒ THỊ RIÊNG HAI PHẦN (tiếp)
Trong E” đánh dấu các đỉnh kề với a2k+1 và a2k+2: ít
nhất có một đỉnh ai được đánh dấu 2 lần.
Giả sử aj là đỉnh kề với ai trong E”, loại (ai, aj) ra
khỏi E” , thêm vào (ai, a2k+1) và (aj, a 2k+2).
Số cạnh trong E” tăng thêm 1.
Tiếp tục như vậy, sau một số bước, | E”| = n, và ta xây
dựng được đồ thị riêng hai phần G”. 
22/37
VÍ DỤ 5.7
Đồ thị và đồ thị riêng hai phần: