English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtĐồ thị và Mạng lướiTô màu bản đồ
Chúng ta đã dùng lý thuyết đồ thị với một số bản đồ nhất định. Nếu chúng ta zoom hình bản đồ ra, mỗi con đường và cây cầu sẽ biến mất và thay vào đó là hình ảnh biên giới của cả nước.
Khi tô màu một bản đồ - hay một bản vẽ gồm nhiều vùng khác nhau– các vùng liền kề nhau không được tô cùng một màu. Và chúng ta cũng muốn sử dụng càng ít màu càng tốt.
Một số “bản đồ” đơn giản, như bàn cờ vua, chỉ cần hai màu (đen và trắng), nhưng hầu hết các bản đồ phức tạp hơn cần nhiều màu hơn.
Khi tô màu bản đồ của các tiểu bang của Mỹ, hiển nhiên 50 màu chắc chắn là đủ, nhưng không cần thiết. Hãy thử tô màu bản đồ dưới đây sử dụng càng ít màu càng tốt:
Hoa Kỳ
Nam Phi
Đức
Anh
Tất cả các bản đồ ở trên đều có thể được tô với chỉ 4 màu khác nhau, và cũng không khó để tưởng tượng được rằng các bản đồ phức tạp khác có thể cần nhiều màu hơn. Thực tế một số bản đồ cần ít nhất bốn màu, khi bản đồ có 4 vùng kết nối với nhau.
Tương tự như trước, chúng ta có thể chuyển đổi bản đồ với vùng miền khác nhau thành một đồ thị phẳng: với mỗi vùng trở thành
Bây giờ chúng ta muốn tô màu các đỉnh của đồ thị, và hai đỉnh phải có màu khác nhau nếu chúng được kết nối bằng một cạnh.
Năm 1852, một sinh viên thực vật học
Trong suốt 100 năm sau đó, rất nhiều nhà toán học tìm cách công bố các chứng minh khác nhau cho định lý này, để rồi sau đó phát hiện ra nhiều lỗi. Trong số đó có những cách chứng minh có vẻ hết sức thuyết phục khiến phải mất hơn 10 năm mới phát hiện ra lỗi của nó.
Trong một thời gian dài, nhiều nhà toán học không tìm được cách chứng minh chỉ cần dùng 4 màu là đủ hoặc đưa ra các bản đồ cần dùng hơn 4 màu.
Không có gì tiến triển về bài toán 4 màu cho đến năm 1976, khi
Định lý bốn màu là định lý toán học nổi tiếng đầu tiên dược chứng minh sử dụng máy tính, một phương pháp ngày càng thông dụng và bớt tranh cãi hơn từ đó. Máy tính càng nhanh với thuật toán càng hiệu quả giúp giải bài toán nhanh hơn và ngày nay bài toán bốn màu có thể được giải chỉ trong vài giờ.
Dấu bưu điện của Khoa toán học, trường Đại học
Illinois Urbana-Champaign, nơi Haken và Appel đã làm việc.
Định lý bốn màu chỉ áp dụng được cho các bản đồ ở mặt phẳng và toàn bộ các vùng trên bản đồ chỉ là một vùng duy nhất.
Tuy nhiên, các nhà toán học cũng nghiên cứu cả các bản đồ của các đế chế, khi các đế chế này có thể có nhiều vùng không kết nối với nhau, và cả những bản đồ thuộc hệ khác, như hình xuyến (hình bánh doughnut). Trong trường hợp này có lẽ bạn cần hơn 4 màu và việc chứng minh trở nên khó khăn hơn nhiều.
This map on a torus requires seven colours.