+). Xây dựng bài toán:
Những bài toán liên quan đến tô màu bản đồ đã dẫn đến rất nhiều kết quả trong lý thuyết đồ thị . Khi một bản đồ đợc tô màu, hai miền có chung biên giới đợc tô bằng hai màu tuỳ ý miễn là khác nhau. Để đảm bảo chắc chắn hai miền kề nhau không bao giờ có màu trùng nhau, chúng ta tô mỗi miền bằng một màu khác nhau. Tuy nhiên điều đó là không thực tế . Nếu bản
đồ có nhiều miền thì sẽ rất khó phân biệt những màu gần giống nhau . Do vậy ngời ta chỉ dùng một số màu cần thiết để tô bản đồ. Một bài toán đợc
đặt ra là: xác định số màu tối thiểu cần có để tô một bản đồ sao cho các miền kề nhau không cùng một màu. Vì vậy, từ thực tế đó ta có bài toán tô
màu đồ thị.
*.Định nghĩa 1: Tô màu một đơn đồ thị là sự gán màu cho các đỉnh của nó sao cho không có hai đỉnh liền kề đợc gán cùng một màu.
Một đồ thị có thể đợc tô màu bằng cách gán các màu khác nhau cho mỗi
đỉnh của nó. Tuy vậy, với hầu hết các đồ thị, ta có thể tô màu chúng với số màu ít hơn số đỉnh.
* Định nghĩa 2: Số màu của một đồ thị là số tối thiểu các màu cần thiết để tô
màu đồ thị này.
Chúng ta thấy rằng câu hỏi về số màu lớn nhất của các đồ thị phẳng chính là câu hỏi về số cực đại các màu cần thiết để tô các bản đồ phẳng sao cho không có hai miền kề nhau đợc gán cùng một màu. Bài toán này đã đợc nghiên cứu từ hơn 100 năm nay. Câu trả lời chính là một trong các định lí nổi tiếng nhất trong toán học.
Định lí : Định lí bốn màu. Số màu của một dồ thị là không lớn hơn bốn.
Định lí bốn màu: Đầu tiên đợc ra nh một phỏng đoán vào năm 1850. Và cuối cùng đã đợc hai nhà toán học Mỹ là Kenneth Appel và Wolfgang Haken chứng minh năm 1976. Trớc năm 1976 cũng đã có nhiều chứng minh sai, mà thông thờng rất khó tìm thấy chỗ sai, đã dợc công bố. Hơn thế nữa đã có
nhiều cố gắng một cách vô ích để tìm phản ví dụ bằng cách cố vẽ bản đồ cần hơn bốn màu để tô nó.
Có lẽ một chứng minh sai nổi tiếng nhất trong toán học là chứng minh sai bài toán bốn màu đợc công bố năm 1879 bởi luật s, nhà toán học nghiệp d Luân - đôn tên là Alfred Kempe. Các nhà toán học chấp nhận cách chứng minh của ông ta cho tới năm 1980, khi Percy Heawood phát hiện ra sai lầm trong chứng của Kempe. Tuy nhiên, cách lập luận của Kempe lại là cơ sở cho chứng minh của Appel và Haken. Chứng minh của họ dựa trên sự phân tích từng trờng hợp một cách cẩn thận nhờ máy tính. Họ đã chỉ ra rằng nếu bài toán bốn màu là sai thì sẽ có một phản ví dụ thuộc một trong gần 2000 loại khác nhau và đã chỉ ra không có loại nào dẫn tới phản ví dụ cả. Trong chứng minh của mình họ đã dùng hơn 1000 giờ máy. Cách chứng minh này
đã gây ra nhiều cuộc tranh cãi vì máy tính đã đóng vai trò quan trọng biết bao. Chẳng hạn, liệu có thể có sai lầm trong chơng trình và điều đó dẫn đến kết quả sai không? lý luận của họ có thật sự là một chứng minh hay không, nếu nó phụ thuộc vào thông tin ra từ một máy tính không đáng tin cậy?
Bài toán bốn màu áp dụng chỉ cho các đồ thị phẳng. Các đồ thị không phẳng có thể có số màu lớn tuỳ ý nh sẽ đợc chỉ ra trong ví dụ1.
Cần phải làm hai điều khi chứng minh số màu của đồ thị là n. Trớc tiên chúng ta phải chứng tỏ rằng đồ thị có thể đợc tô màu bằng n màu. Điều này có thể thực hiện bằng cách tô màu đồ thị đó. Sau đó chúng ta phải chứng tỏ rằng không thể tô màu đồ thị với số màu ít hơn.
Ví dụ1: Tìm số màu của đồ thị Kn. a §á
e N©u
d Vàng
c Lôc b Lam
H×nh 1
Giải: Có thể xây dựng cách tô màu đồ thị Kn với n màu khác nhau. Liệu có cách tô màu nào dùng ít màu hơn không? câu trả lời là không. Không có hai đỉnh nào có thể gán cùng màu vì mọi cặp đỉnh của đồ thị này đều liên kề.
Vì thế số màu của Kn = n. (Nhớ lại rằng Kn là không phẳng nếu n ≥5, vì thế kết quả này không mâu thuẫn với định lí bốn màu). Cách tô màu K5 bằng 5 màu đợc thể hiện trên hình.
Ví dụ2: Tìm số màu của đồ thị phân đôi, đầy đủ Km,n trong đó m và n là các số nguyên dơng.
Giải: Số màu cần thiết phụ thuộc vào m và n. Tuy nhiên, ta chỉ cần 2 màu.
Tô tập m đỉnh bằng một màu, và tập n đỉnh bằng màu khác. Vì mỗi cạnh chỉ nối các đỉnh từ tập m đỉnh tới đỉnh thuộc tập n đỉnh nên không có 2 đỉnh liền kề nào cùng màu. Hình 2 thể hiện cách tô màu đồ thị k3,4 .
H×nh 2
a §á b §á c §á
d Lam e Lam f Lam g Lam
Mọi đơn đồ thị phân đôi liên thông có số màu băng 2 hoặc 1, vì lí lẽ nh trong ví dụ 2 áp dụng đợc cho mọi đồ thị nh thế. Ngợc lại, mọi đồ thị có số màu bằng 2 đều là đồ thị phân đôi.