Code Jam 2009 - Vòng 3

Phân tích: Football Team

0. Vẽ đồ thị

Từ đề bài, rõ ràng đây là bài toán tô màu đồ thị — trên 1000 đỉnh. Nhưng chắc chắn câu chuyện chưa dừng ở đó. Hẳn phải có một tính chất đặc biệt khiến bài toán NP-đầy đủ nổi tiếng này giải được trong cuộc thi.

Biểu diễn mỗi cầu thủ bằng một đỉnh, và nối cạnh giữa hai cầu thủ nếu họ không thể dùng cùng màu. Hiển nhiên ta có thể vẽ đồ thị với mỗi cầu thủ nằm ngay tại vị trí \((x,y)\) của mình.

Như vậy có nhiều nhất 30 hàng cầu thủ. Điều này có giúp ích không? Quan sát ấy dẫn đến các lời giải đủ tốt cho bộ dữ liệu Nhỏ, nhưng không đủ cho bộ dữ liệu Lớn.

Trên mỗi hàng, các cạnh tạo thành một đoạn thẳng ngang từ điểm trái nhất đến điểm phải nhất. Mọi cạnh còn lại đều nối hai hàng kề nhau. Quan trọng hơn, không khó để quan sát và chứng minh rằng:

1. Nếu có ít nhất hai cạnh giữa hai hàng kề nhau, thì các cạnh ấy cùng các cạnh nằm ngang trên hàng tạo thành các tam giác.
2. Nếu vẽ mọi cạnh bằng đoạn thẳng, không có hai cạnh nào cắt nhau ở phần giữa.

Vậy, dù có bất ngờ hay không, đồ thị là đồ thị phẳng! Có các trường hợp đặc biệt dễ xử lý:

• Một màu là đủ khi và chỉ khi không có cạnh nào.
• Với đồ thị tổng quát, ta biết đồ thị tô được bằng 2 màu khi và chỉ khi không có chu trình lẻ. Trong bài này còn đơn giản hơn: có thể chứng minh rằng hễ tồn tại chu trình thì cũng phải tồn tại một tam giác. Vì thế đồ thị tô được bằng 2 màu khi và chỉ khi nó là một cây, đồng thời cũng tương đương với việc không có tam giác.

Ngoài các trường hợp đó, đáp án ít nhất là 3. Có thể bạn cũng biết rất rõ một trong những định lý nổi tiếng của thế kỷ trước, Định lý Bốn màu: 4 màu đủ để tô mọi đồ thị phẳng.

Đây là tin tốt: ngoài những trường hợp đặc biệt đơn giản, ta chỉ cần quyết định đáp án là 3 hay 4. Đáng tiếc, ngay cả bài toán này trong trường hợp tổng quát cũng được biết là NP-đầy đủ.

Như đã nói, ta đang xử lý một lớp đặc biệt ngay cả trong các đồ thị phẳng. Đồ thị hầu như được tam giác hóa, được bố trí gọn theo hàng, và mọi cạnh chỉ nối trong cùng hàng hoặc giữa hai hàng kề nhau. Hóa ra có nhiều lời giải cho bài toán này. Phần còn lại sẽ trình bày một vài lời giải. Trong mọi lời giải, ta thử tô đồ thị chỉ bằng 3 màu A, B và C; nếu thất bại thì đáp án là 4. Để trình bày đơn giản, ta cũng giả sử mọi điểm đều có bậc ít nhất 3 — nếu không, có thể loại bỏ nó mà không làm thay đổi khả năng tô bằng 3 màu.

1. Màu sắc gần như bị ép buộc

Chọn một tam giác bất kỳ. Ba đỉnh của nó phải mang ba màu khác nhau. Ta tô chúng bằng A, B và C. Có thể có một tam giác khác kề với nó, tức là chung một cạnh \(e\). Trong tam giác ấy, hai đỉnh của \(e\) đã được tô; nếu đỉnh thứ ba chưa được tô thì màu của nó giờ đã được quyết định!

Nhìn theo cách khác, quy tắc chỉ là: hễ có một đỉnh với hai hàng xóm kề nhau đã được tô màu, ta tô nó bằng màu thứ ba.

Vì mọi màu đều bị ép buộc, ngay khi gặp xung đột ta biết đáp án là 4.

Ta có thể thực hiện phép tô màu bắt buộc này gần như xuyên suốt. Dễ thấy chỉ cần tạm dừng đôi chút khi gặp một đỉnh khớp. Nhưng trường hợp này cũng không khó: đỉnh đó chia đồ thị thành phần trên và phần dưới; miễn là cả hai phần đều tô được bằng 3 màu, ta có thể ghép hai cách tô lại.

2. Đồ thị đối ngẫu

Lời giải trên hé lộ một khái niệm sâu hơn. Thực chất ta đang xét đồ thị đối ngẫu của một đồ thị phẳng; đồ thị đối ngẫu cũng là đồ thị phẳng. Mỗi mặt (trong bài này là mỗi tam giác) của đồ thị gốc trở thành một đỉnh, và hai đỉnh được nối nếu hai mặt tương ứng có chung một cạnh.

