Giải thích định lý bốn màu
Năm 1852, một nhà toán học trẻ khi tô màu bản đồ các hạt của nước Anh đã nhận thấy rằng bốn màu dường như là đủ để phân biệt các hạt láng giềng. Liệu điều đó có đúng với mọi bản đồ có thể có? Câu hỏi này trở thành một trong những bài toán nổi tiếng nhất của toán học, dẫn tới một chứng minh sai lừng danh đứng vững suốt mười một năm, và cuối cùng được giải quyết vào năm 1976 theo một cách đã thay đổi điều mà các nhà toán học chấp nhận là một chứng minh.
Câu hỏi
Francis Guthrie, một cựu sinh viên của Augustus De Morgan, đã hỏi liệu mọi bản đồ có thể được tô bằng bốn màu sao cho các quốc gia có chung biên giới nhận màu khác nhau hay không. Hai quy tắc làm cho câu hỏi trở nên chính xác. Các quốc gia phải liên thông, mỗi quốc gia là một mảnh liền, và các quốc gia chỉ gặp nhau tại một điểm duy nhất thì không được tính là láng giềng. Rõ ràng ba màu không phải lúc nào cũng đủ, vì một quốc gia bị bao quanh bởi một vòng ba quốc gia khác đều tiếp giáp nhau sẽ cần màu thứ tư. Câu hỏi là liệu có bao giờ cần đến màu thứ năm.
Bản đồ như đồ thị
Đánh dấu một điểm trong mỗi quốc gia và vẽ một đường nối hai điểm bất cứ khi nào hai quốc gia của chúng có chung biên giới. Kết quả là một đồ thị, và vì bản đồ nằm trên một tờ giấy phẳng nên các đường có thể vẽ mà không cắt nhau: đồ thị là đồ thị phẳng. Tô màu bản đồ chính là tô màu các đỉnh của đồ thị này sao cho hai đầu của mọi cạnh khác màu nhau. Số màu nhỏ nhất đáp ứng được gọi là sắc số, và định lý bốn màu khẳng định không có đồ thị phẳng nào có sắc số lớn hơn bốn.
Chứng minh thất bại của Kempe
Năm 1879, luật sư kiêm nhà toán học Alfred Kempe công bố một chứng minh. Ý tưởng khéo léo của nó, nay gọi là chuỗi Kempe, là hoán đổi hai màu dọc theo một chuỗi quốc gia liên thông để giải phóng một màu ở chỗ cần đến. Chứng minh này được chấp nhận suốt mười một năm, cho đến khi Percy Heawood tìm ra một lỗ hổng vào năm 1890. Bản sửa của Heawood chứng minh được một kết quả yếu hơn: năm màu luôn đủ. Chuỗi Kempe vẫn tồn tại và trở thành một công cụ trong chứng minh sau cùng.
Vì sao năm màu thì dễ
Mọi đồ thị phẳng đều có một đỉnh có nhiều nhất năm láng giềng; điều này suy ra từ công thức Euler, vốn giới hạn một đồ thị phẳng có n đỉnh ở nhiều nhất 3n − 6 cạnh. Hãy bỏ một đỉnh như vậy, tô phần còn lại của bản đồ bằng cùng lập luận, rồi đặt đỉnh đó trở lại. Nếu các láng giềng của nó dùng ít hơn năm màu thì còn một màu trống. Nếu chúng dùng đủ cả năm, một phép hoán đổi theo chuỗi Kempe luôn giải phóng được một màu. Với bốn màu, cùng phép hoán đổi đó có thể thất bại, và đó chính là lỗ hổng mà Kempe đã bỏ sót.
Chứng minh bằng máy tính
Năm 1976, Kenneth Appel và Wolfgang Haken tại Đại học Illinois đã chứng minh định lý. Họ chỉ ra rằng mọi bản đồ đều chứa ít nhất một trong 1.936 cấu hình thuộc một tập không thể tránh, và mỗi cấu hình đều khả quy: một bản đồ nhỏ nhất cần năm màu không thể chứa nó. Việc kiểm tra tính khả quy mất hơn một nghìn giờ trên máy tính, quá nhiều để kiểm chứng bằng tay. Nhiều nhà toán học cảm thấy không yên tâm với một chứng minh mà không ai có thể đọc trọn vẹn, và cuộc tranh luận về các chứng minh có máy tính hỗ trợ bắt đầu.
Chứng minh đơn giản hơn và kiểm chứng trọn vẹn
Năm 1996, Neil Robertson, Daniel Sanders, Paul Seymour và Robin Thomas công bố một chứng minh có hệ thống hơn với 633 cấu hình, vẫn được kiểm tra bằng máy tính nhưng dễ kiểm chứng hơn. Năm 2005, Georges Gonthier và Benjamin Werner đã hình thức hóa toàn bộ chứng minh trong trợ lý chứng minh Coq, để một chương trình nhỏ, đáng tin cậy kiểm tra từng bước logic. Ngày nay định lý bốn màu là một trong những kết quả được kiểm chứng kỹ lưỡng nhất trong toán học.
Các thuật toán tô màu
Trong thực tế, tìm một cách tô bốn màu cho một bản đồ cho trước là nhanh, nhưng tìm số màu ít nhất cho một đồ thị tổng quát lại khó: quyết định xem ba màu có đủ hay không là bài toán NP-đầy đủ. Các phương pháp thực tế gồm tô màu tham lam theo thứ tự bậc giảm dần, DSATUR, tô tiếp đỉnh bị ràng buộc nhiều nhất, và tìm kiếm quay lui, khám phá các lựa chọn và hủy chúng khi bế tắc. Tô màu đồ thị giúp xếp lịch thi không bị trùng, gán tần số vô tuyến để các trạm phát gần nhau không gây nhiễu cho nhau, và cấp phát thanh ghi trong trình biên dịch.
Khám phá
Hãy mở công cụ tô màu bản đồ bốn màu để tạo các bản đồ có từ 4 đến 120 quốc gia, tự tay tô chúng bằng bốn màu và xem các xung đột hiện lên màu đỏ. Hãy để tô màu tham lam, DSATUR hoặc quay lui giải bản đồ từng bước, hiện đồ thị của các quốc gia láng giềng, và kiểm tra số màu ít nhất mà bản đồ thực sự cần.
Câu hỏi thường gặp
Định lý có giúp ích cho người vẽ bản đồ không?
Hầu như không. Bản đồ thực tế thường được tô bằng nhiều màu hơn cho rõ ràng, và có cả đại dương, hồ và những quốc gia gồm nhiều mảnh, những thứ mà định lý không bao quát. Tầm quan trọng của nó nằm ở toán học: nó thúc đẩy sự phát triển của lý thuyết đồ thị và đặt ra câu hỏi thế nào thì được coi là một chứng minh.
Chuỗi Kempe là gì?
Lấy hai màu, chẳng hạn đỏ và xanh lam, và một quốc gia tô màu đỏ. Chuỗi Kempe của nó là tập hợp tất cả các quốc gia đỏ và xanh lam mà bạn có thể đi tới từ nó bằng cách chỉ bước qua các láng giềng màu đỏ và xanh lam. Hoán đổi đỏ và xanh lam trên toàn bộ chuỗi vẫn giữ cho cách tô hợp lệ, và có thể giải phóng một màu cho một quốc gia nằm cạnh chuỗi.
Vì sao các quốc gia gồm nhiều mảnh lại phá vỡ định lý?
Nếu một quốc gia có thể gồm các vùng tách rời mà tất cả phải cùng một màu, thì đồ thị láng giềng không còn phẳng nữa, và có thể dựng những bản đồ cần bất kỳ số màu nào lên tới 12 với hai mảnh cho mỗi quốc gia, như Heawood đã nghiên cứu trong bài toán đế quốc của ông.
Vì sao công cụ tạo bản đồ từ các điểm?
Mỗi quốc gia là vùng của hình vuông gần một điểm ngẫu nhiên hơn bất kỳ điểm nào khác, tức là một sơ đồ Voronoi. Cách này cho ra những bản đồ trông thực tế gồm các quốc gia lồi, và hai quốc gia là láng giềng khi và chỉ khi vùng của chúng có chung một đoạn biên giới, điều mà ứng dụng tính toán chính xác.
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.
Mở công cụ tô màu bản đồ bốn màu