Thuật toán tô màu đồ thị

BÀI TOÁN TÔ MÀU ĐỒ THỊ
(graph coloring)

1. Giới thiệu:
Vấn đề liên quan đến tô màu các miền trên bản đồ , ví dụ bản đồ các vùng trên thế giới đã dẫn đến nhiều kết quả trong lí thuyết đồ thị. Khi tô màu bản đồ , ta thường tô 2 miền có chung đường biên giới bằng 2 màu khác nhau. Để đảm bảo điều này , ta có thể sử dụng màu sắc riêng cho mỗi miền. Tuy nhiên , cách làm này là không hiệu quả , và nếu bản đồ có quá nhiều miền, sẽ rất khó để phân biệt giữa các miền có màu sắc gần giống nhau. Do đó , ta nên sử dụng số màu ít nhất có thể được. Nó dẫn đến bài toán xác định số màu tối thiểu cần sử dụng để tô màu các miền bản đồ sao cho các miền lân cận luôn khác màu nhau.
VD:Bản đồ H1a có thể tô được bằng 4 màu , nhưng không thể tô bằng 3 màu -> Số màu tối thiểu phải là 4.
Bản đồ H1b có thể tô bằng 3 màu ,nhưng 2 màu là không thể ->Số màu tối thiểu là 3.


H1: 2 bản đồ ví dụ.

Mỗi bản đồ trên mặt phẳng có thể biểu diễn bằng đồ thị: Mỗi miền biểu diễn bằng 1 đỉnh; 2 đỉnh sẽ được nối với nhau khi 2 miền tương ứng có chung đường biên giới. Hai miền chỉ tiếp xúc nhau tại 1 điểm coi như không kề nhau. Đồ thị này được gọi là đồ thị kép của bản đồ. Từ phương pháp xây dựng đồ thị kép của 1 bản đồ , dễ thấy mỗi bản đồ phẳng sẽ tương ứng với 1 đồ thị kép phẳng .
H2 thể hiện đồ thị phẳng tương ứng của các bản đồ trong H1.


H2: Đồ thị kép của các bản đồ trong H1.
2. Các khái niệm cơ bản:
Định nghĩa 1:
Phép tô màu của một đồ thị đơn là một quy tắc tô mỗi đỉnh đồ thị một màu cụ thể sao cho không có 2 đỉnh kề nhau nào được tô cùng màu.
1 đồ thị có thể tô màu bằng các màu khác nhau cho mỗi đỉnh. Tuy nhiên, trong phần lớn các đồ thị , ta có thể tô bằng số màu ít hơn số đỉnh. Vậy số màu tối thiểu cần sử dụng là bao nhiêu?
Định nghĩa 2:
Số màu của một đồ thị G ( kí hiệu c(G))là số màu tối thiểu cần sử dụng để tô màu đồ thị này.
Chú ý rằng số màu của 1 đồ thị phẳng chính là số màu tối thiểu cần sử dụng để tô màu các miền bản đồ phẳng sao cho không có 2 miền nào kề nhau và được tô cùng màu. Bài toán này đã được nghiên cứu hơn 100 năm,dẫn đến một trong các định lí nổi tiếng nhất của toán học:
Định lí 4 màu:
Số màu của 1 đồ thị phẳng không lớn hơn 4.
Giả thuyết 4 màu được đề ra từ những năm 1850. Nó cuối cùng đã được chứng minh bởi 2 nhà toán học Mĩ là Kenneth Appel và Wolfgang Haken năm 1976. Trước đó , nhiều người đã đề ra các cách chứng minh khác nhau của bài toán, nhưng tất cả đều sai và thường mắc phải những lỗi khó phát hiện. Bên cạnh đó là những cố gắng vô ích trong việc phủ định giả thuyết bằng cách chỉ ra những bản đồ đòi hỏi nhiều hơn 4 màu.
Có lẽ , sai lầm nổi tiếng nhất là chứng minh được xuất bản năm 1879 bởi một luật sư ở Luân Đôn và một nhà toán học nghiệp dư , Afred Kempe. Các nhà toán học công nhận chứng minh này là đúng cho đến năm 1890, khi Percy Heawood tìm ra lỗi. Tuy nhiên , hướng lí luận của Kempe lại trở thành cơ sở cho thành công của Appel và Haken sau này. Chứng minh của họ dựa trên phân tích cẩn thận từng trường hợp trên máy tính. Họ chỉ ra rằng nếu giả thuyết 4 màu sai, họ phải tìm ra được phản ví dụ của 1 trong khoảng 2000 trường hợp khác nhau. Họ đã sử dụng máy tính chạy trong 1000 tiếng để thực hiện chứng minh của mình. Chứng minh này đã gây ra nhiều tranh cãi khi sử dụng máy tính để thực hiện các thao tác chính. Ví dụ, chương trình máy tính có thể mắc lỗi dẫn đến kết quả sai. Liệu lí lẽ của họ có thật sự là 1 chứng minh khi phụ thuộc vào những kết quả không đáng tin cậy của máy tính?
Định lí 4 màu chỉ ứng dụng trên đồ thị phẳng. Đồ thị không phẳng có thể có số màu lớn hơn 4(Xem ví dụ 2).
2 điều kiện được yêu cầu để xác định số màu của 1 đồ thị là n: Đầu tiên ,phải chứng minh đồ thị có thể tô bằng n màu.Việc này có thể thực hiện bằng cách xây dựng, như tô màu. Thứ