Tô màu đồ thị — Số sắc và ứng dụng

Tô màu đồ thị thường có nghĩa là tô màu đỉnh: gán một màu cho mỗi đỉnh sao cho các đỉnh kề nhau không cùng màu. Số màu ít nhất làm được điều đó là số sắc, ký hiệu là $\chi(G)$.

Nếu bạn muốn hiểu nhanh, màu chỉ là các nhãn không xung đột. Hai đỉnh có thể dùng lại cùng một màu chính xác khi không có cạnh nối giữa chúng.

Định nghĩa tô màu đồ thị trong một phút

Trong một cách tô màu đúng, mỗi cạnh nối hai đỉnh có màu khác nhau. Đó là toàn bộ quy tắc.

Vì vậy nếu $\chi(G)=3$, thì đồng thời có hai điều đúng:

• tồn tại một cách tô màu đúng với $3$ màu
• không tồn tại cách tô màu đúng nào chỉ với $2$ màu

Đó là lý do số sắc là một giá trị nhỏ nhất, chứ không chỉ là số màu bạn tình cờ dùng trong một hình vẽ.

Trừ khi có nói khác đi, tô màu đồ thị trong một môn nhập môn thường có nghĩa là tô màu các đỉnh của một đồ thị đơn vô hướng. Tô màu cạnh là một bài toán khác với các quy tắc khác.

Số sắc thực sự đo điều gì

Tên của các màu không quan trọng. Bạn có thể dùng đỏ, xanh dương và xanh lá, hoặc các nhãn $1$, $2$ và $3$.

Điều quan trọng là cách nhóm. Tất cả các đỉnh cùng màu tạo thành một tập không có cạnh nào bên trong, nên nhóm đó không có xung đột.

Góc nhìn này là điều khiến tô màu đồ thị hữu ích trong các bài toán lập lịch và phân bổ. Một màu thường có nghĩa là “những mục này có thể dùng chung một khung thời gian”.

Ví dụ có lời giải: vì sao chu trình 5 đỉnh cần 3 màu

Xét đồ thị chu trình $C_5$ với các cạnh $AB, BC, CD, DE,$ và $EA$.

Hãy thử với $2$ màu trước. Gán cho $A$ màu $1$ và $B$ màu $2$. Khi đó cách tô màu bị ép quanh chu trình:

$$A=1,\quad B=2,\quad C=1,\quad D=2$$

Bây giờ xét $E$. Nó kề với cả $D$ và $A$, nên nó không thể dùng màu $2$ vì $D$, và cũng không thể dùng màu $1$ vì $A$.

Vì vậy $2$ màu không đủ.

Nhưng $3$ màu thì được. Một cách tô màu đúng là

$$A=1,\quad B=2,\quad C=1,\quad D=2,\quad E=3$$

nên

$$\chi(C_5)=3$$

Ví dụ này đáng nhớ vì nó cho thấy một quy luật quan trọng: với đồ thị chu trình, chu trình chẵn có thể tô bằng $2$ màu, còn chu trình lẻ cần $3$ màu.

Cách suy luận về tô màu đồ thị trên các đồ thị nhỏ

Có hai kiểm tra nhanh hữu ích.

Thứ nhất, hãy tìm một xung đột bị ép buộc. Trong ví dụ trên, việc xen kẽ hai màu quanh một chu trình lẻ khiến đỉnh cuối cùng xung đột với cả hai lựa chọn có sẵn.

Thứ hai, hãy tìm một cận dưới. Nếu một đồ thị chứa một tam giác, thì ba đỉnh đó kề nhau từng đôi một, nên chúng đã cần $3$ màu khác nhau. Điều đó không phải lúc nào cũng cho đáp án chính xác, nhưng nó chứng minh số sắc ít nhất là $3$.

Những lỗi thường gặp trong bài toán tô màu đồ thị

Một lỗi phổ biến là xem các đỉnh là kề nhau chỉ vì chúng được vẽ gần nhau. Chỉ có một cạnh thực sự mới tạo ra ràng buộc tô màu.

Một lỗi khác là cho rằng mỗi đỉnh cần một màu riêng. Các đỉnh không kề nhau có thể dùng lại cùng một màu, và các cách tô màu hiệu quả thường tận dụng việc dùng lại màu nhiều nhất có thể.

Sinh viên cũng đôi khi nhầm giữa tô màu đỉnh và tô màu cạnh. Trong trang này, quy tắc áp dụng cho các đỉnh kề nhau, không phải các cạnh kề nhau.

Một lỗi cuối cùng là báo cáo số màu bạn tình cờ đã dùng thay vì số màu nhỏ nhất cần thiết. Dùng $4$ màu trên một đồ thị không chứng minh số sắc của nó là $4$.

Tô màu đồ thị được dùng ở đâu

Một ứng dụng tiêu chuẩn là lập lịch. Giả sử mỗi đỉnh là một kỳ thi, và một cạnh có nghĩa là hai kỳ thi có chung sinh viên nên không thể xếp cùng thời điểm. Khi đó một màu có thể biểu diễn một khung thời gian.

Trong mô hình đó, số sắc cho biết số khung thời gian ít nhất có thể. Nếu $\chi(G)=4$, thì không tồn tại lịch hợp lệ nào chỉ với $3$ khung.

Ý tưởng tương tự cũng xuất hiện trong tô màu bản đồ, nơi các vùng lân cận phải khác nhau, và trong thiết kế trình biên dịch, nơi các biến cần dùng đồng thời không thể chia sẻ cùng một thanh ghi.

Hãy thử một bài toán tô màu đồ thị tương tự

Vẽ một đồ thị với các đỉnh $P,Q,R,S,T$ và các cạnh $PQ, QR, RS, ST, TP,$ và $PR$.

Hãy bắt đầu bằng cách tìm một tam giác để có cận dưới. Sau đó thử tô màu đồ thị với ít màu nhất có thể và kiểm tra xem có cặp đỉnh kề nhau nào trùng màu không. Nếu muốn đi tiếp, hãy thử phiên bản của riêng bạn trên một đồ thị lớn hơn và xem liệu bạn có thể chứng minh cách tô màu của mình là tối thiểu, chứ không chỉ hợp lệ.