BÀI TOÁN BẢN ĐỒ BỐN MÀU

I – Lịch sử

Năm 1852, khi Francis Guthrie thử tô màu bản đồ nước Anh, ông nhận thấy rằng chỉ cần 4 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. 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. Tháng 10 năm đó, De Morgan viết thư cho William Hamilton để thảo luận về nó.

Augustus De Morgan (1806 – 1871) William Hamilton (1788 – 1856)

Năm 1878, tại Hội toán học London, nhà toán học Arthur Carley lần đầu tiên đưa vấn đề này ra với công chúng. Sau đó, nhiều cách chứng minh cho bài toán đã được đưa ra, lần lượt của Alfred Kempe (1879) và Peter Guthrie Tait $latex (1880). Nhưng sau đó, cả hai cách chứng minh trên đều bị phủ định.

Năm 1976, định lý chính thức đượ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!). Phương pháp sử dụng máy vi tính cho việc chứng minh vấn đề này được phát triển trong thập niên 60 của thế kỉ trước bởi Heinrich Heesch, nhà toán học người Đức. 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.

II – Định lý

Đố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 dùng tối đa 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.

III – Ý nghĩa

Thực sự mà nói, định lý này không áp dụng được quá nhiều trong thực tế. Để đảm bảo tính mỹ thuật, không có bản đồ nào được dùng trong đời sống mà chỉ được tô bằng 4 màu cả. 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 (ví dụ như hai quần đảo Trường Sa và Hoàng Sa thuộc chủ quyền Việt Nam ta, do đó nhất thiết phải tô cùng màu với phần đất liền Việt Nam). Ý nghĩa lớn nhất của định lý này là sự kết hợp giữa trí tuệ con người và sức mạnh máy tính.

TƯ LIỆU THAM KHẢO

• https://vi.wikipedia.org/wiki/%C4%90%E1%BB%8Bnh_l%C3%BD_b%E1%BB%91n_m%C3%A0u

Chia sẻ:

• Tweet

Thích Đang tải...