Bài Giảng Toán - Sắc Số Của Đồ Thị

4.4. SẮC SỐ CỦA ĐỒ THỊ Bài toán tô màu đồ thịHãy tô màu các đỉnh của một đồ thị đã cho, sao cho haiđỉnh kề nhau được tô bằng hai màu khác nhau. Ta nói rằng, đồ thị G tô được bằng k màu nếu tồn tại hàm m : V  {0, 1, 2, ... , k-1} sao cho, nếu hai đỉnh x và y kề nhau thì m(x)  m(y).Đồ thị G tô màu được  G không có đỉnh nút.14.4. SẮC SỐ CỦA ĐỒ THỊ (tiếp) Định nghĩa 4.5: Sắc số của một đồ thị chính là số màu ít nhất dùng để tô các đỉnh của đồ thị đó. Ta ký hiệu số s là sắc số của đồ thị G. Hiển nhiên s  n , số màu không vượt quá số đỉnh của đồ thị.24.4. SẮC SỐ CỦA ĐỒ THỊ (tiếp)Ví dụ 4.3: Tô màu đồ thị sau đây:Đồ thị trên có sắc số bằng 3. 012012Hình 4.6. Tô màu các đỉnh đồ thị34.4. SẮC SỐ CỦA ĐỒ THỊ (tiếp)	Nhận xét: - Mỗi cách tô màu m cho đồ thị G sẽ ứng với một cách phân hoạch tập đỉnh V thành các tập ổn định trong không giao nhau, mỗi tập ứng với một màu. 	- Ngược lại, mỗi cách phân hoạch tập đỉnh V thành các tập ổn định trong không giao nhau sẽ cho ta một cách tô màu.4SẮC SỐ CỦA CHU TRÌNH 	Định lý 4.6: Mọi chu trình độ dài lẻ luôn có sắc số bằng 3.	Chứng minh: Giả sử chu trình có độ dài là 2n+1. 	Ta chứng minh bằng quy nạp theo số n. 	- n = 1: Chu trình gồm 3 đỉnh, mà hai đỉnh bất kỳ đều kề nhau. Vậy phải dùng đúng 3 màu để tô các đỉnh.	- (n)  (n+1) : Giả sử  là một chu trình có độ dài 2(n+1)+1 = 2n+3 với dãy các đỉnh là: [x1 , x2 , ... , x2n+1 , x2n+2 , x2n+3].5SẮC SỐ CỦA CHU TRÌNH (tiếp)Nối x1 với x2n+1 ta được một chu trình ’ có độ dài 2n+1. Theo giả thiết quy nạp, chu trình ’ có sắc số bằng 3. Lấy màu của x1 tô cho x2n+2, còn màu của x2n+1 tô cho x2n+3. Chu trình  đã được tô màu mà khôngphải thêm màu mới. Vậy  có sắc số bằng 3. 6SẮC SỐ CỦA ĐỒ THỊ ĐẦY ĐỦ 	Định lý 4.7: Đồ thị đầy đủ n đỉnh Kn có sắc số bằng n. 74.5. ĐỒ THỊ 2 SẮC Định lý 4.8 (Konig) 	Giả sử đồ thị G có ít nhất một cạnh. Đồ thị G là hai sắc 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ị 2 sắc. Theo Định lý 4.6 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 là liên thông. 84.5. ĐỒ THỊ 2 SẮC (tiếp)Chọn một đỉnh a nào đó trong đồ thị. Đặt m(a) = 0. Với x  a , 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 chứng minh m là hàm màu của G. axyDym(a) = 0DxHình 4.7. Cách xây dựng hàm tô màu94.5. ĐỒ THỊ 2 SẮC (tiếp)Giả sử x, y kề nhau. Lấy Dx là đường đi vô hướng ngắn nhất nối a với x có độ dài d(x), Dy 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 [Dx , (x, y) , Dy] có độ dài d(x) + d(y) +1 phải là một số chẵn. 	104.5. ĐỒ THỊ 2 SẮC (tiếp)Vậy thì d(x) + d(y) là một số lẻ, có nghĩa là d(x) và d(y) khác nhau tính chẵn lẻ. Do vậy: m(x)  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. 114.5. ĐỒ THỊ 2 SẮC (tiếp)Hệ quả 4.9: Tất cả các chu trình độ dài chẵn đều có sắc số bằng 2.124.6. SẮC SỐ VÀ HÀM GRUNDYĐịnh lý 4.10: Đồ thị vô hướng G có sắc số bằng s  G có hàm Grundy g  s-1.Chứng minh:	a) Nếu đồ thị G có hàm Grundy g  s-1 thì chỉ việc chọn g làm hàm tô màu.134.6. SẮC SỐ VÀ HÀM GRUNDY (tiếp)	b) Ngược lại, giả sử đồ thị G có sắc số là s, nghĩa là tồn tại hàm tô màu m với tập màu là {0, 1, ... , s-1}. 	Đồ thị G không có đỉnh nút. Hàm tô màu m sẽ phân hoạch tập đỉnh V thành các tập ổn định trong không rỗng, không giao nhau: 	Ci = { x  m(x) = i } , i = 0, 1,  , s-1.144.6. SẮC SỐ VÀ HÀM GRUNDY (tiếp)Mỗi tập ổn định trong của đồ thị vô hướng luôn có thể bổ sung các đỉnh để thành cực đại, và đó cũng là nhâncủa đồ thị. Xây dựng hai dãy tập con các đỉnh: V0, V1, V2,  và B0, B1, B2,  lần lượt như sau:	V0 = V,	Vì C0 là tập ổn định trong của V0 nên có thể bổ sungđể thành tập B0 là nhân của V0. Hiển nhiên B0  V0, V1 = V0 \ B0154.6. SẮC SỐ VÀ HÀM GRUNDY (tiếp)Vì C1 \ B0 là tập ổn định trong của V1 nên có thể bổ sung để thành tập B1 là nhân của V1. Ta có 	 C1 \ B0  B1  V1	. . . . . .	Vi+1 = Vi \ Bi	Vì Ci+1 \ (B0  ...  Bi) là tập ổn định trong của Vi+1 nên có thể bổ sung để thành tập Bi+1 là nhân của Vi+1. Ta có Ci+1 \ (B0  ...  Bi)  Bi+1  Vi+1164.6. SẮC SỐ VÀ HÀM GRUNDY (tiếp)Quá trình tiếp tục cho đến Vk-1.Ck-1 \ (B0  ...  Bk-2) là tập ổn định trong của Vk-1. Sau khi bổ sung thành nhân Bk-1 ta có: 	Ck-1 \ (B0  .. Bk-2)  Bk-1  Vk-1.Hơn nữa, Ck-1 = (C k-1  (B0  ...  Bk-2 ))  (Ck-1 \ (B0  ...  Bk-2 ))  (B0  ...  Bk-2)  Bk-1 = B0  ...  Bk-1	174.6. SẮC SỐ VÀ HÀM GRUNDY (tiếp)	V = C0  ...  Ck-1  B0  ...  Bk-1	Vậy đến nhân Bk-1 thì ta đã vét hết các đỉnh của V. 	Ta được dãy: B0, B1, ... , Bk-1 , trong đó Bi là nhân của Vi.	Xây dựng hàm Grundy cho đồ thị G:	Với x  Bi đặt g(x) = i 	Hàm g chính là một hàm Grundy của đồ thị G. 1) Nếu x, y kề nhau thì không thể cùng nằm trong một tập Bi vì Bi là nhân, cho nên g(x)  g(y). 184.6. SẮC SỐ VÀ HÀM GRUNDY (tiếp)2) Giả sử có u < g(x) = j. Khi đó x  Bu. 	Vì Bu là tập ổn định ngoài của Vu nên tồn tại y  Bu sao cho y  F(x). Suy ra g(y) = u. C0B0. . .. . .Ciy. . .. . . xCjBj. . .Ck-1Bk-1V0V1BiViVjVk-1Hình 4.8. Cách xây dựng dãy các nhân194.6. SẮC SỐ VÀ HÀM GRUNDY (tiếp)Hệ quả 4.11: Mọi đồ thị vô hướng không có đỉnh nút đều có hàm Grundy và giá trị cực đại của các hàm này phải bằng nhau và bằng sắc số của đồ thị trừ đi 1.204.7. THUẬT TOÁN TÔ MÀU ĐỒ THỊ Thuật toán 4.12	1. Liệt kê các đỉnh x1 , x2 , ... , xn của đồ thị theo thứ tự giảm dần của bậc: r(x1)  r(x2)  ...  r(xn) để làm giảm các phép kiểm tra ở bước dưới.	2. Tô màu 0 cho đỉnh x1 cùng các đỉnh không kề với x1 và không kề với các đỉnh đã tô màu 0.	214.7. THUẬT TOÁN TÔ MÀU ĐỒ THỊ (tiếp)3. Lặp lại thủ tục tô màu i+1 giống như thủ tục tô màu i cho đến khi tô màu hết các đỉnh của đồ thị.	Số màu đã dùng chính là sắc số của đồ thị.224.7. THUẬT TOÁN TÔ MÀU ĐỒ THỊ (tiếp)Ví dụ 4.7: Tô màu đồ thị sau đây.1012021201Hình 4.9. Tô màu một đồ thị234.8. SẮC SỐ CỦA ĐỒ THỊ TỔNG	Định lý 4.13: Giả sử đồ thị G tô được bằng s+1 màu, đồ thị H tô được bằng t+1 màu. Khi đó đồ thị tổng G + H tô được bằng d+1 màu, trong đó:	d = max { s'  t'  s'  s , t‘  t }244.8. SẮC SỐ CỦA ĐỒ THỊ TỔNG (tiếp)	Theo Định lý 4.10 đồ thị G có hàm Grundy g  s , đồ thị H có hàm Grundy h  t. 	Ta có z((x,y)) = g(x)  h(y) là hàm Grundy của đồ thị tổng G + H. 	Giá trị lớn nhất của hàm z là d. Từ đó suy ra kết quả. 254.8. SẮC SỐ CỦA ĐỒ THỊ TỔNG (tiếp)	Ví dụ: Đồ thị G tô được bằng 7 màu, đồ thị H tô được bằng 5 màu.	Đồ thị tổng G + H tô được bằng 8 màu.264.9. TÍNH CHẤT CỦA SẮC SỐ Định lý 4.14: Nếu đồ thị G có n đỉnh và sắc số s thì số ổn định trong u của đồ thị G sẽ không nhỏ hơn n/s.Chứng minh: Lập các tập đỉnh cùng màu: 	Ci = { xx tô màu i }, i = 0, ... , s-1 là các tập ổn định trong và |Ci |  u.	n =  |Ci |  s.u . Suy ra: u  n/s. 274.9. TÍNH CHẤT CỦA SẮC SỐĐịnh lý 4.15: Nếu bậc lớn nhất của các đỉnh trong đồ thị G là r thì sắc số của đồ thị G  r+1.Chứng minh: 	Chứng minh quy nạp theo số đỉnh n.- n = 1 : Bậc của đỉnh bằng 0 và sắc số bằng 1.- n = 2 : Bậc của các đỉnh bằng 0 thì sắc số bằng 1còn bậc của các đỉnh bằng 1 thì sắc số bằng 2.284.9. TÍNH CHẤT CỦA SẮC SỐ (tiếp)- (n)  (n+1) : Giả sử đồ thị G có n đỉnh, các đỉnh có bậc cao nhất là r. Theo giả thiết quy nạp: s(G)  r+1.	Đồ thị G’ có n+1 đỉnh được xem là đồ thị G có n đỉnh và thêm một đỉnh mới a và một số cạnh kề nó. Khi đó: s(G)  s(G')  s(G) +1.	Giả sử bậc cao nhất của các đỉnh trong G’ là r'. Hiển nhiên: r  r'.	Nếu s(G)  r thì: s(G’)  r+1  r'+1294.9. TÍNH CHẤT CỦA SẮC SỐ (tiếp)Nếu s(G) = r+1 thì:Trường hợp: r < r' ta có: s(G’)  r + 1 + 1  r‘ + 1aG’G. . .Hình 4.10. Cách chọn màu cho đỉnh mới304.9. TÍNH CHẤT CỦA SẮC SỐ (tiếp)Trường hợp: r = r' thì đỉnh mới a được nối vớikhông quá r đỉnh, do vậy chỉ cần giữ nguyên cách tô màu của G thì các đỉnh kề với a được tôkhông qúa r màu và vẫn còn thừa một màu dànhcho đỉnh a, suy ra: s(G’) = s(G)  r +1 = r' +1 31