Luận văn Luật tương hỗ trong tô màu đồ thị

f, hg} là tập cạnh của đồ thị G. Chỳng ta thấy rằng đồ thị G cú 8 đỉnh và cú 9 cạnh. Đỉnh e khụng thuộc bất kỡ cạnh nào và những đỉnh như vậy được gọi là đỉnh cụ lập của đồ thị G. Trong tập cạnh cú cạnh đặc biệt hh, mà chỳng ta gọi là khuyờn của đồ thị. a b c d e f g h Hỡnh 1.2: Đồ thị G 81.1.2. Cỏc thuật ngữ cơ bản a) Kề và liờn thuộc Giả sử u và v là hai đỉnh của đồ thị G = (V,E) và e = (u, v) là cạnh của đồ thị, khi đú ta núi: + u và v kề nhau và e liờn thuộc với u và v. + Cỏc đỉnh u và v gọi là cỏc đỉnh đầu của cạnh e. +Cạnh e cũng được gọi là cạnh nối cỏc đỉnh u và v. u v e b) Bậc của đỉnh Bậc của đỉnh v trong đồ thị G = (V,E) là số cỏc cạnh liờn thuộc với nú, riờng khuyờn tại một đỉnh được tớnh hai lần cho bậc của nú. Ký hiệu deg(v). Đỉnh treo là đỉnh cú duy nhất một cạnh liờn thuộc với nú v hay deg(v) = 1. Đỉnh cụ lập là đỉnh khụng cú cạnh liờn thuộc với nú v hay deg(v) = 0.. 1.1.3. Đường đi, chu trỡnh Định nghĩa 1.2 Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đú n là số nguyờn dương, trờn đồ thị vụ hướng G = (V,E) là dóy x0 := u, x1, . . . , xn−1, xn := v, trong đú (xi, xi+1) ∈ E, với mọi i = 0, 1, 2, . . . , n−1. Đường đi núi trờn cũn cú thể biểu diễn dưới dạng dóy cỏc cạnh: (x0, x1), (x1, x2), . . . , (xn−1, xn). Đỉnh u gọi là đỉnh đầu, cũn đỉnh v gọi là đỉnh cuối của đường đi. Đường 9đi cú đỉnh đầu trựng với đỉnh cuối (tức là u = v) được gọi là chu trỡnh. Đường đi hay chu trỡnh được gọi là đơn nếu như khụng cú cạnh nào bị lặp lại. Từ bõy giờ trở đi nếu khụng núi gỡ chỳng ta chỉ xột cỏc đường đi hay chu trỡnh đơn. Vớ dụ 1.2 Xột đồ thị G như trong Vớ dụ 1.1. Một số đường đi từ đỉnh a đến đỉnh f là a, b, h, f và a, b, h, g, f . Chỳng ta thấy cú nhiều đường đi từ a đến f và độ dài là khỏc nhau. Ngay cả khi cú cho trước độ dài và và cỏc đỉnh thỡ cú nhiều đường đi khỏc nhau. Vớ dụ hai đường đi cú độ dài 4 đi từ đỉnh d đến đỉnh f là d, a, b, h, f và d, c, b, h, f . Đường đi ngắn nhất từ đỉnh d đến đỉnh f là 3 với đường đi cụ thể là d, b, h, f . Mặt khỏc chỳng ta thấy rằng khụng cú đường đi từ a đến e. Chỳng ta thấy rằng a, b, c, d, a và a, b, d, a là cỏc chu trỡnh duy nhất mà xuất phỏt từ a. Tập cỏc chu trỡnh trong đồ thị G là a, b, c, d; a, b, d; b, c, d và f, h, g. Như vậy đồ thị G cú ba chu trỡnh độ dài 3 và một chu trỡnh độ dài 4. Xem hỡnh 1.3 một chu trỡnh độ dài 4 được tụ bằng màu đỏ và một chu trỡnh độ dài 3 được tụ bằng màu xanh. a b c d e f g h Hỡnh 1.3: Đồ thị G 1.1.4. Tớnh liờn thụng Định nghĩa 1.3 Một đồ thị được gọi là liờn thụng nếu cú đường đi giữa mọi cặp đỉnh phõn biệt của đồ thị. 10 1.1.5. Đồ thị đầy đủ Định nghĩa 1.4 Đồ thị đầy đủ n đỉnh, ký hiệu là Kn, là đơn đồ thị vụ hướng mà hai đỉnh phõn biệt bất kỳ của nú luụn liền kề. Như vậy, Kn cú n(n−1) 2 cạnh và mỗi đỉnh của Kn cú bậc là n− 1. Vớ dụ 1.3 Hỡnh 1.4 là một biểu diễn đồ họa của đồ thị G = (V,E) trong đú • V = {a, b, c, d} là tập đỉnh của đồ thị G. • E = {ab, bc, cd, da, ac, bd} là tập cạnh của đồ thị G. Chỳng ta thấy rằng G là một đơn đồ thị cú 4 đỉnh và 6 cạnh. Mặt khỏc hai đỉnh bất kỡ của G luụn liền kề nờn G được gọi là đồ thị đầy đủ K4 và mỗi đỉnh của nú cú bậc đều bằng 3. a b c d Hỡnh 1.4: Đồ thị đầy đủ K4 1.1.6. Đồ thị vũng Định nghĩa 1.5 Đơn đồ thị n đỉnh v1, v2, . . . , vn (n ≥ 3) và n cạnh (v1, v2), (v2, v3), . . . , (vn−1, vn), (vn, v1) được gọi là đồ thị vũng, ký hiệu là Cn. Như vậy, mỗi đỉnh của Cn cú bậc là 2. Vớ dụ 1.4 Hỡnh 1.5 là một biểu diễn đồ họa của đồ thị G mà chỳng ta gọi là đồ thị tam giỏc. 11 • V = {a, b, c} là tập đỉnh của đồ thị G. • E = {ab, bc, ca} là tập cạnh của đồ thị G. Chỳng ta thấy rằng G là một đơn đồ thị cú 3 đỉnh và 3 cạnh. Đồ thị tam giỏc khụng cú đỉnh cụ lập và khụng cú khuyờn. Hai đỉnh bất kỡ của đồ thị G luụn liền kề, và bậc của mọi đỉnh trong đồ thị tam giỏc là 2. Vậy đồ thị tam giỏc là đồ thị thị vũng và cũng là đồ đầy đủ. a b c Hỡnh 1.5: Đồ thị tam giỏc Vớ dụ 1.5 Hỡnh 1.6 là một biểu diễn đồ họa của đồ thị C4 mà chỳng ta gọi là đồ thị hỡnh vuụng. • V = {u, v, s, t} là tập đỉnh của đồ thị G. • E = {uv, vs, st, tu} là tập cạnh của đồ thị G. Chỳng ta thấy rằng G là một đơn đồ thị cú 4 đỉnh là u, v, s, t và 4 cạnh là (u, v), (v, s), (s, t), (t, u). Do đú G là đồ thị vũng và bậc của mọi đỉnh trong đồ thị hỡnh vuụng đều bằng 2. Vỡ đồ thị G cú hai cặp đỉnh u và s khụng liền kề, v và t cũng khụng liền kề nờn G là đồ thị khụng đầy đủ. u v s t Hỡnh 1.6: Đồ thị hỡnh vuụng (hay đồ thị C4) 12 1.1.7. Đồ thị cõy Định nghĩa 1.6 Cõy là một đồ thị vụ hướng liờn thụng và khụng chứa chu trỡnh. Rừng là hợp của nhiều cõy. Vớ dụ 1.6 Rừng sau cú ba cõy a b c d e f g h i j k lm n o p q r Hỡnh 1.7: Rừng cõy Chỳng ta thấy rằng ba đồ thị trong hỡnh 1.7 là ba đồ thị vụ hướng liờn thụng và khụng cú chu trỡnh nờn chỳng là cỏc cõy. 1.1.8. Đồ thị Petersen Định nghĩa 1.7 Đồ thị Petersen là đồ thị vụ hướng với 10 đỉnh và 15 cạnh. Vớ dụ 1.7 Hỡnh 1.8 là một biểu diễn đồ họa của đồ thị Petersen nú được vẽ như một ngũ giỏc bao ngoài và hỡnh ngụi sao bờn trong với số đỉnh là 10 và số cạnh là 15. 1.1.9. Đồ thị hai phần đầy đủ Định nghĩa 1.8 Đồ thị G = (V,E) sao cho V = V1 ∪ V2, V1 ∩ V2 = ∅, V1 6= ∅, V2 6= ∅ và mỗi cạnh của G được nối một đỉnh trong V1 và một đỉnh 13 B Hỡnh 1.8: Đồ thị Petersen trong V2 được gọi là đồ thị hai phần. Nếu đồ thị hai phần G = (V1∪V2, E) sao cho với mọi v1 ∈ V1, v2 ∈ V2, (v1, v2) ∈ E thỡ G được gọi là đồ thị hai phần đầy đủ. Nếu |V1| = m, |V2| = n thỡ đồ thị G được ký hiệu là Km,n. Như vậy, Km,n cú mn cạnh, cỏc đỉnh của V1 cú bậc n và cỏc đỉnh của V2 cú bậc m. Vớ dụ 1.8 Hỡnh 1.9 là biểu diễn đồ họa của đồ thị G = (V,E) trong đú • V = {a, b, c, d, e, f} là tập đỉnh của đồ thị G. • E = {ad, ae, af, bd, be, bf, cd, ce, cf} là tập cạnh của đồ thị G. Ta cú tập cỏc đỉnh V của đồ thị G được chia thành hai tập rời nhau là V1 = {a, b, c} và V2 = {d, e, f} thỏa món mỗi cạnh của đồ thị G được tạo bởi một đỉnh trong V1 với một đỉnh trong V2 và với mọi u ∈ V1, v ∈ V2, (u, v) ∈ E, mặt khỏc |V1| = 3, |V2| = 3 nờn nú được gọi là đồ thị hai phần đầy đủ K3,3 a e d f b c Hỡnh 1.9: Đồ thị hai phần đầy đủ K3,3 14 1.2. Tụ màu đồ thị Chỳng ta bắt đầu mục này với khỏi niệm tụ màu đồ thị. 1.2.1. Tụ màu thực sự Định nghĩa 1.9 n-màu của một đồ thị G = (V,E) là một ỏnh xạ c : V → [n] := {1, 2, . . . , n}. n-màu c được gọi là thực sự nếu khụng cú hai đỉnh trờn cựng một cạnh được gỏn cựng màu, tức là c (u) 6= c (v) với mọi uv ∈ E. Vớ dụ 1.9 Cho đồ thị tam giỏc G như trong Vớ dụ 1.4. Với n = 2, cỏc cỏch tụ màu của đồ thị G lần lượt là 1. c1(a) = 1, c1(b) = 1, c1(c) = 1 2. c2(a) = 1, c2(b) = 1, c2(c) = 2 3. c3(a) = 1, c3(b) = 2, c3(c) = 1 4. c4(a) = 1, c4(b) = 2, c4(c) = 2 5. c5(a) = 2, c5(b) = 1, c5(c) = 1 6. c6(a) = 2, c6(b) = 1, c6(c) = 2 7. c7(a) = 2, c7(b) = 2, c7(c) = 1 8. c8(a) = 2, c8(b) = 2, c8(c) = 2 Vậy với n = 2 thỡ đồ thị G cú 8 cỏch tụ màu nhưng khụng cú cỏch tụ màu thực sự nào. Với n = 3, cỏc cỏch tụ màu thực của đồ thị G lần lượt là 1. c1(a) = 1, c1(b) = 2, c1(c) = 3 2. c2(a) = 1, c2(b) = 3, c2(c) = 2 15 3. c3(a) = 2, c3(b) = 1, c3(c) = 3 4. c4(a) = 2, c4(b) = 3, c4(c) = 1 5. c5(a) = 3, c5(b) = 1, c5(c) = 2 6. c6(a) = 3, c6(b) = 2, c6(c) = 1 Vậy với n = 3 thỡ đồ thị G cú 6 cỏch tụ màu thực sự. Hỡnh 1.10 là một biểu diễn đồ họa của cỏch tụ màu c1 của đồ thị G a = 1 b = 2 c = 3 Hỡnh 1.10: Tụ màu thực sự Vớ dụ 1.10 Cho đồ thị hỡnh vuụng C4 như hỡnh vẽ. Với n = 2, cỏc cỏch tụ màu thực sự của đồ thị G lần lượt là 1. c1(u) = 1, c1(v) = 2, c1(s) = 1, c1(t) = 2 2. c2(u) = 2, c2(v) = 1, c2(s) = 2, c2(t) = 1 Với n=3, cỏc cỏch tụ màu thực sự của đồ thị hỡnh vuụng là 1. c1(u) = 1, c1(v) = 2, c1(s) = 1, c1(t) = 2 2. c2(u) = 2, c2(v) = 1, c2(s) = 2, c2(t) = 1 3. c3(u) = 1, c3(v) = 3, c3(s) = 1, c3(t) = 3 4. c4(u) = 3, c4(v) = 1, c4(s) = 3, c4(t) = 1 5. c5(u) = 2, c5(v) = 3, c5(s) = 2, c5(t) = 3 6. c6(u) = 3, c6(v) = 2, c6(s) = 3, c6(t) = 2 7. c7(u) = 1, c7(v) = 2, c7(s) = 3, c7(t) = 2 16 8. c8(u) = 1, c8(v) = 3, c8(s) = 2, c8(t) = 3 9. c9(u) = 2, c9(v) = 1, c9(s) = 3, c9(t) = 1 10. c10(u) = 2, c10(v) = 3, c10(s) = 1, c10(t) = 3 11. c11(u) = 3, c11(v) = 1, c11(s) = 2, c11(t) = 1 12. c12(u) = 3, c12(v) = 2, c12(s) = 1, c12(t) = 2 u = 1 v = 2 s = 1t = 2 Hỡnh 1.11: Một cỏch tụ màu thực sự của đồ thị hỡnh vuụng Thuật ngữ "màu" xuất phỏt từ việc giải thớch ý nghĩa tự nhiờn của c(v), vỡ một trong n màu cú thể được tụ cho đỉnh v. Một cỏch tụ màu thực sự là mỗi đỉnh cú màu khỏc màu của cỏc đỉnh kề với nú. Đõy là dấu hiệu đầu tiờn tại sao cỏc đồ thị đơn thường thỏa món: sự tồn tại và số lượng n-màu khụng ảnh hưởng bởi cỏc cạnh song song, và ở đú khụng cú tụ màu thực sự với sự xuất hiện của khuyờn. Phần lớn sự nổi tiếng của bài toỏn tụ màu đồ thị xuất phỏt từ cõu hỏi được đặt ra vào năm 1850 bởi Francis Guthric và được trả lời sau 124 năm. Để dưa ra cõu hỏi trong điều kiện hiện tại, chỳng ta cần định nghĩa sau. 1.2.2. Đồ thị phẳng Định nghĩa 1.10 Đồ thị G được gọi là đồ thị phẳng nếu G được vẽ trong mặt phẳng sao cho cỏc cạnh khụng cắt nhau ngoại trừ tại cỏc đỉnh. 17 Đồ thị G trong Vớ dụ 1.1 là một đồ thị phẳng vỡ hỡnh 1.2 cho chỳng ta một cỏch vẽ đồ thị G trong mặt phẳng và cỏc cạnh khụng cắt nhau ngoại trừ tại cỏc đỉnh. Trong khi đú đồ thị K3,3 là đồ thị khụng phẳng vỡ một số cạnh trong đồ thị K3,3 cắt nhau. Dưới đõy là một phỏt biểu nổi tiếng của Guthrie’s, bõy giờ là định lớ. 1.2.3. Định lớ bốn màu Định lý 1.1 Mỗi đồ thị phẳng được tụ thực sự bởi bốn màu. Định lớ Bốn màu đầu tiờn được đưa ra như một phỏng đoỏn vào năm 1850 bởi một sinh viờn người Anh tờn là Francis Guthric và cuối cựng đó được hai nhà toỏn học Mỹ là Kenneth Appel và Wolfgang Haken chứng minh vào năm 1976 với sự trợ giỳp của mỏy tớnh. Cú nhiều nỗ lực trong chứng minh định lớ bốn màu trước chứng minh đầu tiờn của Kenneth Appel và Wolfgang Haken. Dưới đõy là cỏch tiếp cận đặc biệt thỳ vị (nhưng chưa thành cụng) để chứng minh Định lớ bốn màu được đưa ra bởi George Birkhoff. Định nghĩa 1.11 Giỏ trị của đa thức màu của đồ thị G tại n bằng số cỏch tụ màu thực sự cỏc đỉnh đồ thị G với n màu. Kớ hiệu là XG (n) := |{c : V → [n], n−màu thực sự}|. Cỏc quan sỏt của George Birkhoff và Hassler Whitney cho rằng XG(n) là hạn chế đến Z > 0 của hàm đặc biệt. 1.2.4. Đồ thị xúa, co rỳt Định nghĩa 1.12 Cho e ∈ E việc xúa e trong đồ thị G nhận được kết quả là G\e := (V,E \ {e}). 18 Đồ thị co rỳt G/e là đồ thị nhận được bằng cỏch đồng nhất hai đỉnh thuộc e và bỏ đi e. Giả sử e = (u, v) với u 6= v. Cho f là hàm sao cho f(x) = x với đỉnh x ∈ V \ {u, v} và f(u) = f(v) = w. Khi đú co rỳt G/e là đồ thị với tập đỉnh là V ′ := (V \{u, v})∪{w} và tập cạnh E ′ thỏa món điều kiện sau. Với mọi x ∈ V , f(x) ∈ V ′ là kề với cạnh e′ ∈ E ′ nếu và chỉ nếu cạnh e tương ứng là kề với x trong G. Vớ dụ 1.11 Cho đồ thị G=(V, E) và một cạnh e = uv ∈ E như hỡnh vẽ. Khi đú việc xúa e và co rỳt e trong đồ thị G kết quả nhận được là đồ thị G\e và đồ thị G/e như hỡnh 1.12 v u1 e u Hỡnh 1.12: Đồ thị G/e và đồ thị G\e 1.2.5. Mệnh đề Mệnh đề 1.2 Nếu G = (V,E) là đồ thị khụng khuyờn thỡ XG(n) là đa thức bậc |V | với hệ số nguyờn. Nếu G cú khuyờn thỡ XG(n) = 0. Bằng lạm dụng nhỏ kớ hiệu, chỳng tụi đồng nhất thức XG(n) với đa thức này và gọi nú là đa thức màu của G. Tuy nhiờn chỳng tụi nhấn mạnh rằng cho đến nay, duy nhất giỏ trị của XG(n) là số nguyờn dương thể hiện mối quan hệ với G. Một chứng minh rất thỳ vị của Mệnh đề 1.2 theo đỳng nghĩa của nú là thụng qua quan hệ xúa-co rỳt. 19 Bổ đề 1.1 Nếu G = (V,E) là đồ thị khụng khuyờn thỡ XG(n) = XG\e(n)−XG/e(n) Chứng minh. Giả sử e = uv. Chỳng ta thấy rằng màu thực sự c của G\e với c(u) 6= c(v) là màu thực sự c của G, và ngược lại, màu thực sự c của G là màu thực sự c của G\e với c(u) 6= c(v). Mặt khỏc màu thực sự c của G\e với c(u) = c(v) là màu thực sự c của G/e, và ngược lại màu thực sự c của G\e là màu thực sự c của G/e với c(u) = c(v). Từ đú suy ra số cỏch tụ màu thực sự của G bằng số cỏch tụ màu thực của G\e trừ đi số cỏch tụ màu thực của G\e mà c(u) = c(v). Mặt khỏc chỳng ta cú thể đếm tất cả cỏc màu thực sự của G\e mà gỏn cựng màu tới u và v. Đõy chớnh là màu thực sự của G/e. Vậy ta cú XG(n) = XG\e(n)−XG/e(n).  Chỳng ta sẽ sử dụng đồ thị C4 như trong Vớ dụ 1.5 để minh họa lại cho chứng minh của Bổ đề trờn với trường hợp n = 2 và n = 3. Với n = 2, giả sử hai màu là xanh và đỏ. Khi đú ta thấy cỏch tụ màu của đồ thị G như trong hỡnh 1.13 cho ta cỏch tụ màu tương ứng của đồ thị G\e. Ta thấy rằng đồ thị G và đồ thị xúa cạnh G\e cú hai cỏch tụ màu. Trong khi đú đồ thị co rỳt G/e khụng cú cỏch tụ màu nào. Do đú XG(n) = 2 = 2− 0 = XG\e(n)−XG/e(n). w s t u v st e u v ts Hỡnh 1.13: Đồ thị G, đồ thị xúa cạnh G\e và đồ thị co rỳt G/e. 20 Với n = 3, hỡnh 1.14 cho ta thấy một cỏch tụ màu thực sự của đồ thị G sẽ cho ta một cỏch tụ màu của đồ thị xúa cạnh G\e và một cỏch tụ màu thực sự của đồ thị G/e cho ta cỏch tụ màu thực sự đồ thị G\e. Đồ thị G cú 18 cỏch tụ màu thực sự trong khi đú đồ thị G\e cú 24 cỏch tụ màu thực sự và đồ thị G/e cú 6 cỏch tụ màu thực sự. Vậy XG(n) = 18 = 24− 6 = XG\e(n)−XG/e(n). w s t u s t vu v st e u v ts Hỡnh 1.14: Đồ thị G, đồ thị co rỳt G/e và đồ thị xúa cạnh G\e Chứng minh của Mệnh đề 1.2. Nếu G cú khuyờn thỡ khụng tồn tại tụ màu thực sự. Do đú XG(n) = 0. Nếu G khụng cú khuyờn, ta chứng minh bằng phương phỏp quy nạp trờn |E|. Với |E| = 0 thỡ việc tụ màu thực sự là tựy ý. Do đú XG(n) = n|V |. e1 u v e Hỡnh 1.15 Với |E| = 1, tức là đồ thị cú duy nhất một cạnh. Giả sử cạnh đú là uv như trong hỡnh 1.15. Khi đú ta cú n cỏch tụ màu đỉnh u. Sau đú đỉnh v chỉ cú thể tụ bằng n − 1 màu cũn lại khỏc u. Trong khi cỏc đỉnh cũn lại vấn cú n cỏch tụ màu. Do đú XG(n) = n d−1(n− 1), trong đú d = |V |. Với |E| = k, giả thiết quy nạp rằng XG(n) là đa thức bậc |V | với hệ 21 số nguyờn. Khi đú ta cần chứng minh với |E| = k + 1 thỡ XG(n) cũng là đa thức bậc |V | với hệ số nguyờn. Thật vậy, theo Bổ đề 1.1, ta cú XG(n) = XG\e(n)−XG/e(n) và theo giả thiết quy nạp thỡ XG\e(n) là đa thức với bậc bằng số đỉnh của đồ thị G\e và XG/e(n) là đa thức với bậc bằng số đỉnh của đồ thị G/e nờn XG(n) là đa thức bậc |V | với hệ số nguyờn. Ở đõy chỳng ta lưu ý số đỉnh của đồ thị G\e là |V | và số đỉnh của đồ thị G/e là |V | − 1.  1.2.6. Cỏc vớ dụ Vớ dụ 1.12 Cho đồ thị tam giỏc G = (V,E) như trong Vớ du 1.4. Tỡm đa thức màu XG(n). e e1 Hỡnh 1.16 Giải. Ta cú đa thức màu của G là XG (n) := |{c : V → [n], n−màu thực sự}|. e2e1 Hỡnh 1.17: Đồ thị G\e và G/e 22 Theo Bổ đề 1.1, ta cú. XG(n) = XG\e(n)−XG/e(n) = XG1\e1(n)−XG1/e1(n)− (XG2\e2(n)−XG2/e2(n)) với G1 = G\e,G2 = G/e. Vỡ đồ thị G2\e2 là đồ thị cú duy nhất một cạnh. Giả sử cạnh đú là uv. Khi đú ta cú n cỏch tụ màu đỉnh u. Sau đú đỉnh v chỉ cú thể tụ bằng n− 1 màu cũn lại khỏc u. Do đú XG2\e2(n) = n(n− 1). Cũn đồ thị G2/e2 cú khuyờn nờn XG2/e2(n) = 0 Vỡ đồ thịG1/e1 cũng là đồ thị cú duy nhất một cạnh. Do đúXG1/e1(n) = n(n− 1). Vỡ đồ thị G1\e1 là đồ thị cú duy nhất một cạnh và cú duy nhất một đỉnh cụ lập. Do đú XG1\e1G(n) = n 2(n− 1). Vậy XG(n) = XG1\e1(n)−XG1/e1(n)− (XG2\e2(n)−XG2/e2(n)) = n2(n− 1)− n(n− 1)− [n(n− 1)− 0] = n(n− 1)(n− 2). Vớ dụ 1.13 Cho đồ thị C4 như hỡnh vẽ. Tỡm đa thức màu XG(n). e1 e2 e3 e4 Hỡnh 1.18: Đồ thị C4 Giải. Theo Bổ đề 1.1, ta cú XG(n) = XG\e1(n)−XG/e1(n). Đặt G1 = G\e1 và G2 = G/e1, theo bổ đề ta cú XG1(n) = XG1\e2(n)−XG1/e2(n). XG2(n) = XG2\e2(n)−XG2/e2(n). 23 Đặt G3 = G1\e2 và G4 = G1/e2, theo bổ đề ta cú XG1(n) = XG3\e3(n)−XG3/e3(n)−XG4\e3(n) +XG4/e3(n) = n3(n− 1)− n2(n− 1)− n2(n− 1) + n(n− 1) = n4 − 3n3 + 3n2 − n. Đặt G5 = G2\e2 và G6 = G2/e2, theo Bổ đề 1.1 ta cú XG2(n) = XG5\e3(n)−XG5/e3(n)−XG6\e3(n) +XG6/e3(n) = n2(n− 1)− n(n− 1)− n(n− 1) + 0 = n3 − 3n2 + 2n. Vậy XG(n) = n 4− 3n3+3n2− n− (n3+3n2− 2n) = n4− 4n3+6n2− 3n. Vớ dụ 1.14 Chứng minh rằng a) Đồ thị đường đi n đỉnh được tụ bởi k-màu cú đa thức màu là XG(k) = k(k − 1)n−1 (1.1) b) Đồ thị đầy đủ n đỉnh được tụ bởi k-màu cú đa thức màu là XG(k) = k(k − 1)(k − 2)...(k − (n− 1)) (1.2) c) Đồ thị cõy n đỉnh được tụ bởi k-màu cú đa thức màu là XG(k) = k(k − 1)n−1 (1.3) d) Đồ thị vũng n đỉnh được tụ bởi k-màu cú đa thức màu là XG(k) = (k − 1)n + (−1)n(k − 1) (1.4) Chứng minh. a) Gọi đồ thị đường đi n đỉnh là G=(V,E) trong đú • V = {u1, u2, ..., un} là tập đỉnh của đồ thị G. • E = {u1u2, u2u3, ..., un−1un} là tập cạnh của đồ thị G. 24 Ta chứng minh bằng phương phỏp quy nạp trờn |V |. Với |V | = 1 ta cú XG(k) = k. Vậy (1.1) đỳng. Giả sử (1.1) đỳng với n = t tức là XG(k) = k(k − 1)t−1. Ta cần chứng minh (1.1) đỳng với n = t+ 1 tức là XG(k) = k(k − 1)t. Thật vậy, theo Bổ đề 1.1 ta cú XG(k) = XG\e(k)−XG/e(k). với e = u1u2. Khi đú đồ thị G\e gồm 1 đỉnh độc lập cú k cỏch tụ màu phần cũn lại là đồ thị đường đi t đỉnh cú k(k− 1)t−1 cỏch tụ màu (theo giả thiết quy nạp). Do đú XG\e(k) = kk(k− 1)t−1. Lại cú G/e là đồ thị đường đi t đỉnh nờn theo giả thiết quy nạp XG/e(k) = k(k − 1)t−1. Vậy XG(k) = kk(k − 1)t−1 − k(k − 1)t−1 = k(k − 1)t  b) Ta chứng minh bằng phương phỏp quy nạp trờn |V |. Với |V | = 3 ta cú XG(k) = k(k − 1)(k − 2). Vậy (1.2) đỳng. Giả sử (1.2) đỳng với n = t tức là XG(k) = k(k−1)(k−2)...(k−(t−1)). Ta cần chứng minh (1.2) đỳng với n = t+1 tức là XG(k) = k(k−1)(k− 2)...(k − t). Thật vậy, theo Bổ đề 1.1 ta cú XG(k) = XG\e(k)−XG/e(k). Ta thấy rằng G\e là đồ thị khụng đầy đủ nhưng nếu bỏ một đỉnh liờn thuộc cạnh e và cỏc cạnh liờn thuộc đỉnh đú ta sẽ được đồ thị đầy đủ t đỉnh cú k(k − 1)(k − 2)...(k − (t− 1)) bởi giả thiết quy nạp. Mặt khỏc đỉnh liờn thuộc cạnh e mà ta vừa bỏ cú bậc t− 1 nờn đỉnh đú cú k-(t-1) cỏch tụ màu. Do đú XG\e(k) = k(k−1)(k−2)...(k−(t−1))(k−(t−1)). Lại cú G/e là đồ thị đầy đủ t đỉnh nờn theo giả thiết quy nạp XG/e(k) = k(k − 1)(k − 2)...(k − (t− 1)). Vậy XG(k) = k(k − 1)...(k − (t− 1))(k − (t− 1))− k(k − 1)...(k − (t− 1)) = k(k − 1)(k − 2)...(k − (t− 1))(k − t+ 1− 1) = k(k − 1)(k − 2)...(k − t). 25  c) Ta chứng minh bằng phương phỏp quy nạp trờn |V |. Với |V | = 1 ta cú XG(k) = k. Vậy (1.3) đỳng. Giả sử (1.3) đỳng với n = t tức là XG(k) = k(k − 1)t−1. Ta cần chứng minh (1.3) đỳng với n = t+ 1 tức là XG(k) = k(k − 1)t. Thật vậy, theo Bổ đề 1.1 ta cú XG(k) = XG\e(k)−XG/e(k). với e là cạnh liờn thuộc đỉnh treo. Khi đú đồ thị G\e gồm 1 đỉnh độc lập cú k cỏch tụ màu phần cũn lại là đồ thị cõy t đỉnh cú k(k−1)t−1 cỏch tụ màu (theo giả thiết quy nạp). Do đú XG\e(k) = kk(k−1)t−1. Lại cú G/e là đồ thị cõy t đỉnh nờn theo giả thiết quy nạp XG/e(k) = k(k − 1)t−1. Vậy XG(k) = kk(k − 1)t−1 − k(k − 1)t−1 = k(k − 1)t d) Ta chứng minh bằng phương phỏp quy nạp trờn |V |. Với |V | = 3 ta cú G là đồ thị tam giỏc nờn theo vớ dụ trờn thỡ XG(k) = k(k − 1)(k − 2) = (k − 1)3 + (−1)3(k − 1). Vậy (1.4) đỳng. Giả sử (1.4) đỳng với n = t tức là XG(k) = (k − 1)t + (−1)t(k − 1). Ta cần chứng minh (1.4) đỳng với n = t+1 tức là XG(k) = (k−1)t+1+ (−1)t+1(k − 1). Thật vậy, theo Bổ đề 1.1 ta cú XG(k) = XG\e(k)−XG/e(k). Khi đú đồ thị G\e là đồ thị đường đi t+1 đỉnh nờn theo chứng minh trờn XG\e(k) = k(k− 1)t. Lại cú G/e là đồ thị vũng t đỉnh nờn theo giả thiết quy nạp XG/e(k) = (k − 1)t + (−1)t(k − 1). Vậy XG(k) = k(k − 1)t − (k − 1)t − (−1)t(k − 1) = (k − 1)t(k − 1)− (−1)t(k − 1) = (k − 1)t+1 + (−1)t+1(k − 1).  Vậy ta cú bảng đa thức màu 26 Đồ thị tam giỏc K3 k(k − 1)(k − 2) Đồ thị đường đi Pn k(k − 1)n−1 Đồ thị đầy đủ Kn k(k − 1)(k − 2)...(k − (n− 1)) Cõy n đỉnh k(k − 1)n−1 Đồ thị vũng Cn (k − 1)n + (−1)n(k − 1) Đồ thị Petersen k(k−1)(k−2)(k7−12k6+67k5−230k4+529k3− 814k2 + 775k − 352) 1.2.7. Hệ quả Hệ quả 1.1 Giả sử G là đồ thị khụng khuyờn với d ≥ 1 đỉnh và XG(n) = cdn d + cd−1nd−1 + . . .+ c1n+ c0 là đa thức màu của G. Khi đú ta cú a) hệ số đầu cd = 1. b) hệ số cuối c0 = 0. c) (−1)dXG(−n) > 0, với mọi số nguyờn n ≥ 1. Chứng minh. Chỳng ta chứng minh cỏc mệnh đề a), b) và c) bằng quy nạp trờn số cạnh của G. Với |E| = 0 thỡ ta cú XG(n) = nd nờn cd = 1 và c0 = 0. Hơn nữa ta cú (−1)dXG(−n) = (−1)d(−n)d = nd > 0 với mọi n ≥ 1. Với |E| = 1 thỡ ta cú XG(n) = nd − nd−1 nờn cd = 1 và c0 = 0.Hơn nữa ta cú (−1)dXG(−n) = (−1)d((−n)d − (−n)d−1) = nd + nd−1 > 0 với mọi n ≥ 1. Giả thiết quy nạp rằng kết luận của Hệ quả đỳng với |E| = k và ta sẽ chứng minh kết luận đú đỳng với |E| = k+1. Thật vậy theo Bổ đề 1.1, 27 ta cú XG(n) = XG\e(n)−XG/e(n). Vỡ đồ thị G\e cú k cạnh và số đỉnh bằng d cũn đồ thị G/e cú k cạnh và số đỉnh bằng d− 1 nờn cd(G) = cd(G\e) = 1. Mặt khỏc ta cũng cú c0(G) = c0(G\e)− c0(G/e) = 0. Hơn nữa ta cú (−1)dXG(−n) = (−1)dXG\e(−n) + (−1)d−1XG/e(−n). Vỡ đồ thị G\e cú k cạnh và số đỉnh bằng d, theo giả thiết quy nạp ta cú (−1)dXG\e(−n) > 0. Vỡ đồ thị G/e cú k cạnh và số đỉnh bằng d− 1 theo giả thiết quy nạp ta cú (−1)d−1XG/e(−n) > 0. Vậy (−1)dXG(−n) > 0 với mọi n ≥ 1.  28 Chương 2 Luật tương hỗ của đa thức màu Đặc biệt tớnh chất cuối cựng của Hệ quả 1.1 trong chương 1 sẽ dẫn tới cõu hỏi Việc đỏnh giỏ (−1)dXG(−n) cú ý nghĩa tổ hợp gỡ? Cõu hỏi này đó được hỏi đầu tiờn và cõu trả lời bởi Richard Stanley vào năm 1973. Để tỏi lập lại cõu trả lời đú, chỳng ta cần khỏi niệm định hướng trờn đồ thị. Chỳng ta kớ hiệu cỏc đỉnh của G lần lượt là v1, v2, . . . , vd. Chỳng ta định nghĩa một sự định hướng trờn G thụng qua một tập con ρ ⊆ E. 2.1. Định hướng của đồ thị Định nghĩa 2.1 Cho tập ρ ⊆ E. Một định hướng của G thụng qua tập ρ là định hướng thỏa món điều kiện sau: với mọi cạnh e = vivj ∈ E với i < j chỳng ta cú vi e← vj nếu e ∈ ρ và vi e→ vj nếu e /∈ ρ Khi đú chỳng ta kớ hiệu đồ thị G cựng với định hướng trờn là ρG và đụi khi viết ρG = (V,E, ρ). 29 Núi cỏch khỏc, chỳng ta cú thể coi G như quy tắc định hướng bởi cỏc cạnh đi từ chỉ số nhỏ đến chỉ số lớn và ρ chỉ cỏc cạnh trờn đú sự định hướng là ngược lại xem Vớ dụ sau. Vớ dụ 2.1 Cho G là đồ thị với • tập đỉnh là V = {v1, v2, v3, v4} • tập cạnh là E = {v1v2, v2v3, v3v4, v4v1, v4v2}. Cho tập con cỏc cạnh là ρ = {v1v4, v2v3, v2v4}. Khi đú tập ρ sẽ xỏc định định hướng trờn đồ thị G. Cụ thể v1 e→ v2 vỡ v1v2 /∈ ρ v2 e← v3 vỡ v2v3 ∈ ρ v3 e→ v4 vỡ v3v4 /∈ ρ v2 e← v4 vỡ v2v4 ∈ ρ v1 e← v4 vỡ v1v4 ∈ ρ Với định hướng như trờn ta nhận được đồ thị định hướng ρG như trong Hỡnh 2.1. v u1 e u v1 v2 v3v4 Hỡnh 2.1: Đồ thị định hướng sinh bởi ρ = {v1v4, v2v3, v2v4} 2.2. Đường định hướng Định nghĩa 2.2 Đường định hướng là một đường vi0 → vi1 → . . .→ vis 30 trong đồ thị ρG sao cho vik 6= vil với 0 ≤ k < l ≤ s, và nú được gọi là chu trỡnh tuần hoàn nếu vi0 = vis. Một định hướng ρ trờn G là khụng tuần hoàn nếu khụng cú chu trỡnh tuần hoàn trong ρG. Vớ dụ 2.2 Cho G là đồ thị với • tập đỉnh là V = {v1, v2, v3, v4} • tập cạnh là E = {v1v2, v2v3, v3v4, v1v4, v2v4}. Cho tập con cỏc cạnh là ρ = {v1v4, v2v3, v2v4}, theo Vớ dụ 2.1 ta cú đồ thị định hướng như trong Hỡnh 2.1 . Đồ thị này cú cỏc đường định hướng là v3 → v4 → v1 → v2 v3 → v4 → v2 v3 → v2 Vỡ khụng tồn tại chu trỡnh định hướng trong pG nờn p được gọi là định hướng khụng tuần hoàn trờn G. Mối quan hệ giữa tụ màu thực sự và định hướng khụng tuần hoàn được mụ tả như sau: cho màu thực sự c, chỳng ta định nghĩa một định hướng trờn G thụng qua tụ màu c là định hướng trờn G thụng qua tập ρ = { vivj ∈ E | nếu i c (vj) } . Cụ thể, cạnh đi từ chỉ số thấp i đến chỉ số cao j là cú hướng dọc theo gradient màu của nú c (vj)− c (vi) . Chỳng ta gọi sự định hướng ρ này cảm sinh bởi c. Vớ dụ 2.3 Cho 4-màu thực sự c như hỡnh vẽ 2.3. Mệnh đề Mệnh đề 2.1 Giả sử c : V −→ [n] là màu thực sự và ρ là định hướng cảm sinh của c trờn G = (V,E). Khi đú ρG khụng tuần hoàn. 31 v1 v2 v3v4 c(v1) = 3 c(v2) = 4 c(v3) = 1c(v4) = 2 Hỡnh 2.2: Đồ thị định hướng sinh bởi ρ = {v1v4, v2v3, v2v4} Chứng minh. Bằng phương phỏp phản chứng ta giả sử ρG tuần hoàn, tức là trong ρG tồn tại định hướng tuần hoàn vi0 → vi1 → ...→ vis → vi0. Khi đú bởi định nghĩa định hướng cảm sinh ta cú c (vi0) > c (vi1) > ... > c (vis) > c (vi0) , vụ lớ. Vậy ρG khụng tuần hoàn.  Vỡ chỉ cú hữu hạn cỏc định hướng khụng tuần hoàn trờn G nờn chỳng ta cú thể đếm cỏch tụ màu thụng qua định hướng khụng tuần hoàn họ cảm sinh. 2.4. Cặp tương thớch Định nghĩa 2.3 Một định hướng ρ và n-màu c của G được gọi là tương thớch nếu mọi cạnh định hướng u → v trong ρG chỳng ta cú c(u) ≥ c(v) Cặp (ρ, c) được gọi là tương thớch thực sự nếu c(u) > c(v) với mọi cạnh định hướng u→ v. Vớ dụ 2.4 Cho G là đồ thị với 32 • tập đỉnh là V = {v1, v2, v3, v4} • tập cạnh là E = {v1v2, v2v3, v3v4, v1v4, v2v4}. Cho định hướng p = v1v4, v2v3, v2v4 và 3-màu c được tụ như sau c(v1) = 1, c(v2) = 1, c(v3) = 3, c(v4) = 2. Ta thấy: v1 → v2 cú c(v1) = c(v2) v4 → v1 cú c(v4) > c(v1) v4 → v2 cú c(v4) > c(v2) v3 → v4 cú c(v3) > c(v4) v3 → v1 cú c(v3) > c(v1) Vậy định hướng p và 3-màu thực sự c là tương thớch nhưng khụng là tương thớch thực sự. c(v1) = 1