Tô màu đồ thị

Trong Lý thuyết đồ thị, tô màu đồ thị (tiếng Anh: graph coloring) là trường hợp đặc biệt của gán nhãn đồ thị, mà trong đó mỗi đỉnh hay mỗi cạnh hay mỗi miền của đồ thị có thể được gán bởi một màu hay một tập hợp các màu nào đó. Tô màu đồ thị có thể là:

tô màu đỉnh (tiếng Anh: vertex coloring) là gán cho mỗi đỉnh của đồ thị một màu nào đó sao cho không có hai đỉnh nào liền kề lại trùng màu nhau;
tô màu cạnh (tiếng Anh: edge coloring) là gán cho mỗi cạnh của đồ thị một màu nào đó sao cho sao cho không có 2 cạnh nào trùng màu;
tô màu miền (tiếng Anh: face coloring) là gán cho mỗi miền của đồ thị phẳng một màu sao cho không có 2 miền có chung đường biên lại cùng màu.

Sắc số (tiếng Anh: chromatic number) của một đồ thị là số màu ít nhất để tô các đỉnh. Sắc số của đồ thị G được ký hiệu là χ(G).

Số màu cạnh (tiếng Anh: chromatic index) của một đồ thị là số màu ít nhất dùng để tô các cạnh. Số màu cạnh của đồ thị G được ký hiệu là χ'(G).

Số màu cạnh của đồ thị G bất kì bằng sắc số của đồ thị đường L((G)) của đồ thị đó:

χ'(G) = χ(L(G)),

do đó việc nghiên cứu tô màu cạnh của G tương đương với nghiên cứu tô màu đỉnh của L(G).

Các định lý và tính chất

Các giá trị giới hạn của sắc số

Rõ ràng sắc số của một đồ thị sẽ không vượt quá số đỉnh của nó (bậc của đồ thị):

1 \leq χ (G) \leq n .

.

Nếu G có clique kích thước k thì cần ít nhất k màu để tô màu đỉnh cho clique này (xem thêm bài về đồ thị đầy đủ), như vậy sắc số của một đồ thị sẽ không nhỏ hơn chỉ số clique của đồ thị đó:

χ (G) \geq ω (G) .

Nếu đồ thị đơn G có bậc cực đại bằng Δ(G) thì sắc số của nó không vượt quá Δ(G)+1^[1]. Bản mẫu:Hidden begin

Gọi số đỉnh của G là n.

Ta dùng Δ(G)+1 màu để tô n đỉnh của G như sau: xuất phát từ đỉnh thứ nhất đến đỉnh thứ n, tô màu đỉnh đầu tiên bằng 1 màu tùy ý trong Δ(G)+1 màu. Tô màu đỉnh kế tiếp bằng một màu khác với các màu đã tô cho các láng giềng của đỉnh đó. Việc tô màu này luôn thực hiện được, đến lượt 1 đỉnh bất kì, ta luôn có màu để tô cho nó, vì số màu Δ(G)+1 lớn hơn bậc của đỉnh bất kì.

Bản mẫu:Hidden end

Tổng quát hơn là định lý Brook, định lý khẳng định rằng:

Tất cả mọi đồ thị đơn và liên thông G, ngoại trừ đồ thị đầy đủ $K_{n}$ và đồ thị chu trình bậc lẻ $W_{n}$ , đều có sắc số nhỏ hơn hoặc bằng bậc cực đại:

χ (G) \leq

Δ(G).

Nếu đồ thị G có m cạnh thì sắc số của nó thỏa mãn:

χ (G) (χ (G) - 1) \leq 2 m .

Bản mẫu:Hidden begin

Chứng minh quy nạp theo m (m là số tự nhiên) mệnh đề (*) sau:

nếu đồ thị G có không quá m cạnh thì sắc số của nó thỏa mãn:

χ (G) (χ (G) - 1) \leq 2 m .

Với m=0,1, mệnh đề (*) đúng.

Giả sử mệnh đề (*) đúng đến m-1. Xét m.

Gọi

χ

là số tự nhiên lớn nhất thỏa mãn:

χ (χ - 1) \leq 2 m .

Nếu bậc cực đại của G nhỏ hơn

χ

thì như ta đã biết, sắc số của G không vượt quá bậc cực đại của nó cộng với một, nên sẽ không vượt quá

χ

, suy ra luôn điều phải chứng minh.

