Skip to content

Lấy người mình yêu và định lý Birkoff

Tháng Mười Hai 4, 2010

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, vv. Phải lấy người mình yêu, chà !

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ó \le 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 lai 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 thẻoem) nói rằng đây cũng là điều kiện đủ.

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

Đjinh 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 đỏ.

Định lý Hall. G có perfect matching khi và chỉ khi vơi mọi k, với mọi tập đỏ S với k phần tử, số đỉnh xanh nối vởi S ít nhất là k.

Định lý Hall chứng minh không khó, bạn có thể thử dưới dạng bài tập. Trong phần còn lại của bài, ta sẽ dùng định lý Hall để chứng minh một trong những định lý quan trọng nhất trong đại số tuyến tính: định lý Birkoff. Để phát biếu định lý này, ta cần một khái niệm. Một ma trận n \times n được gọi là doubly stochastic nếu các phần tử là số không âm và tổng mối hàng và mỗi cột là một. Nếu ta biếu diễn ma trận đưới dạng một điểm trong không gian R^{n^2} thì các ma trận DS tạo thành một tập lồi; chính xác hơn, một đa diện lồi S. Câu hỏi đặt ra là: tìm đỉnh của đa diện này. Câu hỏi này quan trọng, vì trong rất nhiều bài toán cực trị, giá trị cực trị được đạt được trên các đỉnh.

Birkoff tìm ra câu trả lời rất đẹp cho câu hỏi này. Một ma trận DS được gọi là “permutation matrix” nếu mỗi hàng và mỗi cột có chính xác một số một (còn lại là không). Bạn có thể dễ dàng thấy rằng mối PM tương đương với một phần tử \sigma của nhóm giao hoán S_n. Bạn cũng có thể dễ dàng chứng minh các PM là đỉnh của đa diện S. Birkoff chứng minh rằng ngoài ra không còn đỉnh nào khác.

Định lý Birkoff. Tập PM là các đỉnh duy nhất của đa diện S.

Giả sử A là một ma trận với phần tử a_{ij}. Với mỗi giao hoán \sigma, ta gọi dãy a_{1 \sigma (1)}, \dot, a_{n \sigma n} là một diagonal của A. Bạn có thể dùng định lý Hall để chứng minh bổ đề sau

{ Bổ đề.} Nếu mỗi diagonal của A có ít nhất một số 0 thì A có một k \times l ma trận con với các phần tử đều bằng 0k+l > n.

Chứng minh định lý Birkoff. Giả sử A là một điểm trong S. Ta sẽ chứng minh A có thể viết đưới dạng \sum_{i=1}^m \lambda_i M_i, với \sum_I \lambda_i=1, \lambda_i \ge 0M_i là PM. Ta qui nạp theo số phần tử dương của A. Nếu An phần tử dương thì nó là một PM. Giả sử Am \ge n+1 phần tử dương. Bạn có thể dễ dàng kiểm tra là một ma trận DS không thể có một ma trận con như trong bổ đề (bài tập). Như vậy, ta có một diagonal gồm toàn số dương. Diagonal này gắn với một phép giao hoán \sigma, và qua đó, một PM P. Gọi a là giá trị (dương) nhỏ nhất trong diagonal trên và B: = \frac{A- aP}{1-a}.

B cũng là một DS matrix. Ngoài ra sồ phần tử dương của nó \le m-1. Vậy B có thể biểu diến dưới dạng \sum_{i=1}^m \lambda_i M_i. Nhưng, A = (1-a) B + aP. QED

From → Khác

