Tô màu bản đồ theo định lý bốn màu
Dù một bản đồ phức tạp đến đâu, bốn màu vẫn luôn đủ để tô sao cho các quốc gia có chung biên giới không bao giờ trùng màu. Phát biểu này đơn giản đến mức một đứa trẻ có thể kiểm tra bằng bút sáp màu, vậy mà phải mất hơn một thế kỷ và cần đến máy tính mới chứng minh được. Hãy tự tô một bản đồ ngẫu nhiên, xem những đường biên giới nào xung đột, rồi xem ba phương pháp thực hiện, từ một quy tắc tham lam nhanh đôi khi cần đến màu thứ năm cho đến phép tìm kiếm quay lui luôn xoay xở được với bốn màu. Chọn một màu rồi nhấp vào các quốc gia để tô; đường biên giới chuyển sang màu đỏ khi hai quốc gia láng giềng trùng màu. Các quốc gia chỉ chạm nhau ở một góc thì được phép cùng màu. Hoặc để máy tính làm: chọn một phương pháp rồi nhấn Giải để xem nó thực hiện, hoặc nhấn Bước để theo dõi lần lượt từng thao tác. Ít màu nhất kiểm tra xem bản đồ này có thể chỉ cần ba, thậm chí hai màu hay không. Bản đồ mới vẽ một bản đồ khác, còn Hiện láng giềng vẽ mạng lưới các quốc gia có chung biên giới.
Cách nó hoạt động
- Chọn số quốc gia rồi nhấn Bản đồ mới, hoặc bắt đầu với bản đồ đang hiển thị.
- Chọn một màu và nhấp vào các quốc gia để tô, để ý các đường biên giới màu đỏ ở chỗ các láng giềng xung đột.
- Chọn một phương pháp rồi nhấn Giải hoặc Bước để xem nó tô bản đồ, và nhấn Ít màu nhất để xem bản đồ này cần bao nhiêu màu.
Từ bản đồ đến đồ thị
Đặt một điểm vào mỗi quốc gia và nối hai điểm khi hai quốc gia của chúng có chung biên giới. Bản đồ trở thành một đồ thị, và tô màu bản đồ cũng chính là tô màu các điểm sao cho hai điểm được nối khác màu nhau. Vì bản đồ được vẽ trên một tờ giấy phẳng, các đồ thị này là đồ thị phẳng: có thể vẽ chúng mà không có đường nào cắt nhau. Các quốc gia chỉ gặp nhau tại một điểm, như bốn hình vuông ở một góc, không phải là láng giềng. Định lý bốn màu khẳng định rằng mọi đồ thị phẳng đều có thể tô bằng bốn màu. Hãy bật Hiện láng giềng để xem đồ thị của bản đồ hiện tại.
Ba cách tô màu
Tô màu tham lam lần lượt xét từng quốc gia, bắt đầu từ những quốc gia có nhiều láng giềng nhất, và gán cho mỗi quốc gia màu đầu tiên mà các láng giềng của nó chưa dùng. Cách này nhanh nhưng thiển cận, và trên một số bản đồ nó phải dùng đến màu thứ năm, thậm chí thứ sáu. DSATUR, do Daniel Brélaz phát minh năm 1979, luôn chọn tiếp theo quốc gia mà các láng giềng đã có nhiều màu khác nhau nhất, nhờ vậy thường tránh được cái bẫy đó. Quay lui thử lần lượt từng màu và, khi một quốc gia không còn màu nào, hủy những lựa chọn gần nhất rồi thử lại; nó luôn tìm được cách tô bằng bốn màu, đôi khi sau khi phải quay lại rất nhiều lần.
Câu hỏi thường gặp
Vì sao bốn màu luôn đủ?
Chưa ai tìm ra một lý do ngắn gọn. Chứng minh của Kenneth Appel và Wolfgang Haken năm 1976 cho thấy mọi bản đồ đều phải chứa một trong 1.936 cấu hình nhỏ, và mỗi cấu hình này đều có thể được gỡ bỏ rồi sau đó khôi phục lại cách tô màu; việc kiểm tra tất cả mất hơn một nghìn giờ máy tính. Một chứng minh bằng máy tính đơn giản hơn của Neil Robertson, Daniel Sanders, Paul Seymour và Robin Thomas năm 1996 cần 633 cấu hình, và năm 2005 Georges Gonthier đã kiểm chứng trọn vẹn một chứng minh bằng trợ lý chứng minh Coq.
Có bản đồ nào cần đủ cả bốn màu không?
Có. Bốn quốc gia mà mỗi quốc gia đều tiếp giáp với ba quốc gia còn lại, chẳng hạn một quốc gia bị ba quốc gia khác bao quanh thành vòng, cần bốn màu. Tuy vậy, nhiều bản đồ chỉ cần ba, và Ít màu nhất sẽ xác định điều đó cho bản đồ trên màn hình. Việc quyết định một cách tổng quát xem một bản đồ có thể tô bằng ba màu hay không là một bài toán khó, NP-đầy đủ, dù bốn màu thì luôn đủ.
Vì sao phương pháp tham lam đôi khi dùng năm màu?
Nó tô mỗi quốc gia một lần và không bao giờ đổi ý. Một lựa chọn sớm có thể khiến một quốc gia về sau bị bao quanh bởi cả bốn màu, và lối thoát duy nhất là màu thứ năm. Còn quay lui thì sẽ quay trở lại và thay đổi các lựa chọn trước đó.
Định lý có đúng trên các mặt khác không?
Trên mặt cầu thì đúng: nó giống như mặt phẳng. Trên mặt xuyến, tức bề mặt của một chiếc bánh donut, một số bản đồ cần bảy màu, và bảy màu luôn đủ, như Percy Heawood đã chỉ ra. Nếu một quốc gia có thể gồm nhiều mảnh tách rời, như một nước có thuộc địa, thì bốn màu không còn đủ nữa.
Có dữ liệu nào được gửi lên máy chủ không?
Không. Bản đồ, các phương pháp tô màu và việc kiểm tra đều chạy trong trình duyệt của bạn. Các cài đặt của bạn được giữ trong bộ nhớ cục bộ của trình duyệt này.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Tới trình chỉnh sửa