Đẹp 1

Post này xuất phát từ post rất hay trên blog của Gil Kalai về câu đố 17 con lạc đà và ứng dụng rất đẹp của ý tưởng câu đố này vào bài toán cặp ghép hoàn hảo .


Câu đố 17 con lạc đà: Ba anh em được thừa hưởng 17 con lạc đà từ người cha. Di chúc của người cha nói rằng chia cho người anh cả một nửa, người anh thứ 2 một phần ba và người em út một phần chín. Hỏi họ phải làm thế nào để thực hiện di chúc này? (Dừng ở đây nếu bạn muốn tự suy nghĩ. Lời giải sẽ ngay sau.)

Trả lời: Ba anh em mượn thêm 1 con lạc đà từ người hàng xóm để có 18 con lạc đà. Giờ họ chia theo nguyện vọng người cha. Người anh cả được con, người anh thứ hai được con và người em út được con. Sau khi chia, họ vẫn còn dư 1 con và họ trả con lạc đà này lại cho người hàng xóm.


Bạn có thể chưa vừa lòng với câu trả lời vì hình như phép chia lạc đà này ăn gian ở đâu đó. Nhưng điều đó không quan trọng. Mục tiêu của bài viết là cách mà Noga Alon áp dụng ý tưởng này trong định lý sau:

Theorem 1: Luôn tồn tại một cặp ghép hoàn hảo trong đồ thị chính quy hai phía bậc 3.

 

Một đồ thị là chính quy bậc 3 (-regular) nếu mọi đỉnh trong đồ thị đều có bậc 3 (số cạnh kề với mỗi đỉnh là 3). Một cặp ghép (matching) được gọi là hoàn hảo (perfect matching) nếu mọi đỉnh đều xuất hiện trong cặp ghép.

Chứng minh Theorem 1: Gọi là số đỉnh của đồ thị, mỗi phía có đỉnh. Ta chọn một số sao cho với (logarithm cơ số ). (Tại sao luôn chọn được như vậy? xem gợi ý ở cuối bài).

Với mỗi cạnh của đồ thị, ta thêm bản copy để thu được một đa đồ thị với mỗi đỉnh có bậc . Sau đó, ta thêm một cặp ghép hoàn hảo (không nhất thiết phải là cặp ghép của đồ thị) vào đồ thị . Gọi là đồ thị thu được sau hai bước này. Không khó để thấy mỗi đỉnh trong có bậc . Do mọi đỉnh có bậc chẵn, tồn tại một chu trình Euler đi qua mọi cạnh của đồ thị đúng một lần. Đánh số các cạnh bắt đầu từ 0, theo cùng chiều kim đồng hồ dọc theo chu trình. Gọi là tập các cạnh lẻ của chu trình và là tập các cạnh chẵn của chu trình. Do là đồ thị hai phía, nó không có chu trình (có số cạnh) lẻ. Do đó, mỗi là một đồ thị chính quy bậc . Ngoài ra,

Một trong hai đồ thị , , chứa không quá một nửa số cạnh của

Gọi là đồ thị chứa không quá một nửa số cạnh của . Tiếp tục lặp lại tìm chu trình Euler của và phân thành hai đồ thị con, tìm đồ thị chính quy con chứa không quá một nửa các cạnh của trong , ta thu được . Tiếp tục như vậy đến khi thu được . Do , sẽ không chứa cạnh nào của chỉ có cạnh. Mỗi đỉnh trong có bậc , chính là một cặp ghép hoàn hảo của . Quá đẹp!!!!


Làm thế nào để chọn ? Ta sẽ chọn , . Giờ bạn chỉ cần chứng minh một trong ba số , , chia hết cho là xong.

Comments: Chứng minh của Theorem 1 còn có thể chuyển thành giải thuật để tìm cặp ghép hoàn hảo của trong thời gian như sau. Đầu tiên chuyển thành trong thời gian (do ). Gọi là số cạnh của () Sau đó tìm chu trình Euler trong trong thời gian (sử dụng thuật toán Hierholzer) và đệ quy. Tổng thời gian đệ quy cho đến khi chúng ta tìm được là:

Giải phương trình trên ta được . Thuật toán này nhanh hơn nhiều so với thuật toán Hopcroft-Karp (), thuật toán hiện tại tốt nhất tìm cặp ghép trên đồ thị hai phía.

Nguồn: Bài viết gốc của Gil Kalai ở đây. Bài báo của Noga Alon ở đây.

Disclaimer: Bài viết này người viết dựa trên ý tưởng của hai bài viết đã ghi trong nguồn. Bất cứ lỗi nào xuất hiện trong bài viết là lỗi của người viết bài này, không phải lỗi của hai bài viết trong nguồn.

Facebook Comments

Tags: , , , , , ,

Reply

Your email address will not be published. Required fields are marked *