Lấy người mình yêu

Khi bé, bạn đi nhà trẻ. Lớn lên, bạn phải lấy vợ. Kiểu gì cũng không tránh được, trừ các vĩ nhân.

Chuyện lấy vợ ngày xưa rất đơn giản. Một ngày đẹp trời, bố khề khà nói với…mẹ “Tôi xem con Sứt con ông phó cối đầu ngõ chăm chỉ đáo để….” Thế là vài tháng sau bạn sẽ là chồng của cô Sứt, và ngày ngày đóng cối….

Chuyện bây giờ không đơn giản như thế nữa. Bạn có tự do, có quyền theo đuổi tình yêu, chắp cánh bay xa. Phải lấy người mình yêu!

Trớ trêu, người bạn yêu (như Angelina Jolie) thì vô số bạn khác cũng yêu. Thế mới cáu. Nhưng không sao, chuyện này các ông Tây cũng đã nghĩ tới, chẳng phải vì cô Angelina là Tây, mà ở bên Tây luật một vợ một chồng có sớm hơn ta, nên các bác ấy phải đi trước một bước, âu cũng là cực chẳng đã.

Các ông Tây giải quyết vấn đề như sau: Thay vì mỗi Angelina, mỗi ông lên một danh sách gồm các cô có thể đưa vào tầm ngắm. Danh sách này sẽ ngắn dài gầy béo tùy theo khả năng và sở thích mối người. Câu hỏi đặt ra là: Khi nào bạn có thể lấy được một người trong danh sách của bạn mà không dẫn đến một cuộc đọ súng đọ kiếm hay đọ một cái gì với các bạn khác ?

Điều kiện cần của bài toán tương đối dễ xác định. Tưởng tượng cô Mít và cô Đào rất “hot”, và là ý trung nhân của các anh Mai, Thuổng và Xẻng. Thế là hai thục nữ nhưng những ba anh hùng, kiếu gì cũng không ổn. Nói tổng quát, nếu danh sách của k chàng tổng cộng lại chỉ có <=k-1 nàng, thì thế nào cũng dẫn đến mâu thuẫn khó giải quyết. Vậy điều kiện cần của bài toán Lấy (một trong những) Người Mình Yêu là:

(1) Với mọi k, danh sách của bất kỳ k chàng trai nào tổng cộng lại phải có ít nhất k cô gái.

Định lý Lấy Người Mình Yêu của Hall (Hall Marriage’s theorem) nói rằng (đây cũng là điều kiện đủ).

Định lý Hall (1) là điều kiện đủ.

Định lý này có thể phát biểu dưới dạng đồ thị. Ta biểu diễn các chàng trai bằng chấm màu đỏ và các cô gái bằng chấm màu xanh. Đồ thị G có các cạnh giữa chấm xanh và chấm đỏ, A nối với B nếu nàng B ở trong danh sách của chàng A. Một “perfect matching” là một tập các cạnh không dính nhau phủ hết các đỉnh đỏ.