18 phản hồi
  1. Leobio permalink

    Dẫn nhập bài quá tuyệt🙂
    Nhưng có vẻ phân biệt Nam/Nữ nhỉ. Thế nhỡ con gái không lấy được người mình yêu thì sao ạ?🙂

  2. Anh VHV vào đề duyên dáng quá.

  3. Em cũng rất hâm mộ Angelina Jolie.

    Lâu rồi không thấy anh Văn viết thêm bài cho báo TP gì cả. Hình như anh vẫn đang ấp ủ đề tài học trước chương trình ở trường phổ thông thì phải.

    À, anh vẫn còn nhuận bút chưa lấy ở báo TP đấy nhé.

  4. Hi anh Văn, thanks for the post! Xin bình loạn vài ý:

    1. Có typo: “perfect matching” phải phủ cả đỉnh xanh lẫn đỏ; nếu chỉ phủ đỏ thì gọi là “complete matching”.

    2. Định lý Birkhoff có thể chứng minh một cách “trực quan” hơn bằng cách

    2a. xây dựng một edge-weighted bipartite graph từ ma trận M (cạnh ij có cân nặng m_{ij},

    2b. dùng định lý Hall để “lọc” ra một perfect matching (PM) với weight của cạnh nhỏ nhất \alpha > 0, PM này cho ta một ma trận hoán vị P,

    2c. gán M = M - \alpha P và quay lại bước 2b.

    3. Có lẽ các bác làm Toán ít biết đến thực tế là thuật toán tìm max-weight matching trên bipartite graphs là một trọng những thành phần cơ bản của thiết kế các routers tốc độ khủng trên Internet. Tiếc rằng thuật toán matching tốt nhất hiện nay chạy vẫn còn chậm quá, mà các routers ở trung tâm Internet cần cái time-scale là nanô giây.

    • Man permalink

      Anh Hung, cho em hoi doc them cho na`o de biet duoc ung dung max-weight bipartite matching trong routing vay anh? Bai tren mang thi nhieu nhung lung tung, nen em muon co paper na`o da’ng tin cay.

      • Chào Man,

        Bài này là một trong những bài kinh điển:

        J. Dai, B. Prabhakar, “The throughput of data switches with and without speedup,” Proceedings of IEEE INFOCOM Conference on Computer Communications, 2:556-564, March 2000.

        Ngoài ra, hy vọng lần sau bác Văn sẽ viết tiếp về bài toán “Hôn Nhân Bền Vững” (HNBV), tại vì “Lấy Người Mình Yêu” thôi chưa đủ làm cho HNBV. Ví dụ như anh A lấy chị A’, B lấy B’, nhưng B’ thích A hơn B, và A thích B’ hơn A’; thì khi sẽ dẫn đến … ngoại tình. Mà cái đa diện HNBV cũng thú vị, chưa kể ứng dụng trong Kinh Tế …

        Các routers cũng cần thuật toán Hôn Nhân Bền Vững, bài này cho biết HNBV dẫn đến 100% throughput:

        Shang-Tse Chuang, Ashish Goel, Nick McKeown, Balaji Prabhakar: Matching Output Queueing with a Combined Input Output Queued Switch. INFOCOM 1999: 1169-1178

      • Man permalink

        Cam on anh Hung!

        Em da biet Hungarian method va Stable-Marriage problem tu truoc. Co dieu vi em lam theory nen ko biet ve mat ung dung cua no’.

  5. Thu Ha permalink

    Anh viet duyen qua. Em von so nhung thu rat chi la logique nay, neu duoc mot lan lam hoc sinh cua anh thi chac … hiu het. Anh nhi. HIhi

  6. dongsongxanh permalink

    Chả hiếu mô tê gì. Dốt toán nên đành chịu.

  7. faithhw permalink

    @Leobio: Dù sao thì phụ nữ cũng hay lấy người yêu mình mà😀

  8. thanh nga permalink

    Nay bac go cong thuc toan trong wordpress bang cach nao vay?

  9. Rất thích nửa entry của bác, phần “Lấy người mình yêu” 😛, phần còn lại “định lý Birkoff” không thuộc chuyên môn của tui😛

  10. Thanks anh nhiều.
    Mà anh làm thế nào để gõ LaTeX vậy ?

  11. Its such as you learn my thoughts! You appear to understand a
    lot about this, like you wrote the guide in it or something.
    I think that you simply can do with some % to power the message home a little bit, however other than that, that is excellent blog. A great read. I’ll definitely be back.

Trackbacks & Pingbacks

  1. (st) Lấy người mình yêu và… không bỏ được (Nobel kinh tế 2012) | tazycanhga

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: