Định lý bốn màu

Định lý bốn màu (còn gọi là định lý bản đồ bốn màu) phát biểu rằng đối với bất kỳ mặt phẳng nào được chia thành các vùng phân biệt, chẳng hạn như bản đồ hành chính của một quốc gia, chỉ cần đến bốn màu để phân biệt các vùng lân cận với nhau. Hai vùng được coi là lân cận nếu như chúng có chung nhau một đoạn đường biên, không tính chung nhau một điểm.

Định lý bốn màu là định lý lớn đầu tiên được chứng minh bằng máy vi tính. Tuy nhiên một số nhà toán học không đồng tình với cách chứng minh này, bởi vì con người không thể kiểm chứng trực tiếp được cách chứng minh. Do vậy, muốn tin vào chứng minh này thì người ta phải công nhận sự chính xác của Trình biên dịch và phần cứng máy tính được sử dụng để chạy chương trình chứng minh.

Lịch sử

Vấn đề này lần đầu tiên được đề cập vào năm 1852 bởi Francis Guthrie khi ông thử tô màu bản đồ nước Anh và ông nhận ra rằng chỉ cần bốn màu khác nhau là đủ. Ông đã đem vấn đề này hỏi người anh trai là Fredrick, lúc đó đang là sinh viên của trường Đại học Học viện London (UCL). Fredrick đã đưa vấn đề này hỏi thầy của mình là nhà toán học Augustus De Morgan nhưng người thầy cũng chưa biết rõ vấn đề này.

Người đầu tiên giới thiệu vấn đề ra trước công chúng là nhà toán học Arthur Cayley vào năm 1878 tại Hội Toán học London, ông đã chỉ ra người đề cập vấn đề là De Morgan. Vào tháng 10/1852, giáo sư De Morgan ở trường Đại học Luân Đôn viết thư cho đồng nghiệp của mình là ông William Hamilton để bàn về bài toán: "Mọi bản đồ đều có thể tô bằng 4 màu sao cho hai nước nằm kề nhau phải được tô bằng hai màu khác nhau".^[1]

Người đầu tiên chứng minh định lý này là Alfred Kempe vào năm 1879. Năm 1880, có thêm một cách chứng minh khác của Peter Guthrie Tait. Nhưng đến năm 1890 Percy Heawood đã chỉ ra sai lầm trong cách chứng minh của Kempe, và đến năm 1891 Julius Petersen chỉ ra sai lầm trong cách chứng minh của Tait.

Trong việc chỉ ra sai lầm của Kempe, Heawood còn chứng minh rằng tất cả các Đồ thị phẳng phải sử dụng năm màu khác nhau, và làm cơ sở phát triển cho lời giải sau này. Xem Định lý năm màu.

Trong những năm 1960 và 1970, nhà toán học người Đức là Heinrich Heesch đã phát triển phương pháp sử dụng máy vi tính cho việc chứng minh vấn đề.

Năm 1976, cuối cùng thì định lý cũng được chứng minh bởi Kenneth Appel và Wolfgang Haken tại trường Đại học Illinois với sự trợ giúp của máy vi tính (trong khoảng 1000 giờ máy). Nhà khoa học John A. Koch cũng góp phần cải tiến thuật toán để giải quyết trọn vẹn bài toán 4 màu.^[2]

Không áp dụng vào thực tế

Mặc dù định lý được phát hiện ra trong quá trình tô màu bản đồ, nhưng trên thực tế nó rất ít khi được áp dụng vào khoa học vẽ bản đồ. Nhiều bản đồ phải sử dụng nhiều hơn bốn màu để thể hiện các khu vực, ngoài ra có những bản đồ sử dụng ít hơn bốn màu.

Hầu hết các bản đồ thực tế đều có vẽ hồ ao, mà tất cả hồ ao này phải vẽ cùng màu. Do vậy làm tăng số lượng màu cần thiết để vẽ các vùng đất. Nếu bỏ qua không vẽ hồ ao, thì trên thực tế vẫn có những vùng đất của cùng một quốc gia nhưng bị tách rời nhau, do đó phải vẽ cùng màu và định lý không áp dụng được.

Các sách vở về môn Bản đồ học cũng không nhắc đến định lý này. Những người vẽ bản đồ cho rằng họ quan tâm hơn đến việc phối màu bản đồ sao cho đẹp mắt; do vậy việc sử dụng bốn, năm hay nhiều màu hơn không phải là vấn đề đáng bận tâm.

Vị trí các phần lãnh thổ trên thực tế

Những vùng không liên tục

Trên thực tế có nhiều quốc gia mà các phần lãnh thổ không liền kề nhau. Ví dụ như phần lãnh thổ Alaska của nước Mỹ, Nakhchivan của Azerbaijan, hay Kaliningrad của Nga. Nếu việc vẽ bản đồ đòi hỏi các phần lãnh thổ này phải cùng màu thì việc sử dụng bốn màu là không đủ.

Trong toán học, những vùng đất tách rời này được gọi là điểm cô lập của tập hợp miền quốc gia.

Thử xét một hình vẽ đơn giản sau

Trong hình, hai khu vực được đánh dấu "A" cùng thuộc về một quốc gia, và phải được vẽ cùng màu. Bản đồ này phải sử dụng năm màu, nên cần chú ý một số điểm sau.

Các nước chung 1 điểm được xem là không kề nhau

Một số điểm cần chú ý

Để tránh một số hiểu lầm về bài toán 4 màu, chúng ta cần phải lưu ý một số trường hợp đặc biệt mà có thể ngộ nhận là giả thiết 4 màu không đúng:

Hai nước có chung 1 điểm được xem là không kề nhau: kề nhau phải có chung đường biên giới. Vì nếu không có quy ước này thì bản đồ có dạng như hình Các nước chung 1 điểm được xem là không kề nhau là phản ví dụ: phải dùng đến 5 màu (do 2 nước đôi một đều có chung 1 điểm).
Một nước phải là một vùng liên thông
Một nước phải là một vùng liên thông. Vì nếu không có quy ước này thì bản đồ có dạng như hình Một nước phải là một vùng liên thông là một ví dụ: bốn nước A, B, C, D đôi một kề nhau; nước E (có hai vùng đất 1 và 2) kề cả bốn nước A, B, C, D nên phải dùng đến 5 màu.
Bản đồ buộc phải dùng 4 màu
Con số 4 màu nói chung không thể hạ thấp xuống hơn: bản đồ có dạng như hình Bản đồ buộc phải dùng 4 màu buộc phải dùng đúng 4 màu.
Bản đồ phải được vẽ trên mặt phẳng hay mặt cầu: ta có thể tìm ví dụ về bản đồ vẽ trên phao bơi cần phải dùng trên 5 màu mới có thể tô được.

Giả thuyết 4 màu và số màu đồ thị phẳng

Để giải bài toán 4 màu, các nhà toán học đã tìm cách xây dựng các đồ thị tương ứng với các bản đồ và đưa giả thuyết 4 màu về giả thuyết số màu của đồ thị phẳng.

Với mỗi bản đồ, ta có thể định nghĩa một đồ thị:

Tập đỉnh: gồm các đỉnh mà mỗi đỉnh tương ứng với một nước trên bản đồ;
Tập cạnh: mỗi cạnh tương ứng với 2 nước kề nhau có chung một biên giới.

Ví dụ: Hình minh họa đồ thị (G) tương ứng với bản đồ Giả thuyết minh họa đồ thị (G) bên cạnh.

Mỗi vùng được ký hiệu bằng một chữ cái, các chữ này cũng được dùng để ký hiệu các đỉnh của đồ thị.

Từ ví dụ này ta thấy yêu cầu hai nước kề nhau phải có màu khác nhau khi tô bản đồ cũng tương ứng với yêu cầu hai đỉnh kề nhau phải có màu khác nhau khi thực hiện phép tô màu đỉnh cho đồ thị.

Các nhà toán học đã chứng minh được định lý sau đây:

Định lý: Đồ thị (G) được định nghĩa tương ứng với mỗi bản đồ M (theo như định nghĩa trên) luôn là đồ thị phẳng. Cách tô màu mỗi vùng của bản đồ M tương ướng với cách tô màu các đỉnh của đồ thị (G)

Nhờ định lý trên, giả thuyết 4 màu được quy về giả thuyết về số màu của đồ thị phẳng được phát biểu như sau:

Giả thuyết:

Mọi đồ thị phẳng (G) đều có số màu γ(G)≤4

Sau công trình của Kenneth Appel, Wolfgang Haken và John A. Koch thì giả thuyết trên đã trở thành định lý và ngày nay chúng ta cũng gọi là định lý 4 màu.

Cho đến bây giờ cũng chưa tìm được cách chứng minh định lý 4 màu mà không dùng kiểm chứng bằng máy tính. Một số công trình khác cũng tìm cách cải tiến thuật toán kiểm tra để chạy nhanh hơn.

Chú thích

^ Trần Đan Thư - Dương Anh Đức (2008). Lý Thuyết Đồ Thị. Nhà xuất bản Đại học Quốc gia TP Hồ Chí Minh.
^ Wilson, Robin (2002). Four Colors Suffice. London: Penguin Books. ISBN 0-691-11533-8.

Tham khảo

