Lý thuyết đồ thị - Bài 08: Cặp ghép và đồ thị hai phần

1/37
CHƯƠNG 5


CẶP GHÉP VÀ ĐỒ THỊ
HAI PHẦN

2/37
NỘI DUNG
Tập đỉnh tựa và cặp ghép
Đồ thị hai phần
Đồ thị riêng hai phần

3/37
5.1. TẬP ĐỈNH TỰA VÀ CẶP GHÉP
Bài toán phân công nhiệm vụ
Khái niệm tập đỉnh tựa
Khái niệm cặp ghép
4/37
BÀI TOÁN PHÂN CÔNG NHIỆM VỤ
Một cơ quan có:
- n nhân viên: x1, x2, …, xn
- m nhiệm vụ: y1, y2,…, ym .
Mỗi nhân viên có thể đảm nhiệm một hay nhiều
nhiệm vụ và mỗi nhiệm vụ có một số nhân viên có
thể đảm nhiệm được.

Yêu cầu: Phân công cho mỗi nhân viên đảm nhiệm một nhiệm vụ thích hợp với trình độ của người đó?
5/37
TẬP ĐỈNH TỰA
Định nghĩa 5.1
Giả sử G = (V, E) là một đồ thì vô hướng.
Tâp C  V được gọi là tập đỉnh tựa nếu mỗi cạnh
của G đều kề với ít nhất một đỉnh nào đó trong C.
6/37
TẬP ĐỈNH TỰA (tiếp)
Tập đỉnh tựa của một đồ thị luôn tồn tại.
Ví dụ: Tập tất cả các đỉnh.
Song ta thường quan tâm đến tập đỉnh tựa có ít đỉnh nhất.

C là tập đỉnh tựa  V C là tập ổn định trong.


7/37
CẶP GHÉP
Định nghĩa 5.2
Giả sử G = (V, E) là một đồ thì vô hướng.
Tập W  E được gọi là cặp ghép nếu trong W không có hai cạnh nào kề nhau.
8/37
CẶP GHÉP (tiếp)
- Cặp ghép của một đồ thị luôn tồn tại.
- Mỗi cạnh trong cặp ghép tạo nên sự ghép giữa một đỉnh với đỉnh kề của nó.
- Ta thường quan tâm đến các cặp ghép có nhiều cạnh nhất.


9/37
VÍ DỤ 5.1
Với đồ thị cho trên hình vẽ:
- Các tập đỉnh tựa: {1, 2, 6}, {2, 5, 6}, ...
- Các cặp ghép: {(1,2), (3,6)}, {(1,5), (2,4), (3,6)}, ...


10/37
5.2. ĐỒ THỊ HAI PHẦN
Khái niệm đồ thị hai phần
Thuật toán kiểm tra một đồ thị là đồ thị hai phần
Một số tính chất của đồ thị hai phần



11/37
5.2. ĐỒ THỊ HAI PHẦN (tiếp)
Định nghĩa 5.2
Đồ thị G = (V, F) được gọi là đồ thị hai phần nếu tập
đỉnh V có thể tách thành hai tập ổn định trong không
giao nhau.
V = V1  V2 , V1  V2 =  ,
F(V1)  V2 , F(V2)  V1 .

12/37
5.2. ĐỒ THỊ HAI PHẦN (tiếp)
Khi đó, mỗi cạnh có một đầu thuộc V1 và đầu kia thuộc V2.
V1 và V2 là các tập đỉnh tựa của đồ thị G.
Nếu đồ thị có ít nhất một cạnh, khái niệm đồ thị hai phần trùng với điều kiện sắc số bằng 2.

Ký hiệu đồ thị hai phần là: G = (V1, V2, F).

13/37
VÍ DỤ 5.2
Cho đồ thị vô hướng (hình bên trái):





Vẽ lại đồ thị (hình bên phải) ta nhận được:
- Đồ thị trên là đồ thị hai phần.
- Tập đỉnh tựa bé nhất là {1, 2, 7}.
- Cặp ghép lớn nhất là {(1,3), (2,5), (4,7)}.
14/37
KIỂM TRA MỘT ĐỒ THỊ
LÀ ĐỒ THỊ HAI PHẦN
Thuật toán 5.1
1) Chọn một đỉnh bất kỳ a trong đồ thị G.
2) Đặt V1 = {a}.
3) Đặt V2 là tập các đỉnh kề của các đỉnh trong V1.
4) Nếu V1  V2   thì kết luận đồ thị không phải là đồ thị hai phần, ngược lại thì quay lên bước 3)
5) Khi hết đỉnh để thêm vào, nếu V1  V2 =  thì kết luận đồ thị là đồ thị hai phần.


15/37
VÍ DỤ 5.3
Xét đồ thị vô hướng được cho trên hình vẽ.






- Bắt đầu chọn: V1 = {1} , V2 = {2, 4}.
Sau đó thêm vào V1 = {1, 2, 3, 4, 5} , ta có:
V1  V2  .
Kết luận: đồ thị không phải là đồ thị hai phần.
Nếu bỏ cạnh (2, 4) thì đồ thị trên trở thành đồ thị hai phần.