Nếu bậc cực đại của G lớn hơn hoặc bằng

χ

, suy ra trong G tồn tại đỉnh a có deg(a) lớn hơn hoặc bằng

χ

.

Xóa đỉnh a và các cạnh liên thuộc của nó khỏi G ta nhận được đồ thị mới là G', đồ thị này có số cạnh thỏa mãn:

m^{'} = m - d e g (a) \leq m - χ

Theo giả thiết quy nạp, mệnh đề (*) đúng cho m' nên:

χ (G^{'}) \leq 2 m^{'} \leq 2 (m - χ)

,

Suy ra:

χ (G^{'}) \leq χ - 1

.

Tức là sắc số của G' không thể vượt quá

χ - 1

, từ đó suy ra sắc số của G không vượt quá

χ

. Như vậy mệnh đề cũng đúng với m.

Suy ra mệnh đề (*) đúng với mọi m là số tự nhiên.

Bản mẫu:Hidden end

Một số định lý liên quan của sắc số

Định lý 1

Bất cứ chu trình độ dài lẻ nào cũng đều có sắc số bằng 3

Chứng minh: Giả sử chu trình có độ dài là $2 n + 1$ ta chứng minh theo số $n$

$n = 1$ chu trình gồm 3 đỉnh mà 2 đỉnh bất kì đều kề nhau $\Rightarrow$ dùng đúng 3 màu để tô
$(n) \Rightarrow (n + 1)$ Giả sử $α$ là một chu trình có độ dài $2 (n + 1) + 1 = 2 n + 3$ với các dãy đỉnh là $x_{1}$ , $x_{2}$ ,..., $x_{2 n + 1}$ , $x_{2 n + 2}$ , $x_{2 n + 3}$ .

Nối $x_{1}$ với $x_{2 n + 1}$ ta được một chu trình $α$ 'có độ dài $2 n + 1$ .

Theo giả thuyết quy nạp chu trình $α$ ' có sắc số bằng 3.

Lấy màu của $x_{1}$ tô cho $x_{2 n + 2}$ còn màu của $x_{2 n + 1}$ tô cho $x_{2 n + 3}$ .

Chu trình $α$ được tô màu mà không thêm màu mới vào.

Vậy chu trình $α$ có sắc số bằng 3

Định lý 2

Đồ thị đầy đủ n đỉnh K_n có sắc số bằng n

Một số tiêu chuẩn đơn giản để kiểm tra xem 1 đồ thị có hai sắc số hay không:

Ta có định lý: Giả sử đồ thị G có ít nhất một cạnh. Đồ thị G có hai sắc số khi và chỉ khi G không có chu trình đơn vô hướng độ dài lẻ.

Chứng minh:

Giả sử G là đồ thị có hai sắc số. Theo Định lý 1 thì G không thể có chu trình đơn vô hướng độ dài lẻ.
Ngược lại giả sử G không có chu trình đơn vô hướng độ dài lẻ. Không mất tính tổng quát có thể xem G liên thông.

Chọn 1 đỉnh a nào đó bất kì trong đồ thị

Đặt $m (a) = 0$ (m: số màu)

Với $x$ $\neq$ $a$ Ta ký hiệu $d (x)$ là độ dài đường đi vô hướng ngắn nhất nối $a$ với $x$

Đặt $m (x) = d (x)$ mod 2

Ta sẽ chứng minh m là hàm màu của G

Giả sử $x, y$ kề nhau

Lấy

d (x)

là đường đi vô hướng ngắn nhất nối a với x có độ dài

d (x)

d (y)

là đường đi vô hướng ngắn nhất nối

a

với

y

có độ dài

d (y)

Chu trình đơn $[d (x), (x, y), d (y)]$ có độ dài $d (x) + d (y) + 1$ phải là một số chẵn

Vậy thì $d (x) + d (y)$ là một số lẻ $\Rightarrow$ $d (x), d (y)$ khác nhau tính chẵn lẻ

$\Rightarrow$ $m (x)$ $\neq$ $m (y)$

Hàm tô màu m có hai giá trị, vậy sắc số ≤ 2. G có ít nhất một cạnh nên sắc số của nó bằng 2

Từ định lý trên ta có hệ quả sau: Tất cả các chu trình độ dài chẵn đều có sắc số bằng 2.

Định lý 3

Tập tin:DL3 SSDT.png

Ví dụ định lý 3: Tìm sắc số đồ thị

Phát biểu: Nếu G có chứa 1 đồ thị con đẳng cấu với K_n thì $x (G) \geq n$ .

Chứng minh: Hiển nhiên

Các giá trị giới hạn của số màu cạnh

Định lý 1

Số màu cạnh của đồ thị đơn G bất kì không vượt quá số đỉnh của nó.

Bản mẫu:Hidden begin Xét đồ thị $K'_{n}$ có hai đỉnh bất kì liền kề và $K'_{n}$ có các khuyên. n là số đỉnh của $K'_{n}$ .

Đánh số các đỉnh của $K'_{n}$ là $v_{1}, v_{2}, v_{3}, \dots, v_{n}$ .

Chỉ cần chứng minh $K'_{n}$ có thể tô màu các cạnh bởi n màu thì suy ra đồ thị đơn G bất kì có số đỉnh không vượt quá n đều có thể tô các cạnh bởi n màu.

Ký hiệu các màu là $M_{1}, M_{2}, \dots, M_{n}$ .

Khi đó ta có cách tô màu cho $K'_{n}$ như sau.

Ma trận dưới đây biểu thị cách tô màu, trong đó:

giá trị ở hàng thứ i cột j chính là màu được gán cho cạnh $(v_{i}, v_{j})$ ;

\begin{matrix} v_{1} & v_{2} & v_{3} & v_{4} & \dots & v_{n - 2} & v_{n - 1} & v_{n} \\ v_{1} & M_{1} & M_{2} & M_{3} & M_{4} & \dots & M_{n - 2} & M_{n - 1} & M_{n} \\ v_{2} & M_{2} & M_{3} & M_{4} & M_{5} & \dots & M_{n - 1} & M_{n} & M_{1} \\ v_{3} & M_{3} & M_{4} & M_{5} & M_{6} & \dots & M_{n} & M_{1} & M_{2} \\ v_{4} & M_{4} & M_{5} & M_{6} & M_{7} & \dots & M_{1} & M_{2} & M_{3} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ \\ v_{n} & M_{n} & M_{1} & M_{2} & M_{3} & \dots & M_{n - 3} & M_{n - 2} & M_{n - 1} \end{matrix} .

Bản mẫu:Hidden end

Định lý König khẳng định rằng đối với đồ thị hai phía G, số màu cạnh của nó bằng bậc cực đại của nó: $χ^{'} (G) = Δ (G)$ .

Định lý Vizing khẳng định rằng, nếu đồ thị đơn G có bậc cực đại bằng $Δ (G)$ thì số màu cạnh của nó bằng $Δ (G)$ hoặc $Δ (G) + 1$ .

Đa thức màu

Xem bài đa thức màu.

Sắc số và số màu cạnh của một số đồ thị cơ bản

Khái niệm sắc số liên quan đến bài toán tô màu như sau: Hãy tô màu các đỉnh của đồ thị đã cho, sao cho 2 đỉnh kề phải được tô bằng hai màu khác nhau

Đồ thị hai phía

Các đỉnh của đồ thị $K_{3, 3}$ được tô bằng hai màu xanh và đỏ.

Đồ thị hai phía đầy đủ $K_{m, n}$ có sắc số bằng 2: χ( $K_{3, 3}$ )=2. Mở rộng: một đồ thị hai phía bất kì có sắc số không vượt quá 2.

Ví dụ minh họa là các đỉnh của đồ thị $K_{3, 3}$ có thể được tô bởi hai màu xanh và đỏ.

Đồ thị chu trình

Các đỉnh của đồ thị $C_{5}$ tô được bởi ít nhất 3 màu.
Các đỉnh của đồ thị $C_{6}$ tô được bởi ít nhất 2 màu.
Các cạnh của đồ thị $C_{5}$ tô được bởi ít nhất 3 màu.
Các cạnh của đồ thị $C_{6}$ tô được bởi ít nhất 2 màu.

Đồ thị chu trình $C_{n}$ có sắc số bằng:

χ( $C_{n}$ )= 3, nếu n lẻ.
χ( $C_{n}$ )= 2, nếu n chẵn.

Số màu cạnh:

χ'( $C_{n}$ )= 3, nếu n lẻ.
χ'( $C_{n}$ )= 2, nếu n chẵn.

Đồ thị bánh xe

Các đỉnh của đồ thị $W_{6}$ tô được bởi ít nhất 4 màu.
Các đỉnh của đồ thị $W_{7}$ tô được bởi ít nhất 3 màu.
Các cạnh của đồ thị $W_{7}$ tô được bởi ít nhất 6 màu.

Đồ thị bánh xe $W_{n}$ (n≥4) có sắc số bằng:

χ( $W_{n}$ )= 3, nếu n lẻ.
χ( $W_{n}$ )= 4, nếu n chẵn.

Số màu cạnh (n≥3):

χ'( $W_{n}$ )= n-1.

Đồ thị đầy đủ

Đồ thị đầy đủ 7 đỉnh có sắc số bằng 7.
$K_{5}$ có số màu cạnh bằng 5.
$K_{4}$ có số màu cạnh bằng 3.

Đồ thị đầy đủ $K_{n}$ có sắc số bằng:

χ( $K_{n}$ ) = n.

Số màu cạnh:

χ'( $K_{n}$ ) = n, nếu n lẻ.
χ'( $K_{n}$ ) = n-1, nếu n chẵn.

Bản mẫu:Hidden begin Đánh số các đỉnh của $K_{n}$ là $v_{1}, v_{2}, v_{3}, \dots, v_{n}$ .

Do mỗi đỉnh của $K_{n}$ có bậc bằng n-1, nên số màu cạnh của nó không nhỏ hơn n-1, do đó χ'( $K_{n}$ ) bằng n hoặc n-1.

Chứng minh χ'( $K_{n}$ )=n-1 với n chẵn:

Ta chỉ cần chỉ ra cách tô n-1 màu cho các cạnh của

K_{n}

là được.

Ký hiệu các màu là

M_{1}, M_{2}, \dots, M_{n - 1}

.

Ma trận dưới đây biểu thị cách tô màu, trong đó:

giá trị ở hàng thứ i cột j chính là màu được gán cho cạnh $(v_{i}, v_{j})$ ;
X nghĩa là không được gán màu.

\begin{matrix} v_{1} & v_{2} & v_{3} & v_{4} & \dots & v_{n - 2} & v_{n - 1} & v_{n} \\ v_{1} & X & M_{1} & M_{2} & M_{3} & \dots & M_{n - 3} & M_{n - 2} & M_{n - 1} \\ v_{2} & M_{1} & X & M_{3} & M_{4} & \dots & M_{n - 2} & M_{n - 1} & M_{2} \\ v_{3} & M_{2} & M_{3} & X & M_{5} & \dots & M_{n - 1} & M_{1} & M_{4} \\ v_{4} & M_{3} & M_{4} & M_{5} & X & \dots & M_{1} & M_{2} & M_{6} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ \\ v_{n} & M_{n - 1} & M_{2} & M_{4} & M_{6} & \dots & \dots & \dots & X \end{matrix} .

Ví dụ với n=6, ta có cách tô màu như sau:

\begin{matrix} v_{1} & v_{2} & v_{3} & v_{4} & v_{5} & v_{6} \\ v_{1} & X & M_{1} & M_{2} & M_{3} & M_{4} & M_{5} \\ v_{2} & M_{1} & X & M_{3} & M_{4} & M_{5} & M_{2} \\ v_{3} & M_{2} & M_{3} & X & M_{5} & M_{1} & M_{4} \\ v_{4} & M_{3} & M_{4} & M_{5} & X & M_{2} & M_{1} \\ v_{5} & M_{4} & M_{5} & M_{1} & M_{2} & X & M_{3} \\ v_{6} & M_{5} & M_{2} & M_{4} & M_{1} & M_{3} & X \end{matrix}

Chứng minh χ'( $K_{n}$ )=n với n lẻ:

Trái lại, giả sử tồn tại n lẻ sao cho χ'(

K_{n}

) = n-1.

Xét màu M bất kì, các cạnh tô màu M ký hiệu là

(v_{i_{1}}, v_{j_{1}}), (v_{i_{2}}, v_{j_{2}}), \dots, (v_{i_{k}}, v_{j_{k}})

, trong đó

v_{i_{1}}, v_{j_{1}}, v_{i_{2}}, v_{j_{2}}, \dots, v_{i_{k}}, v_{j_{k}}

là các đầu mút đôi một phân biệt. Như vậy có 2k đỉnh có cạnh liên thuộc tô bởi màu M, mà n lẻ nên tồn tại ít nhất một đỉnh

v_{i}

nào đó không có cạnh liên thuộc tô bởi màu M. Như vậy các cạnh liên thuộc với đỉnh

v_{i}

chỉ được tô bởi không quá n-2 màu, mà

d e g (a) = n - 1

(vô lý).

Bản mẫu:Hidden end

Đồ thị siêu khối

Sắc số của $Q_{2}$ bằng 2.
Sắc số của $Q_{3}$ bằng 2.

Đồ thị siêu khối $Q_{n}$ có sắc số bằng 2, vì bản thân nó là đồ thị phân đôi.

Ứng dụng

Tô màu bản đồ

Trên các bản đồ, các miền khác nhau (miền ở đây được hiểu là các quốc gia trên bản đồ thế giới hay các tỉnh trong một bản đồ hành chính quốc gia) được tô màu sao cho 2 miền có chung biên giới không trùng màu nhau. Đối với bản đồ có nhiều miền, nếu ta dùng một số lượng lớn màu thì sẽ rất khó phân biệt các miền có màu gần giống nhau, vì thế người ta chỉ dùng một số lượng màu nhất định để tô màu bản đồ. Một bài toán được đặt ra là: có thể dùng ít nhất bao nhiêu màu để tô màu một bản đồ sao cho các miền kề nhau không cùng một màu^[2] (tr.593).

Bài toán này dẫn đến định lý bốn màu nổi tiếng và định lý năm màu^[3]. Các dạng bài toán tô màu bản đồ có thể áp dụng Thuật toán tô màu Greedy để tìm ra số màu ít nhất để tô cho các miền trên bản đồ.

Xem thêm

Chú thích

Bản mẫu:Tham khảo

Tham khảo

Bản mẫu:Refbegin

Bản mẫu:Chú thích

Bản mẫu:Chú thích

Bản mẫu:Refend

Liên kết ngoài

Graph Coloring Page Bản mẫu:Webarchive by Joseph Culberson (graph coloring programs)
CoLoRaTiOn by Jim Andrews and Mike Fellows is a graph coloring puzzle
Links to Graph Coloring source codes Bản mẫu:Webarchive
Code for efficiently computing Tutte, Chromatic and Flow Polynomials Bản mẫu:Webarchive by Gary Haggard, David J. Pearce and Gordon Royle
Graph Coloring Web Application Bản mẫu:Webarchive

↑ Vũ Đình Hòa, Đồ thị, Nhà xuất bản Giáo dục
↑ Kenneth H.Rosen, Toán học rời rạc, Nhà xuất bản Khoa Học và Kỹ thuật Hà Nội, 2003
↑ Bản mẫu:Chú thích sách

[VDH-1] Vũ Đình Hòa, Đồ thị, Nhà xuất bản Giáo dục

[KHR-2] Kenneth H.Rosen, Toán học rời rạc, Nhà xuất bản Khoa Học và Kỹ thuật Hà Nội, 2003

[3] Bản mẫu:Chú thích sách

[1]

[2]

[3]

Tô màu đồ thị

Mục lục

Các định lý và tính chất

Các giá trị giới hạn của sắc số

Một số định lý liên quan của sắc số

Định lý 1

Định lý 2

Định lý 3

Các giá trị giới hạn của số màu cạnh

Định lý 1

Đa thức màu

Sắc số và số màu cạnh của một số đồ thị cơ bản

Đồ thị hai phía

Đồ thị chu trình

Đồ thị bánh xe

Đồ thị đầy đủ

Đồ thị siêu khối

Ứng dụng

Tô màu bản đồ

Xem thêm

Chú thích

Tham khảo

Liên kết ngoài

Bảng điều hướng

Tô màu đồ thị

Các định lý và tính chất

Các giá trị giới hạn của sắc số

Một số định lý liên quan của sắc số

Định lý 1

Định lý 2

Định lý 3

Các giá trị giới hạn của số màu cạnh

Định lý 1

Đa thức màu

Sắc số và số màu cạnh của một số đồ thị cơ bản

Đồ thị hai phía

Đồ thị chu trình

Đồ thị bánh xe

Đồ thị đầy đủ

Đồ thị siêu khối

Ứng dụng

Tô màu bản đồ

Xem thêm

Chú thích

Tham khảo

Liên kết ngoài

Bảng điều hướng

Tìm kiếm