Tài liệu

Bài toán đám cưới vùng quê

Science and Technology

Bài toán đám cưới vùng quê

Có m chàng trai ở một vùng quê nọ. Đối với mỗi chàng trai ta biết các cô gái mà anh ta vừa ý. Hỏi khi nào thì có thể tổ chức các đám cưới trong đó chàng trai nào cũng sánh duyên với các cô gái mà mình vừa ý.

Ta có thể xây dựng đồ thị với các đỉnh biểu thị các chàng trai và các cô gái, còn các cung biểu thị sự vừa ý của các chàng trai với các cô gái. Khi đó ta thu được một đồ thị hai phía.

Ví dụ. Có 4 chàng trai { T1, T2, T3,T4}và 5 cô gái { G1, G2, G3,G4, G5}. Sự vừa ý cho trong bảng sau

Chàng trai Các cô gái mà chàng trai ưng ý
T1 G1, G4, G5
T2 G2
T3 G2, G3,G4
T4 G2, G4

Đồ thị tương ứng được cho trong hình dưới đây

Mạng tương ứng với bài toán đám cưới vùng quê.

Đưa vào điểm phát s và điểm thu t. Nối s với tất cả các đỉnh biểu thị các chàng trai, và nối t với tất cả các đỉnh biểu thị các cô gái. Tất cả các cung của đồ thị đều có khả năng thông qua bằng 1. Bắt đầu từ luồng 0, ta tìm luồng cực đại trong mạng xây dựng được theo thuật toán Ford-Fulkerson. Từ định lý về tính nguyên, luồng trên các cung là các số hoặc 1. Rõ ràng là nếu luồng cực đại trong đồ thị có giá trị Vmax = m, thì bài toán có lời giải, và các cung với luồng bằng 1 sẽ chỉ ra cách tổ chức đám cưới thoả mãn điều kiện đặt ra. Ngược lại, nếu bài toán có lời giải thì Vmax = m. Bài toán về đám cưới vùng quê là một trường hợp riêng của bài toán về cặp ghép trên đồ thị hai phía mà để giải nó có thể xây dựng thuật toán hiệu quả hơn.

Đánh giá:
0 dựa trên 0 đánh giá
Nội dung cùng tác giả
 
Nội dung tương tự