Allaire, F. (1997), “Another proof of the four colour theorem—Part I”, Proceedings, 7th Manitoba Conference on Numerical Mathematics and Computing, Congr. Numer., 20, tr. 3–72
Appel, Kenneth; Haken, Wolfgang (1977), “Every Planar Map is Four Colorable Part I. Discharging”, Illinois Journal of Mathematics, 21, tr. 429–490
Appel, Kenneth; Haken, Wolfgang; Koch, John (1977), “Every Planar Map is Four Colorable Part II. Reducibility”, Illinois Journal of Mathematics, 21, tr. 491–567
Appel, Kenneth; Haken, Wolfgang (1977), “Solution of the Four Color Map Problem”, Scientific American, 237 (4), tr. 108–121, doi:10.1038/scientificamerican1077-108
Appel, Kenneth; Haken, Wolfgang (1989), Every Planar Map is Four-Colorable, Providence, RI: American Mathematical Society, ISBN 0-8218-5103-9
Bernhart, Frank R. (1977), “A digest of the four color theorem.”, Journal of Graph Theory, 1, tr. 207–225, doi:10.1002/jgt.3190010305
Cayley, Arthur (1879), “On the colourings of maps”, Proc. Royal Geographical Society, Blackwell Publishing, 1 (4), tr. 259–261, doi:10.2307/1799998, JSTOR 1799998
Fritsch, Rudolf; Fritsch, Gerda (1998), The Four Color Theorem: History, Topological Foundations and Idea of Proof, New York: Springer, ISBN 978-0-387-98497-1
Gonthier, Georges (2008), “Formal Proof—The Four-Color Theorem” (PDF), Notices of the American Mathematical Society, 55 (11), tr. 1382–1393
Gonthier, Georges (2005), A computer-checked proof of the four colour theorem (PDF), unpublished
Hadwiger, Hugo (1943), “Über eine Klassifikation der Streckenkomplexe”, Vierteljschr. Naturforsch. Ges. Zürich, 88: 133–143
Heawood, P. J. (1890), “Map-Colour Theorem”, Quarterly Journal of Mathematics, Oxford, 24, tr. 332–338
Magnant, C.; Martin, D. M. (2011), “Coloring rectangular blocks in 3-space”, Discussiones Mathematicae Graph Theory, 31 (1): 161–170, Bản gốc lưu trữ ngày 4 tháng 2 năm 2022, truy cập ngày 17 tháng 7 năm 2012
Nash-Williams, C. St. J. A. (1967), “Infinite graphs—a survey”, J. Combinatorial Theory, 3: 286–301, MR 0214501.
O'Connor; Robertson (1996), The Four Colour Theorem, MacTutor archive, Bản gốc lưu trữ ngày 16 tháng 1 năm 2013, truy cập ngày 17 tháng 7 năm 2012
Pegg, A.; Melendez, J.; Berenguer, R.; Sendra, J. R.; Hernandez; Del Pino, J. (2002), “Book Review: The Colossal Book of Mathematics” (PDF), Notices of the American Mathematical Society, 49 (9): 1084–1086, Bibcode:2002ITED...49.1084A, doi:10.1109/TED.2002.1003756
Reed, Bruce; Allwright, David (2008), “Painting the office”, Mathematics-in-Industry Case Studies, 1: 1–8, Bản gốc lưu trữ ngày 3 tháng 2 năm 2013, truy cập ngày 17 tháng 7 năm 2012
Ringel, G.; Youngs, J.W.T. (1968), “Solution of the Heawood Map-Coloring Problem”, Proc. Nat. Acad. Sci. USA, 60 (2), tr. 438–445, doi:10.1073/pnas.60.2.438, PMC 225066, PMID 16591648
Robertson, Neil; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin (1996), “Efficiently four-coloring planar graphs”, Efficiently four-coloring planar graphs, STOC'96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, ACM Press, tr. 571–575, doi:10.1145/237814.238005
Robertson, Neil; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin (1997), “The Four-Colour Theorem”, J. Combin. Theory Ser. B, 70 (1), tr. 2–44, doi:10.1006/jctb.1997.1750
Saaty, Thomas; Kainen, Paul (1986), “The Four Color Problem: Assaults and Conquest”, Science, New York: Dover Publications, 202 (4366): 424, Bibcode:1978Sci...202..424S, doi:10.1126/science.202.4366.424, ISBN 0-486-65092-8
Swart, ER (1980), “The philosophical implications of the four-color problem” (PDF), American Mathematical Monthly, Mathematical Association of America, 87 (9), tr. 697–702, doi:10.2307/2321855, JSTOR 2321855, Bản gốc (PDF) lưu trữ ngày 14 tháng 7 năm 2010, truy cập ngày 17 tháng 7 năm 2012
Thomas, Robin (1998), “An Update on the Four-Color Theorem” (PDF), Notices of the American Mathematical Society, 45 (7), tr. 848–859
Thomas, Robin (1995), The Four Color Theorem
Thomas, Robin, Recent Excluded Minor Theorems for Graphs (PDF), tr. 14, Bản gốc (PDF) lưu trữ ngày 3 tháng 8 năm 2016, truy cập ngày 17 tháng 7 năm 2012
Wilson, Robin (2002), Four Colors Suffice, London: Penguin Books, ISBN 0-691-11533-8

[1] Trần Đan Thư - Dương Anh Đức (2008). Lý Thuyết Đồ Thị. Nhà xuất bản Đại học Quốc gia TP Hồ Chí Minh.

[2] Wilson, Robin (2002). Four Colors Suffice. London: Penguin Books. ISBN 0-691-11533-8.

[1]

[2]