5.1. Tập đỉnh tựa và cặp ghép
Để đưa vào các khái niệm mới này, chúng ta xét bài toán phân công nhiệm
vụ như sau:
Một cơ quan có n nhân viên x
1, x
2, …, x
n và m nhiệm vụ y
1, y
2, …, y
m. Do
quá trình đào tạo, 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. Vậy có thể 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 đó được
không?
Bài toán này sẽ giải quyết được nhờ khái niệm cặp ghép mà chúng ta sẽ đưa
vào dưới đây.
Định nghĩa 5.1: Giả sử G là một đồ thị vô hướng.
Bạn đang xem 5. - LY THUYET DO THI BAI 8
