Bài giảng Chương 5: Cặp Ghép Và Đồ Thị Hai Phần

CHƯƠNG 5CẶP GHÉP VÀ ĐỒ THỊ HAI PHẦN1NỘI DUNGTập đỉnh tựa và cặp ghépĐồ thị hai phầnĐồ thị riêng hai phần25.1. TẬP ĐỈNH TỰA VÀ CẶP GHÉPBài toán phân công nhiệm vụKhái niệm tập đỉnh tựaKhái niệm cặp ghép3BÀ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 đó?4TẬ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. 5TẬ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.6CẶ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. 7CẶ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.8VÍ DỤ 5.1Vớ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)}, ...	61243595.2. ĐỒ THỊ HAI PHẦNKhái niệm đồ thị hai phầnThuật toán kiểm tra một đồ thị là đồ thị hai phầnMột số tính chất của đồ thị hai phần105.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ônggiao nhau. 	V = V1  V2 , V1  V2 =  ,	F(V1)  V2 , F(V2)  V1 .115.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). 12VÍ DỤ 5.2Cho đồ 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)}. 6124357132476513KIỂ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.14VÍ DỤ 5.3Xé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.1425315