Luận văn Một số bài toán đếm trong lý thuyết đồ thị

3 số 0) là 011100111111; ta có thể thiết lập lại tổ hợp có lặp chập 9 kiểu (0,3,0,6) của 4 phần tử a, b, c, d là bbbdddddd). Như vậy số tổ hợp có lặp chập n của m phần tử bằng số chỉnh hợp có lặp chập n+m− 1 của hai chữ số 0 và 1 (trong đó có n chữ số 1 và m− 1 chữ số 0), tức là bằng số các hoán vị có lặp cấp n+m− 1, kiểu (n,m− 1), của hai chữ số 1 và 0). Kí hiệu số tổ hợp có lặp chập n của m phần tử là Cnm, khi đó theo Định lý 1.1.23 ta có Cnm = Cn+m−1(n,m− 1) = C n n+m−1. 1.2. Công thức đa thức "Công thức nhị thức Newton" là sự khai triển của biểu thức (a + b)n trong đó a, b ∈ R và n ∈ N∗. "Công thức đa thức" là sự khai triển của biểu thức (a1 + a2 + . . .+ am)n trong đó a1, a2, . . . , am ∈ R và n ∈ N∗. Để chứng minh công thức đa thức, trước hết ta chứng minh lại công thức nhị thức Newton, theo một cách khác so với cách đã trình bày ở trên. Cách này dễ dàng mở rộng ra cho trường hợp tổng quát. Theo định nghĩa, ta có (a+ b)n = (a+ b)(a+ b) . . . (a+ b)︸ ︷︷ ︸ n lần . Ta khai triển vế phải dựa vào tính chất phân phối của phép nhân với phép cộng, và viết các số hạng của sự khai triển đó theo đúng thứ tự xuất hiện của chúng. Ví dụ 1.2.1. Ta xét các khai triển (a+b)2 = (a+b)(a+b) = aa+ba+ab+bb. (a+b)3 = (a+b)(a+b)(a+b) = aaa+aab+aba+abb+baa+bab+bba+bbb. Rõ ràng các số hạng ở vế phải là tích các phần tử của tất cả các chỉnh hợp có lặp chập n của hai chữ a và b. Các số hạng đồng dạng là tất cả các hoán vị có lặp của a và b có cấp n và kiểu (n1, n2), với n1+n2 = n. Số tất cả các hoán vị có lặp đó là Cn(n1, n2). Sau khi rút gọn các số hạng đồng dạng 12 có kiểu (n1, n2), ta tìm được số hạng tương ứng của sự khai triển là Cn(n1, n2)a n1bn2. Làm như vậy đối với tất cả các kiểu (n1, n2) khác nhau, cuối cùng ta tìm được sự khai triển của nhị thức Newton dưới dạng (a+ b)n = ∑ Cn(n1, n2)a n1bn2 (1.2) trong đó phép cộng trải trên tất cả các kiểu (n1, n2) với n1 + n2 = n và n1, n2 ∈ N. Để chuyển từ đẳng thức 1.2 sang công thức quen thuộc, chỉ cần chú ý rằng Cn(n1, n2) = n! n1!n2! = Cn1n = C n2 n . Đặt n2 = k, ta có C n2 n = C k n. Vậy (a+ b)n = n∑ k=0 Ckna n−kbk. Định lý 1.2.2. Sự khai triển của (a1 + a2 + . . . + am)n được cho bởi công thức sau đây, gọi là công thức đa thức (a1 + . . .+ am) n = ∑ n1,...,nm∈N, ∑m i=1 ni=n Cn(n1, . . . , nm) a n1 1 . . . a nm m = ∑ n1,...,nm∈N, ∑m i=1 ni=n n! n1! . . . nm! an11 . . . a nm m . (1.3) Chứng minh. Xuất phát từ định nghĩa (a1 + . . .+ am) n = (a1 + . . .+ am)(a1 + . . .+ am) . . . (a1 + . . .+ am) (n lần), ta mở các dấu ngoặc và viết các số hạng theo thứ tự xuất hiện của chúng, ta sẽ được mn số hạng có dạng d1d2 . . . dn, mỗi số hạng là một chỉnh hợp có lặp chập n của m chữ a1, a2, . . . , am. Các số hạng đồng dạng là tất cả các hoán vị có cùng một kiểu (n1, n2, . . . , nm). Có Cn(n1, n2, . . . , nm) hoán vị như thế. Rút gọn các số hạng đồng dạng đó, ta tìm được số hạng tương ứng của sự khai triển là Cn(n1, n2, . . . , nm) a n1 1 a n2 2 . . . a nm m = n! n1!n2! . . . nm! an11 a n2 2 . . . a nm m . Làm như vậy đối với tất cả các kiểu (n1, n2, . . . , nm) sao cho n1 + n2 + . . .+ nm = n, cuối cùng ta tìm được sự khai triển của (a1 + a2 + . . .+ am)n dưới 13 dạng: (a1 + a2 + . . .+ am) n = ∑ n1≥0,...,nm≥0 ∑m i=1 ni=n n! n1!n2! . . . nm! an11 a n2 2 . . . a nm m . 1.3. Mở đầu lý thuyết đồ thị Mục này trình bày một số kiến thức chuẩn bị về đồ thị: đồ thị vô hướng, đồ thị có hướng, một số dạng đồ thị đặc biệt, bậc của đỉnh, Bổ đề bắt tay, ... Tài liệu tham khảo chính của mục này là Ngô Đắc Tân (2003), Lý thuyết tổ hợp và đồ thị, NXB Đại học Quốc gia Hà Nội. Định nghĩa 1.3.1 (Đồ thị có hướng). Một đồ thị có hướng G là một cặp có thứ tự G = (V, E), ở đây V là một tập, còn E là một tập con của tích Đề các V × V , tức là E là một quan hệ hai ngôi trên V. Các phần tử của V được gọi là đỉnh, còn các phần tử của E được gọi là các cung của đồ thị có hướng G. Cụ thể hơn, nếu (a, b) ∈ E thì (a,b) được gọi là cung của G với đỉnh đầu là a, đỉnh cuối là b và có hướng đi từ a tới b. Để được trực quan người ta thường biểu diễn đồ thị có hướng G trên mặt phẳng như sau. Các đỉnh của G được biểu diễn bằng các chấm tròn, còn các cung thì dược biểu diễn bằng các đường cong nối đỉnh đầu với đỉnh cuối và có mũi tên hướng từ đỉnh đầu tới đỉnh cuối. a f b cd e Hình 1.1: Ví dụ một đồ thị có hướng Ví dụ 1.3.2. Cho G = (V, E) với V = {a, b, c, d, e, f} và E = {(a, a), (a, b), (b, d), (d, b)(c, e), (e, a)}. Khi đó G là đồ thị có hướng được biểu diễn bằng Hình 1.1. 14 Định nghĩa 1.3.3. Giả sửG = (V, E) là một đồ thị có hướng. Nếu (a, b) ∈ E thì các đỉnh a và b được gọi là liên thuộc với cung (a, b). Khi đó a và b cũng được gọi là kề nhau. Hai cung bất kỳ của G được gọi là kề nhau nếu chúng có đỉnh chung. Cung dạng (a,a) với a ∈ V được gọi là khuyên. Đỉnh không liên thuộc với một cung nào được gọi là đỉnh cô lập. Số các đỉnh của G, tức là |V |, được gọi là cấp của G, còn số các cung của G, tức là |E|, được gọi là cỡ của G. Trước khi định nghĩa khái niệm đồ thị vô hướng ta nhắc lại khái niệm đa tập. Một đa tập hợp, gọi tắt là đa tập là tập các vật, trong đó có thể có những vật không phân biệt được với nhau (và có thể coi như sự lặp lại của cùng một vật). Ví dụ A = {a, b, b, c, c} là một đa tập lực lượng 6. Định nghĩa 1.3.4 (Đồ thị vô hướng). Một đồ thị vô hướng G là một cặp có thứ tự G = (V, E), ở đây V là một tập, còn E là tập với các phần tử là các đa tập lực lượng 2 trên V. Các phần tử của V cũng được gọi là các đỉnh, còn các phần tử của E được gọi là các cạnh của đồ thị có hướng G. Nếu e = {a, b} là một cạnh của G thì a và b được gọi là các đinh đầu mút của cạnh e hay các đỉnh liên thuộc với e. Ta cũng thường ký hiệu cạnh {a, b} ngắn gọn là ab. Người ta cũng thường biểu diễn đồ thị vô hướng trên mặt phẳng tương tự như ta biểu diễn đồ thị có hướng: các đỉnh của đồ thị được biểu diễn bằng các chấm tròn, còn các cạnh thì được biểu diễn bằng một đường cong nối các đỉnh của cạnh. Điểm khác biệt ở đây là không có mũi tên chỉ hướng trên các đường cong đó. Ví dụ 1.3.5. Cho G = (V, E) với V = {a, b, c, d} và E = {(a, a), (a, b), (b, d), (b, c)(c, d)}. Khi đó G là đồ thị vô hướng được biểu diễn bằng Hình 1.2. Đồ thị G′ = (V ′, E ′) được gọi là đồ thị con của đồ thị G = (V, E) nếu V ′ ⊆ V và E ′ ⊆ E. Đồ thị con G′ = (V ′, E ′) của đồ thị G = (V, E) được gọi là đồ thị con bao trùm của G nếu V ′ = V . Nếu E’ chứa tất cả các cung hay 15 ab c d Hình 1.2: Ví dụ một đồ thị vô hướng cạnh của G, mà cả hai đỉnh liên thuộc với nó đều thuộc V’, thì G′ = (V ′, E ′) được gọi là đồ thị con của G = (V, E) cảm sinh bởi tập đỉnh V’ hay cũng được gọi là đồ thị con cảm sinh bởi G = (V, E) trên tập đỉnh V’. Khi đó G’ cũng được ký hiệu là G′ = G[V ′]. Ta thường phải xây dựng các đồ thị mới từ các đồ thị đã cho bằng cách xóa hay thêm một số đỉnh hoặc cạnh. Nếu W ⊆ V , thì G−W = G [V/W ], tức là đồ thị con của G nhận được từ G bằng cách xóa đi cách đỉnh thuộc W và mọi cung (hay cạnh) liên thuộc với các đỉnh trong W. Tương tự, nếu E ′ ⊆ E thì G − E ′ = (V, E/E ′). Nếu W = {w} và E ′ = {(x, y)} (hay E ′ = {xy} ) thì ký hiệu ở trên được đơn giản viết thành (G − w) và G − (x, y) (hay (G− xy) ). Tương tự, nếu x và y không kề nhau trong G thì G+(x, y) (hay G + xy ) là đồ thị nhận được từ G bằng cách nối x với y bằng cung (x, y) (tương ứng, bằng cạnh xy).Nếu G1 = (V1, E1) và G2 = (V2, E2) là hai đồ thị đã cho, thì hợp của hai đồ thị này, ký hiệu là G1 ∪G2, là đồ thị với tập đỉnh là V1 ∪ V2 và tập cung (hay cạnh) E1 ∪E2. Nếu cả hai đồ thị G1 và G2 là đồ thị vô hướng, thì kết nối của hai đồ thị G1 và G2, ký hiệu là G1 +G2, là đồ thị nhận được từ G1 ∪ G2 bằng cách thêm vào tất cả các cạnh dạng xy với x 6= y và x ∈ V1, y ∈ V2. Hiển nhiên là nếu một đồ thị vô hướng không có khuyên có cấp bằng n thì cỡ m của nó thỏa mãn 0 ≤ m ≤ ( n 2 ) . Đồ thị vô hướng cấp n và cỡ m = 0 được gọi là n-đồ thị rỗng hay n-đồ thị hoàn toàn rời rạc và được kí hiệu là On hay En. Còn đồ thị vô hướng không có khuyên cấp n và cỡ m = ( n 2 ) được gọi là n-đồ thị đầy đủ và thường được ký hiệu là Kn. 16 Giả sử G = (V, E) là đồ thị vô hướng không có khuyên với |V | = n. Ta định nghĩa đồ thị bù của G, ký hiệu là G , là đồ thị vô hướng với tập đỉnh cũng là V, còn tập cạnh là E(Kn)\E. Lớp đồ thị đặc biệt sau đây gọi là đồ thị m-phần cũng thường được chú ý. Một đồ thị vô hướng không có khuyên G = (V, E) được gọi là đồ thị m-phần nếu ta có thể phân hoạch V thành dạng V = V1 ∪ V2 ∪ ... ∪ Vm với Vi 6= ∅, i = 1, 2, ..., m sao cho các đỉnh trong cùng Vi , i = 1, 2, ..., m, là không kề nhau. Nếu G là đồ thị m-phần và tồn tại cạnh nối một đỉnh bất kỳ của Vi với một đỉnh bất kỳ của Vj cho mọi i 6= j thì G được gọi là m-phần đầy đủ. Đồ thị 2-phần đầy đủ, trong đó các phần V1 và V2 có |V1| = m, |V2| = n được ký hiệu là Km,n. Giả sử G = (V, E) là một đồ thị có hướng và v ∈ V . Ký hiệu N+(v) = {x ∈ V |(v, x) ∈ E}, N−(v) = {y ∈ V |(y, v) ∈ E}. Khi đó |N+(v)| được gọi là bậc đi ra, còn |N−(v)| được gọi là bậc đi vào của v. Bây giờ giả sử G = (V, E) là một đồ thị vô hướng và v ∈ V . Ký hiệu NG(v) = {x ∈ V |x 6= v, và {x, v} ∈ E} Khi đó NG(v) được gọi là tập các láng giềng của v. Trong trường hợp đồ thị G được hiểu ngầm, ta ký hiệu NG(v) đơn giản bằng N(v). Định nghĩa 1.3.6. Ta định nghĩa bậc của đỉnh v trong đồ thị G, ký hiệu là degG(v) hay ngắn gọn là deg(v) nếu như G được hiểu ngầm, như sau: deg(v) = { |N(v)|, nếu {v, v} /∈ E |N(v)|+ 2, nếu {v, v} ∈ E . (1.4) Ta cũng kí hiệu δ(G) = min v∈V deg(v), ∆(G) = max v∈V deg(v), và gọi chúng tương ứng là bậc nhỏ nhất và bậc lớn nhất của các đỉnh của G. Nếu δ(G) = ∆(G) = k, thì mọi đỉnh của G đều có bậc là k và G được gọi 17 là đồ thị chính qui bậc k hay ngắn gọn là k-chính qui. Một đồ thị vô hướng được gọi là chính qui nếu nó là k-chính qui với một k nào đấy. Đồ thị vô hướng k-chính qui cũng được gọi là đồ thị bậc k. Có những đồ thị khác nhau nhưng khi đổi tên các đỉnh của các đồ thị đó thì chúng lại có thể trùng nhau. Những đồ thị như thế được đọi là đẳng cấu và trong lý thuyết đồ thị người ta thường đồng nhất chúng. Cụ thể hơn, đồ thị có hướng (tương ứng, vô hướng) G = (V, E) và G′ = (V ′, E ′) được gọi là đẳng cấu với nhau nếu tồn tại song ánh ϕ : V → V ′ sao cho (a, b) ∈ E (tương ứng, {a, b} ∈ E) khi và chi khi (ϕ(a), ϕ(b)) ∈ E (tương ứng, {ϕ(a), ϕ(b)} ∈ E). Song ánh ϕ như trên được gọi là đẳng cấu của G và G’. Hai đồ thị đẳng cấu với nhau G và G’ được kí hiệu là G ∼= G′. 1 2 3 4 5 6 a b c d e f G = (V,E) G ′ = (V ′, E′) Hình 1.3: Ví dụ hai đồ thị vô hướng đẳng cấu Ví dụ 1.3.7. Giả sử G = (V, E) và G′ = (V ′, E ′) là các đồ thị vô hướng trong Hình 1.3. Khi đó G ∼= G′ và ánh xạ ϕ : V → V ′ với ϕ(1) = a, ϕ(5) = b, ϕ(2) = c, ϕ(6) = d, ϕ(3) = e, ϕ(4) = f là đẳng cấu của G và G’. Định lý 1.3.8 (Bổ đề bắt tay). Trong đồ thị vô hướng G = (V, E) bất kỳ ta luôn có ∑ v∈V deg(v) = 2 |E|. Chứng minh. Mỗi x ∈ N(v) ta tương ứng với e = {v, x} ∈ E. Dễ thấy rằng tương ứng này là song ánh giữa N(v) và E(v) = {{v, x} ∈ E|v 6= x}. 18 Vì thế ∑ v∈V |N(v)| = ∑ v∈V |Ev|. Vì mỗi cạnh {v, x} ∈ E với v 6= x có hai đỉnh liên thuộc với nó là v và x, nên trong tổng ở vế phải mỗi {v, x} ∈ E với v 6= x đã được tính đúng hai lần: một lần trong Ev và một lần trong Ex. Do đó,∑ v∈V |E(v)| = 2|E1|, ở đây E1 là tập tất cả các cạnh không phải là khuyên của G. Do đó∑ v∈V |N(v)| = 2|E1|. Mặt khác, ta có E2 = E/E1 là tập tất cả khuyên của G. Ký hiệu V1 = {v ∈ V |{v, v} /∈ E}, V2 = {v ∈ V |{v, v} ∈ E}. Khi đó, vì với mỗi đỉnh v ∈ V2, ta có đúng một khuyên {v, v} ∈ E, nên |V2| = |E2|. Vì vậy,∑ v∈V deg(v) = ∑ v∈V1 deg(v) + ∑ v∈V2 deg(v) = ∑ v∈V1 |N(v)|+ ∑ v∈V2 |N(v)|+ 2 |V2| = ∑ v∈V |N(v)|+ 2 |V2| = 2 |E1|+ 2 |E2| = 2 |E| . Định nghĩa 1.3.9. Giả sử G = (V, E) là một đồ thị có hướng. Một hành trình có hướng trong G là một dãy v0e1v1e2v2.....envn sao cho với mọi i = 0, 1, ..., n, vi ∈ V , còn với mọi i = 1, 2, ..., n, ei ∈ E và ei = (vi−1, vi). Khi đó n được gọi là độ dài, đỉnh v0 được gọi là đỉnh đầu, còn vn được gọi là đỉnh cuối của hành trình có hướng trên. Tương tự, một hành trình vô hướng trong G là một dãy v0e1v1e2v2.....envn sao cho với mọi i = 0, 1, ..., n, vi ∈ V , còn với mọi i = 1, 2, ..., n, ei ∈ E và hoặc ei = (vi−1, vi) hoặc ei = (vi, vi−1). Khi đó n cũng được gọi là độ dài, đỉnh v0 được gọi là đỉnh đầu, còn đỉnh vn được gọi là đỉnh cuối của hành trình vô hướng trên. Một hành trình (có hướng, vô hướng) được gọi là khép kín nếu đỉnh đầu và đỉnh cuối của nó trùng nhau. Ví dụ 1.3.10. Giả sử G = (V, E) là đồ thị có hướng như ở Hình 1.4. Khi đó: 19 v2 e2 v3 e3 v4 e4 e5 v5 e6 e7 e8e9 v1 e1 v6 Hình 1.4: Dùng để minh hoạ cho hành trình trong đồ thị 1. v1e1v2e9v2e9v6e6v5e7v2e2v3 là một hành trình có hướng với đỉnh đầu là v1, đỉnh cuối là v3 và độ dài bằng 5. 2. v1e1v2e7v5e4v4e3v3e2v2e7v5e6v6 là một hành trình vô hướng với đỉnh đầu là v1, đỉnh cuối là v6 và độ dài bằng 7. 3. v2e9v6e6v5e7v2 là một hành trình có hướng khép kín. 4. v2e7v5e5v4e3v3e2v2 là một hành trình vô hướng khép kín. Trong trường hợp hành trình có hướng, mỗi cung ei đều có đỉnh đầu là đỉnh đứng trước và đỉnh cuối là đỉnh đứng sau ei trong dãy, tức là nó được xác định bởi chính hai đỉnh đó. Vì vậy người ta thường đơn giản gọi dãy các đỉnh v0v1v1v2.....vn của G là hành trình có hướng trong G nếu với mọi i = 0, 1, ...., n− 1, (vi, vi+1) là một cung của G. Tình huống có hơi khác với trường hợp hành trình vô hướng. Nếu trong G giữa hai đỉnh vi và vj có cả hai cung là e1 = (vi, vj) và e2 = (vj, vi) thì hai dãy con vie1vj và vie2vj là hai đoạn khác nhau trong hành trình. Vì thế, cung giữa vi và vj cần được chỉ ra cụ thể. Tuy nhiên nếu trong G chỉ có một cung giữa vi và vj ( hoặc là (vi, vj) hoặc là (vj, vi) nhưng không đồng thời cả hai), thì cung giữa hai đỉnh đó cũng được xác định duy nhất trong G bởi vi và vj. Do đó để đơn giản ta cũng thay đoạn vie1vj với e1 = (vi, vj) hay vie2vj với e2 = (vj, vi) của hành trình bằng vi, vj. Định nghĩa 1.3.11. Một hành trình có hướng (tương ứng, vô hướng), trong đó các đỉnh đều khác nhau được gọi là một đường có hướng (tương ứng, vô hướng). Một hành trình có hướng (tương ứng, vô hướng), trong đó các cung 20 đều khác nhau được gọi là một vết có hướng (tương ứng, vô hướng). Một hành trình có hướng (tương ứng, vô hướng) khép kín, mà khi xóa đỉnh cuối thì trở thành một đường có hướng (tương ứng, vô hướng), được gọi là một chu trình có hướng (tương ứng, vô hướng). Một hành trình có hướng (tương ứng, vô hướng) khép kín, trong đó các cung đều khác nhau, được gọi là một mạch có hướng (tương ứng, vô hướng). Trên đây ta đã đưa ra các định nghĩa của hành trình, đường, chu trình, vết và mạch (có hướng, vô hướng) trong đồ thị có hướng. Các khái niệm tương tự cũng có thể định nghĩa trong đồ thị vô hướng. Tuy nhiên, ta nhận xét thấy rằng trong đồ thị vô hướng giữa hai đỉnh bất kỳ chỉ có nhiều nhất là một cạnh. Vì thế, các khái niệm trên có thể định nghĩa trong đồ thị vô hướng đơn giản như sau. Định nghĩa 1.3.12. Giả sử G = (V, E) là một đồ thị vô hướng. Một hành trình (vô hướng) trong G là một dãy các đỉnh v0v1v2...vn sao cho với mọi i = 0, 1, ..., n − 1, {vi, vi+1} là một cạnh của G. Các cạnh {vi, vi+1}, i = 0, 1, ..., n− 1, cũng được gọi là các cạnh của hành trình v0v1v2...vn. Khi đó n được gọi là độ dài, v0 được gọi là đỉnh đầu, còn vn được gọi là đỉnh cuối của hành trình trên. Một hành trình được gọi là khép kín nếu đỉnh đầu và đỉnh cuối của nó trùng nhau. Một hành trình được gọi là đường nếu các đỉnh của hành trình đó đều khác nhau. Một hành trình được gọi là vết nếu các cạnh của hành trình đó đều khác nhau. Một hành trình khép kín được gọi là chu trình, nếu nó có độ dài ít nhất là 3 và khi xóa đi đỉnh cuối thì trở thành đường. Một hành trình khép kín được gọi là mạch nếu mọi cạnh của nó đều khác nhau. Ví dụ 1.3.13. Cho đồ thị G = (V, E) như Hình 1.5. Đồ thị này được gọi là đồ thị Petersen. Khi đó, 1. abcde là một đường; 2. abcdea là một chu trình; 3. abcdeaa’c’e’e là một vết. 21 ab cd e a’ b’ c’d’ e’ Hình 1.5: Đồ thị Petersen Định nghĩa 1.3.14. Một đồ thị (có hướng, vô hướng) G = (V, E) được gọi là liên thông yếu hay cũng gọi tắt là liên thông, nếu với hai đỉnh vi và vj khác nhau bất kỳ của G tồn tại một hành trình vô hướng trong G với đỉnh đầu là vi và đỉnh cuối là vj. Trong trường hợp ngược lại, đồ thị được gọi là không liên thông. a b c d e G1 g h i f G2 G = (V,E) Hình 1.6: Đồ thị G với hai thành phần liên thông là G1 và G2 Đồ thị con liên thông G′ = (V ′, E ′) của một đồ thị (có hướng, vô hướng) G = (V, E) được gọi là một thành phần liên thông của G, nếu G′ = G[V ′] và với mọi V ′′ ⊆ V , mà thực sự chứa V ′, đồ thị G[V ′′] là không liên thông. Ví dụ 1.3.15. Đồ thị có hướng G = (V, E) cho trong Hình 1.6 là đồ thị không liên thông. Nó có hai thành phần liên thông là G1 và G2. 22 Chương 2 Bài toán đếm trên đồ thị 2.1. Cây và các bài toán đếm cây Mục này chủ yếu theo các tài liệu [4, 6, 7, 8, 9]]. Các kết quả mục này được tham khảo trong cuốn Combinatorial problems and exercises của Lovasz (Bài tập 1-6 trang 34). Một cách chứng minh khác có thể xem thêm trong cuốn Introduction to enumerative combinatorics của Bona (mục 5.1 và 5.3). Định nghĩa 2.1.1. Một đồ thị vô hướng liên thông không có khuyên và không có chu trình được gọi là cây. Định nghĩa 2.1.2. Một đồ thị vô hướng không có khuyên (không nhất thiết phải là liên thông) và không có chu trình được gọi là rừng. Từ các định nghĩa trên dễ thấy rằng mỗi thành phần liên thông của rừng là cây. G1 G2 G3 G4 G = (V,E) Hình 2.1: Ví dụ một rừng gồm 4 cây 23 Ví dụ 2.1.3. Đồ thị G = (V, E) trên Hình 2.1 là rừng gồm 4 cây là G1, G2, G3, G4. Định nghĩa 2.1.4. Một đồ thị G = (V, E) được gọi là acyclic nếu không tồn tại các dãy các đỉnh v0, v1, . . . , vn = v0 sao cho (vi, vi+1) ∈ E với i = 1, 2, . . . , n. Nhận xét 2.1.5. Một đồ thị acyclic là một rừng. Một đồ thị liên thông và acyclic là một cây. Các đỉnh bậc 1 của cây được gọi là đỉnh lá hay đỉnh cuối, còn các đỉnh bậc lớn hơn 1 của cây được gọi là đỉnh cành hay đỉnh trong. Cấu trúc của cây được mô tả bởi định lý sau đây. Định lý 2.1.6 (Định lý móc xích kiểu hoa cúc). Giả sử T = (V, E) là đồ thị có hướng không có khuyên. Khi đó các khẳng định sau đây là tương đương nhau: (a) T là cây; (b) T không chứa chu trình và |E| = |V | − 1; (c) T liên thông và |E| = |V | − 1; (d) T là đồ thị liên thông, nhưng nếu xóa đi một cạnh bất kỳ thì đồ thị nhận được là không liên thông; (e) Hai đỉnh khác nhau bất kỳ của T được nối với nhau bởi đúng một đường; (f) T không chứa chu trình, nhưng nếu ta thêm một cạnh nối hai đỉnh không kề nhau trong T thì đồ thị nhận được có đúng một chu trình. Chứng minh. 1. (a) ⇒ (b): Giả sử T là cây. Khi đó theo định nghĩa cây, T không chứa chu trình. Vì vậy để chứng minh (b) ta chỉ còn phải chứng minh rằng T có |V |−1 cạnh.Ta chứng minh khẳng định này bằng quy nạp theo |V |. Khẳng định là hiển nhiên đúng nếu |V | = 1. Giả sử với mọi |V | ≤ k, khẳng định đã được chứng minh là đúng. Ta chứng minh nó đúng cho |V | = k+1. Giả sử e = {u, v} là một cạnh của cây T. Xóa cạnh này ra khỏi T ta thu được đồ thị mới T’. Nếu u và v cùng thuộc một thành phần liên thông cuả T’ và chẳng hạn P là một hành trình của thành phần liên thông đó nối u với v, thì uevP là một hành trình khép kín. Từ hành trình này ta có thể 24 xây dựng được một chu trình trong T. Điều này mâu thuẫn với giả thiết T là cây. Vậy u và v phải thuộc hai thành phần liên thông khác nhau của T’, chẳng hạn u thuộc thành phần liên thông T1, còn v thuộc thành phần liên thông T2 của T’. Nếu ngoài T1 và T2, T còn có thành phần liên thông T3, thì trong T ta không thể nối u bằng một hành trình với một đỉnh x trong T3. Điều này mâu thuẫn với giả thiết rằng T là đồ thị liên thông. Vậy T’ có đúng hai thành phần liên thông là T1 = (V1, E1) và T2 = (V2, E2). Khi đó Ti là cây với |Vi| ≤ k, và theo giả thiết qui nạp, |Ei| = |Vi| − 1, i = 1, 2. Ta có |V | = |V1|+ |V2| |E| = |E1|+ |E2|+ 1 Suy ra, |E| = |E1|+ |E2|+ 1 = (|V1| − 1) + (|V2 − 1) + 1 = (|V1|+ |V2|)− 1 = |V | − 1. 2. (b) ⇒ (c): Giả sử T là đồ thị không chứa chu trình và có |E| = |V | − 1. Để chứng minh khẳng định (c) ta chỉ còn phải chứng minh rằng T là đồ thị liên thông. Giả sử T không liên thông. Khi đó T bao gồm k ≥ 2 thành phần liên thông chẳng hạn là T1, T2, ...., Tk. Do T không chứa chu trình, nên các thành phần liên thông Ti = (Vi, Ei), i = 1, 2, ..., k, là cây. Vì (a) ⇒ (b) đã được chứng minh, nên ta suy ra |Ei| = |Vi| − 1, i = 1, 2, ..., k. Vì |E| = |E1|+ |E2|+ ...+ |EK|, |V | = |V1|+ |V2|+ ...+ |VK |, nên ta có |E| = |E1|+ |E2|+ ...+ |EK | = (|V1| − 1) + (|V2| − 1) + ...+ (|Vk| − 1) = |V | − k. Vì k ≥ 2, nên đẳng thức nhận được mâu thuẫn với giả thiết |E| = |V | − 1. Vậy T phải là đồ thị liên thông. 3. (c) ⇒ (d): Trước hết ta chứng minh rằng nếu một đồ thị vô hướng không có khuyên bất kỳ G = (V, E) có k thành phần liên thông thì |E| ≥ |V | − k. Ta chứng minh khẳng định này bằng qui nạp theo |E|. Với |E| = 0, khẳng định trên là hiển nhiên đúng vì khi đó G = On, tức là k = |V |. Giả sử khẳng định đã được chứng minh là đúng cho các đồ thị có t cạnh và 25 G = (V, E) là một đồ thị vô hướng liên thông với |E| = t+1. Nếu ta xóa đi một cạnh của G thì đồ thị nhận được G’ sẽ có |V | đỉnh, t cạnh và số thành phần liên thông hoăc bằng k hoặc bằng k+1. Nếu số thành phần liên thông bằng k thì theo giả thiết qui nạp t ≥ |V | − k. Suy ra, |E| = t+ 1 ≥ |V | − k và đây là điều ta cần chứng minh. Nếu số thành phần liên thông bằng k+1, thì cũng theo giả thiết qui nạp, t ≥ |V | − (k + 1) = |V | − k − 1. Suy ra, |E| = t+ 1 ≥ (|V | − k − 1) + 1 = |V | − k và đây cũng là điều ta cần chứng minh. Bây giờ ta chứng minh (c) ⇒ (d). Giả sử T = (V, E) là đồ thị vô hướng liên thông với |E| = |V | − 1. Nếu xóa một cạnh của T thì đồ thị nhận được T’ sẽ có |E|− 1 cạnh. Nếu T’ vẫn liên thông, thì theo khẳng định vừa chứng minh ở đoạn trên, |E| − 1 ≥ |V | − 1. Nhưng |E| = |V | − 1, nên |E| − 1 = |V | − 2. Ta nhận được |V | − 2 ≥ |V | − 1. Mâu thuẫn. Vậy đồ thị nhận được từ T bằng cách xóa đi một cạnh bất kỳ là không liên thông. 4. (d) ⇒ (e): Giả sử T = (V, E) là đồ thị thỏa mãn (d). Vì T liên thông nên hai đỉnh khác nhau bất kỳ u và v của T được nối với nhau bằng một hành trình Q. Giả sử đỉnh a là đỉnh xuất hiện ít nhất hai lần trong Q. Q1 là đoạn hành trình của Q từ u tới lần xuất hiện đầu tiên của a trong Q, còn Q2 là đoạn hành trình của Q từ lần xuất hiện cuối cùng của a trong Q tới v. Khi đó Q1 ∪ Q2 là hành trình trong T nối u với v, trong đó đỉnh a xuất hiện đúng một lần. Lặp lại quá trình trên một số hữu hạn lần ta sẽ nhận được đường P trong T nối u với v. Giả sử hai đỉnh khác nhau u và v của T được nối với nhau bằng hai đường khác nhau P1 và P2. Khi đó Q = P1 ∪ P2 là một hành trình khép kín trong T. Nếu e = {u, v} là một cạnh của Q, thì T − e sẽ là đồ thị liên thông. Thật vậy, nếu hành trình H nào đó trong T nối hai đỉnh khác nhau x và y không chứa cạnh e thì H cũng là hành trình trong T − e nối x và y; còn nếu H chứa e thì (H − e) ∪ (Q − e) sẽ là hành trình trong T − e nối x và y. Điều vừa nhận được mâu thuẫn với (d). Vậy hai đỉnh khác nhau bất kỳ của T được nối với nhau bởi đúng một đường. 5. (e)⇒ (f): Giả sử đồ thị vô hướng T = (V, E) thỏa mãn (e). Khi đó T không chứa chu trình vì trong trường hợp ngược lại hai đỉnh khác nhau 26 bất kỳ của chu trình đó sẽ được nối với nhau bằng hai đường. Bây giờ nếu thêm vào T một cạnh e nối hai đỉnh u và v không kề nhau nào đó trong T, thì cạnh e đó cùng với đường nối u với v trong T sẽ tạo thành chu trình trong đồ thị T + e. Nếu trong T + e có hai chu trình là C1 và C2, thì dễ thấy rằng cả C1 và C2 đều chứa e (vì T không chứa chu trình). Khi đó C1 − e và C2− e là hai đường khác nhau nối u với v. Điều này mâu thuẫn với (e). Vậy T + e có đúng một chu trình. 6. (f) ⇒ (a): Giả sử đồ thị vô hướng T = (V, E) thỏa mãn (f). Để chứng minh T là cây ta chỉ còn phải chứng minh rằng T liên thông. Giả sử T không liên thông. Khi đó T có ít nhất là hai thành phần liên thông. Nếu ta thêm một cạnh nối hai đỉnh không kề nhau nhưng thuộc hai thành phần liên hông khác nhau của T thì ta không nhận được một chu trình nào trong đồ thị nhận được. Điều này mâu thuẫn với giả thiết (f). Vậy T liên thông và cùng với khẳng định (f). T là cây Mệnh đề 2.1.7. Giả sử cho trước các đỉnh v1, . . . , vn và các số nguyên dương d1, . . . , dn sao cho n∑ i=1 di = 2n− 2, di ≥ 1. Khi đó số cây có tập đỉnh {v1, . . . , vn} sao cho đỉnh vi có bậc di với i = 1, 2, . . . , n là (n− 2)! (d1 − 1)! . . . (dn − 1)! . Chứng minh. Ta chứng minh bằng quy nạp theo n. Với n = 1, 2, khẳng định là hiển nhiên. Do n∑ i=1 di = 2n− 2 < 2n nên ta luôn tìm được một chỉ số i sao cho di = 1. Không