Chương 1: TỔNG QUAN MỘT SỐ VẤN ĐỀ VỀ ĐỒ THỊ VÀ ĐỒ THỊ HAI PHÍA 1. Các khái niệm cơ bản 1. Đồ thị Đồ thị vô hướng G = (V,E) gồm[4]: - V là tập hợp khác rỗng mà các phần tử của nó gọi là đỉnh (vertex) của G. - E là đa tập hợp gồm các cặp không sắp thứ tự của hai đỉnh.
Mỗi phần tử của E được gọi là một cạnh (edge) của G. Đồ thị vô hướng không có cạnh song song và không có khuyên gọi là đồ thị đơn vô hướng. Đồ thị hai phía Một đồ thị đơn vô hướng G:=(V,E) được gọi là hai phía nếu tồn tại một phân hoạch tập đỉnh V thành hai tập con X1 và X2 độc lập, rời nhau sao cho bất kì cạnh nào của đồ thị cũng nối một đỉnh thuộc X1 với một đỉnh thuộc X2. Khi đó người ta còn kí hiệu là: G:=(X1X2,E) với các phân hoạch X1, X2 và gọi một tập (chẳng hạn X1) là tập các đỉnh trái và tập còn lại (chẳng hạn X2) là tập Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 các đỉnh phải của đồ thị hai phía G.
Các đỉnh thuộc X1 gọi là các X1_đỉnh, các đỉnh thuộc X2 gọi là các X2_đỉnh. Nếu |X1|=|X2| thì G được gọi là đồ thị hai phía cân bằng. Đồ thị hai phía không có chu trình Hình 3. Đồ thị hai phía có chu trình Hình 4.Đồ thị không phải đồ thị hai phía 1.
Đồ thị hai phía đầy đủ Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 13 Cho G = (V,E) là một đồ thị vô hướng hai phía, một phân hoạch V thành hai tập con X1 và X2 (X1 ≠ ≠ X2 và X1 X2 = ), sao cho không có cạnh nối giữa 2 điểm trong cùng một tập con. Khi đó G được gọi là hai phía đầy đủ nếu: Với mọi cặp đỉnh (i,j) mà iX1 và j X2 thì có đúng một cạnh nối i và j, ij là một cạnh trong E. Một đồ thị hai phía đầy đủ với các phân chia kích thước |X1| = m, |X2| = n được kí hiệu là Km,n. Hai đồ thị mà có kí hiệu giống nhau thì chúng đẳng cấu.
- Đồ thị hai phía đầy đủ Km,n có: m+n đỉnh, m. - Các dạng đồ thị đầy đủ hai phía: K1,n với đồ thị hình sao Hình 5.Đồ thị hai phía đầy đủ hình sao K1,n với đồ thị hình vuốt cây Hình 6. Đồ thị hai phía đầy đủ hình vuốt cây Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 14 Km,n với m≠n Hình 7. Đồ thị hai phía đầy đủ m≠n Km,n với m = n Hình 8.
Đồ thị hai phía đầy đủ m=n 1. Bài toán ghép cặp không trọng 1. Bài toán Cho một đồ thị hai phía G = (X1X2,E) ở đây X1 là các tập đỉnh trái và X2 là tập các đỉnh phải của G. Một bộ ghép (matching) của G là một tập các cạnh của G đôi một không có đỉnh chung.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 15 Bài toán ghép cặp (matching problem) là tìm một bộ ghép lớn nhất (nghĩa là có số cạnh lớn nhất) của G. Xét một bộ ghép M của G. - Các đỉnh trong M gọi là các đỉnh đã ghép (matched vertices), các đỉnh khác là chưa ghép. - Các cạnh trong M gọi là các cạnh đã ghép, các cạnh khác là chưa ghép.
Nếu định hướng lại các cạnh của đồ thị thành cung, những cạnh chưa ghép được định hướng từ X1 sang X2, những cạnh đã ghép định hướng từ X2 về X1 .Trên đồ thị định hướng đó: Một đường đi xuất phát từ một X1_đỉnh chưa ghép gọi là đường pha (alternating path), một đường đi từ một X1_đỉnh chưa ghép tới một X2_đỉnh chưa ghép gọi là đường mở (augmenting path). Một cách dễ hiểu, có thể quan niệm như sau: - Một đường pha là một đường đi đơn trong G bắt đầu bằng một X1_đỉnh chưa ghép, đi theo một cạnh chưa ghép sang X2 , rồi đến một cạnh đã ghép về X1, rồi lại đến một cạnh chưa ghép sang X2… cứ xen kẽ nhau như vậy. - Một đường mở là một đường pha. Bắt đầu từ một X1_đỉnh chưa ghép kết thúc bằng một X2_đỉnh chưa ghép.
Ví dụ: Với đồ thị hai phía trong hình 9 và bộ ghép M ={(x1[1],x2[1]),(x1[2],x2[2])} x1[3] và x2[3] là những đỉnh chưa ghép, các đỉnh khác là đã ghép. Đường (x1[3], x2[3], x1[2], x2[1]) là đường pha. Đường (x1[3], x2[3], x1[2], x2[1], x1[1], x2[3]) là đường mở. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Đồ thị hai phía và bộ ghép M 1. Thuật toán đường mở Thuật toán đường mở để tìm một bộ ghép lớn nhất cho bài toán ghép cặp phát biểu như sau: Bước 1: Bắt đầu từ một bộ ghép bất kỳ M (thông thường bộ ghép được khởi gán bằng bộ ghép rỗng hay được tìm bằng các thuật toán tham lam). Bước 2: Tìm một đường mở. Bước 3: Nếu bước 2 tìm được đường mở thì mở rộng bộ ghép M: Trên đường mở, loại bỏ những cạnh đã ghép khỏi M và thêm vào M những cạnh chưa ghép.
Sau đó lặp lại bước 2. Nếu bước 2 không tìm được đường mở thì thuật toán kết thúc. * Mã giả thuật toán: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 17 Input: Đồ thị hai phía G = (X1X2,E), X1={x1[1], x1[2],…, x1[m]}, X2={x2[1], x2[2],…, x2[n]}. Output: Một bộ ghép M lớn nhất của G.
Như ví dụ trên, với bộ ghép hai cạnh M ={(x1[1],x2[1]),(x1[2],x2[2])} và đường mở tìm được gồm các cạnh: (x1[3], x2[2]) M (x2[2], x1[2]) M (x1[2], x2[1]) M (x2[1], x1[1]) M (x1[1], x2[3]) M Vậy thì ta sẽ loại đi các cạnh (x2[2], x1[2]) và (x2[1], x1[1]) trong bộ ghép cũ và thêm vào đó các cạnh (x1[3], x2[2]), (x1[2], x2[1]), (x1[1], x2[3]) được bộ ghép 3 cạnh. Bài toán ghép cặp với trọng số cực tiểu 1. Bài toán Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 18 Cho một đồ thị hai phía G = (X1X2,E). Được cho bởi ma trận vuông C cỡ kk, c[i, j] = trọng số cạnh nối đỉnh x1[i] với x2[j].
Giả thiết c[i, j]0 (i, j) Bài toán ghép cặp với trọng số cực tiểu là tìm một bộ ghép đầy đủ trọng số nhỏ nhất. Hai định lý sau đây tuy rất đơn giản nhưng là những định lý quan trọng tạo cơ sở cho thuật toán sẽ trình bày. Định lý 1: Loại bỏ khỏi G những cạnh trọng số lớn hơn 0. Nếu những cạnh trọng số 0 còn lại tạo ra bộ ghép k cạnh trong G thì đây là bộ ghép cần tìm.
Chứng minh: theo giả thiết, các cạnh của G mang trọng số không âm nên bấy kỳ bộ ghép nào trong G cũng có trọng số không âm, mà bộ ghép ở trên mang trọng số 0, nên tất nhiên đó là bộ ghép đầy đủ trọng số nhỏ nhất. Định lý 2: Với đỉnh x1[i], nếu ta cộng thêm một số (dương hay âm) vào tất cả những cạnh liên thuộc với x1[i] (tương đương với việc cộng thêm vào tất cả các phần tử thuộc hàng i của ma trận C) thì không ảnh hưởng tới bộ ghép đầy đủ trọng số nhỏ nhất. Chứng minh: Với một bộ ghép đầy đủ bất kỳ thì có một và chỉ một cạnh ghép với x1[i]. Nên việc cộng thêm vào tất cả các cạnh liên thuộc với x1[i] sẽ làm tăng trọng số bộ ghép đó lên .
Vì vậy nếu như ban đầu, M là bộ ghép đầy đủ trọng số nhỏ nhất thì sau thao tác trên, M vẫn là bộ ghép đầy đủ trọng số nhỏ nhất. Các khái niệm Để cho gọn, ta gọi những cạnh trọng số 0 của G là những 0_cạnh. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 19 Xét một bộ ghép M chỉ gồm những 0_cạnh. - Những đỉnh M gọi là những đỉnh đã ghép, những đỉnh còn lại gọi là những đỉnh chưa ghép.
- Những 0_cạnh M gọi là những 0_cạnh đã ghép, những 0_cạnh còn lại là những 0_cạnh chưa ghép. Nếu ta định hướng lại các 0_cạnh theo cách: Những 0_cạnh chưa ghép cho hướng từ tập X1 sang tập X2, những 0_cạnh đã ghép cho hướng từ tập X2 về tập X1. Khi đó: - Đường pha là một đường đi cơ bản xuất phát từ một X1_ đỉnh chưa ghép đi theo các 0_cạnh đã định hướng ở trên. Như vậy dọc trên đường pha, các 0_cạnh chưa ghép và những 0_cạnh đã ghép xen kẽ nhau.
Vì đường pha chỉ là đường đi cơ bản trên đồ thị định hướng nên việc xác định những đỉnh nào có thể đến được từ x X1 bằng một đường pha có thể sử dụng các thuật toán tìm kiếm trên đồ thị. Những đỉnh và những cạnh được duyệt qua tạo thành một cây pha gốc x. - Một đường mở là một đường pha đi từ một X1_ đỉnh chưa ghép tới một X2_đỉnh chưa ghép. Như vậy: - Đường đi trực tiếp từ một X1_đỉnh chưa ghép tới một X2_đỉnh chưa ghép qua một 0_cạnh chưa ghép cũng là một đường mở.
- Dọc trên đường mở, số 0_cạnh chưa ghép nhiều hơn số 0_cạnh đã ghép đúng 1 cạnh. Thuật toán Hungari Bước 1: Khởi tạo Một bộ ghép M := Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 20 Bước 2: với mọi đỉnh x X1, ta tìm cách ghép x: Bắt đầu từ đỉnh x, thử tìm đường mở bắt đầu ở x bằng thuật toán tìm kiếm trên đồ thị. Có hai khả năng có thể xảy ra: - Hoặc tìm được đường mở thì dọc theo đường mở, ta loại bỏ những cạnh đã ghép khỏi M và thêm vào M những cạnh chưa ghép, ta được một bộ ghép mới nhiều hơn bộ ghép cũ 1 cạnh và đỉnh x trở thành đã ghép. - Hoặc không tìm được đường mở thì có thể xác định được: VisitedX1= {Tập những X1_đỉnh có thể đến được từ x bằng một đường pha} VisitedX2= {Tập những X2_đỉnh có thể đến được từ x bằng một đường pha} Gọi là trọng số nhỏ nhất của các cạnh nối giữa một đỉnh thuộc VisitedX1 với một đỉnh không thuộc VisitedX2.
Dễ thấy >0 bởi nếu =0 thì tồn tại một 0_cạnh (x1, x2) với x1VisitedX1 và x2VisitedX2. Vì x đến được x1 bằng một đường pha và (x1, x2) là một 0_cạnh nên x cũng đến được x2 bằng một đường pha, dẫn tới x2 VisitedX2, điều này vô lý.