Bảng chú giải

Chọn một trong những từ khóa bên trái

Đồ thị và Mạng lướiTô màu bản đồ

Thời gian đọc: ~15 min

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ỳ

Number of colours: 0

Nam Phi

Number of colours: 0

Đức

Number of colours: 0

Anh

Number of colours: 0

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 , và các vùng kết nối với nhau bởi một cạ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 Francis Guthrie phải tô màu các vùng của nước Anh. Ông quan sát được rằng hầu như chỉ cần 4 màu là đủ với bất kỳ bản đồ nào Ông thử, nhưng Ông tìm được minh chứng rằng quy tắc 4 màu này áp dụng được cho tất cả các bản đồ. Điều này thực ra là một bài toán cực kỳ khó, được biết đến với cái tên định lý bốn màu.

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 Wolfgang HakenKenneth Appel sử dụng máy tính để giải bài toán này. Họ gom vô vàn kiểu bản đồ khác nhau thành 1936 kiểu bản đồ cụ thể, mỗi bản đồ được kiểm tra bởi máy tính, tổng cộng hết tất cả 1000 giờ đồng hồ.

Đị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.

Archie