Nếu quen với thuật toán tô đồ thị bằng 2 màu và phát hiện chu trình lẻ, bạn có thể thấy nó rất giống lời giải trên. Ta sẽ lập luận rằng đồ thị gốc tô được bằng 3 màu khi và chỉ khi đồ thị đối ngẫu tô được bằng 2 màu (một màu dành cho tất cả các tam giác có thứ tự màu theo chiều kim đồng hồ).

Quan sát rằng nếu đồ thị gốc tô được bằng 3 màu, và một tam giác có ba đỉnh mang A, B, C theo chiều kim đồng hồ, thì mọi tam giác kề với nó bắt buộc phải có các đỉnh mang A, B, C theo chiều ngược kim đồng hồ. Do đó, đồ thị gốc tô được bằng 3 màu suy ra đồ thị đối ngẫu tô được bằng 2 màu.

Không khó để hình dung chứng minh chiều ngược lại, nhưng nó có nhiều chi tiết hơn và cần thêm một số điều kiện đối với đồ thị. Một cách dễ để chứng minh là quy nạp theo các hàng.

3. Tính chất cục bộ

Lời giải trên không giúp cài đặt đơn giản hơn nhiều. Nhưng nó dẫn đến một nhận xét còn đẹp hơn. Ta gọi một đỉnh của đồ thị gốc là đỉnh trong nếu nó được các tam giác bao quanh theo mọi hướng. Sự kiện sau cho lời giải đơn giản nhất của bài toán:

Đồ thị tô được bằng 3 màu khi và chỉ khi không có đỉnh trong nào có bậc lẻ.

Phần còn lại của mục này dành để chứng minh sự kiện ấy. Nếu một vài khẳng định về đồ thị phẳng và đồ thị đối ngẫu chưa có vẻ hiển nhiên, hãy thử vẽ vài hình để tự thuyết phục mình.

Mỗi đỉnh trong \(v\) có bậc \(d\) được bao quanh bởi \(d\) tam giác cùng chung đỉnh ấy. Trong đồ thị đối ngẫu, chúng tạo thành một chu trình độ dài \(d\) bao lấy \(v\) ở giữa.

Một chiều của chứng minh dễ hơn. Nếu \(v\) có bậc lẻ, ta thấy một chu trình lẻ trong đồ thị đối ngẫu, do đó đồ thị gốc không thể tô bằng 3 màu.

Bây giờ giả sử có một chu trình lẻ bất kỳ; chọn \(C\) là chu trình có diện tích bao quanh nhỏ nhất. Ta khẳng định \(C\) chỉ bao quanh một đỉnh trong, và vì thế ta tìm được một điểm trong có bậc lẻ. Có nhiều cách chứng minh điều này với một số chi tiết. Về cơ bản, nếu có hai đỉnh trong nằm bên trong, ta có thể tìm một đường tách chúng và cắt \(C\) tại hai vị trí. Đường này chia miền bên trong \(C\) thành hai miền nhỏ hơn, và không khó thấy một trong hai miền phải được bao bởi một chu trình lẻ. Điều đó mâu thuẫn với giả sử \(C\) là chu trình lẻ có diện tích nhỏ nhất, và hoàn tất bản phác thảo chứng minh cho lời giải ngắn gọn.

Trong hình dưới đây có một chu trình lớn độ dài 9, còn \(v\) là một đỉnh trong được bao quanh bởi một chu trình độ dài 5.

Trong hình dưới đây có một chu trình lớn độ dài 9, và \(v\) là một đỉnh trong được bao quanh bởi một chu trình độ dài 5.

4. Các lời giải khác

Ta đề cập hai lời giải vét cạn đủ tốt cho bộ dữ liệu Nhỏ. Muốn dùng chúng cho bộ dữ liệu Lớn, cần tối ưu rất nhiều và có lẽ rồi cũng sẽ phát hiện một trong những chìa khóa của các lời giải thời gian đa thức đã nêu trên.

Một lần nữa, ta xét đồ thị gốc. Giả sử đồ thị liên thông và mọi đỉnh đều có bậc ít nhất 3.

Nhận thấy có nhiều nhất 30 hàng. Ta có thể cố định màu của đỉnh đầu tiên trên mỗi hàng. Có \(2^{\text{số hàng}}\) cách làm việc này (thay vì \(3^{\text{số hàng}}\)). Một khi các màu ấy đã cố định, toàn bộ phần tô màu còn lại cũng được xác định, vì lý do tương tự phần 1.

Một lời giải khác là quy hoạch động: quét từ phải sang trái và ghi nhớ màu của đỉnh đầu tiên ở bên phải trên mỗi hàng. Lưu ý rằng không thể làm từ trái sang phải, vì theo hướng đó, biết màu của chỉ một đỉnh trên một hàng là chưa đủ.

Thông tin thêm

Tô màu đồ thị - Định lý Bốn màu - Đồ thị đối ngẫu

Lời giải dùng tính chất cục bộ rất giống một định lý của Heawood năm 1898: một đồ thị phẳng cực đại tô được bằng 3 màu khi và chỉ khi mọi bậc đều chẵn. Một định lý tổng quát hơn, kéo theo lời giải của chúng ta, có thể được tìm thấy trong bài báo A new 3-color criterion for planar graphs của Krzysztof Diks, Lukasz Kowalik và Maciej Kurowski.

Nguồn

Bản dịch dựa trên phân tích chính thức của Google Code Jam 2009 - Round 3 - Football Team, thuộc kho Google Coding Competitions (Apache-2.0).