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.

1/37


5.3. MỘT SỐ TÍNH CHẤT CỦA
ĐỒ THỊ HAI PHẦN (tiếp)
 Chứng minh định lý
1) 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.

2/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.

ĐỒ 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.
6/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).

7/37


5.3. MỘT SỐ TÍNH CHẤT CỦA
ĐỒ THỊ HAI PHẦN (tiếp)
Chứng minh định lý:
1) 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

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.
10/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 .

11/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.
12/37


5.3. MỘT SỐ TÍNH CHẤT CỦA
ĐỒ THỊ HAI PHẦN (tiếp)

15/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) |.
16/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.
17/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 ?


20/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”.
21/37


VÍ DỤ 5.7
Đồ thị và đồ thị riêng hai phần:
2

1

3

4

5

6

2