Một số vấn đề về đồ thị và đường kính khuyết của đồ thị

MỘT SỐ VẤN ĐỀ VỀ LÝ THUYẾT ĐỒ THỊ

Các khái niệm cơ bản

1.1.1 Các khái niệm cơ bản về đồ thị

Cho V là một tập hữu hạn và E là tập con của V × V Cặp G = (V, E) được gọi là đồ thị, trong đó V (hay V_G) là tập hợp đỉnh và E (hay E_G) là tập hợp cạnh của đồ thị G Đồ thị G có thể được ký hiệu dưới dạng này.

 Cho hai đỉnh A và B, nếu  A , B  E ( G )thì AB được gọi là cạnh nối đỉnh A với đỉnh B và cạnh AB được gọi là cạnh vô hướng

 Cho hai đỉnh A và B, cạnh nối đỉnh A với đỉnh B đồng thời chỉ rõ hướng (hướng từ A đến B hay hướng từ B đến A) được gọi là cạnh có hướng

 Ta nói cạnh vô hướng hoặc cạnh có hướng u kề với đỉnh A của đồ thị nếu A là đỉnh đầu hoặc đỉnh cuối của cạnh u

 Hai đỉnh A và B được gọi là kề nhau (còn gọi là láng giềng) nếu chúng được nối với nhau bởi một cạnh

 Đồ thị mà có tất cả các cạnh đều vô hướng thì được gọi là đồ thị vô hướng (xem Hình 1.1)

 Đồ thị mà có tất cả các cạnh đều có hướng thì được gọi là đồ thị có hướng (xem Hình 1.2 )

 Đồ thị mà có cả cạnh vô hướng và cạnh có hướng thì được gọi là đồ thị hỗn hợp

 Một đỉnh được nối với chính nó bởi một cạnh được gọi là khuyên

 Đồ thị không có khuyên và giữa hai đỉnh có không quá một cạnh nối giữa chúng được gọi là đồ thị đơn (xem Hình 1.1)

Đồ thị kép, hay còn gọi là đa đồ thị, là loại đồ thị có thể chứa các cạnh song song giữa hai đỉnh hoặc có thể có các đỉnh với khuyên, với ít nhất hai cạnh nối giữa chúng.

 Đồ thị có hữu hạn đỉnh được gọi là đồ thị hữu hạn

 Đồ thị mà mỗi cạnh của nó được gán cho một giá trị được gọi là đồ thị có trọng số (xem Hình 1.4 )

 Đồ thị mà các cạnh của nó không được gán một giá trị được gọi là đồ thị không có trọng số (xem Hình 1.1 )

 Đồ thị rỗng là đồ thị không có đỉnh và không có cạnh nào cả

 Đồ thị điểm là đồ thị chỉ có một đỉnh

1.1.2 Đồ thị con ([1]) Đồ thị G 1  ( V 1 ; E 1 ) được gọi là đồ thị con của đồ thị

1.1.3 Đường đi, chu trình, độ dài của đường đi ([1])

 Trong một đồ thị hai cạnh được gọi là nối tiếp nếu chúng có chung một đầu mút

Một dãy n cạnh k k 1 , 2 , , k n được xem là kề nhau khi không có cạnh nào lặp lại và đỉnh cuối của mỗi cạnh là đỉnh đầu của cạnh tiếp theo.

Một đường đi, hay còn gọi là quỹ đạo, là một dãy các cạnh nối tiếp từ đỉnh A1 đến đỉnh An, ký hiệu là A1 A2 An, trong đó không có đỉnh nào được đi qua hai lần Đỉnh A1 được gọi là đỉnh đầu, còn A n là đỉnh cuối của đường đi Các đỉnh Ai (với 2 ≤ i ≤ n-1) là các đỉnh trong của quỹ đạo Chiều dài của quỹ đạo P, ký hiệu l(P), là số cạnh của P.

Trong đồ thị G, khoảng cách giữa hai đỉnh x và y được ký hiệu là dG(x, y), thể hiện quỹ đạo ngắn nhất nối hai đỉnh này Nếu không tồn tại quỹ đạo nào giữa x và y, ta sẽ quy ước một giá trị cụ thể.

Một quỹ đạo P trong đồ thị G được xác định bởi dãy y, v, e, v, e, v, e, v, x = 0, 1, 1, 2, , k - 1, k, k, có thể được coi là một đồ thị con với tập đỉnh V(P) = {v0, v1, , vk} và tập cạnh E(P) = {e1, e2, , ek} Nếu đảo ngược dãy đỉnh này, ta cũng có một đồ thị con, cho phép xây dựng quỹ đạo P theo hai hướng từ x đến y hoặc từ y đến x.

 Một đường đi khép kín (có đỉnh đầu và đỉnh cuối trùng nhau) được gọi là một chu trình

1.1.4 Định nghĩa bậc của đỉnh ([1])

Bậc của đỉnh v trong đồ thị G được xác định bởi tổng số cạnh kết nối với đỉnh đó, cộng với số lượng khuyên tại đỉnh v, trong đó các khuyên được tính gấp đôi Ký hiệu bậc của v trong G là deg(v).

 Đỉnh treo là đỉnh có bậc bằng 1

 Một đỉnh được gọi là đỉnh cô lập nếu bậc của nó bằng 0

1.1.5 Ví dụ Đồ thị trong Hình 1.1

Ta có deg(A) = deg(C) = 2, deg(B) = deg(D) = 1 Đỉnh B và đỉnh D trong đồ thị Hình 1.1 là các đỉnh treo

1.1.6 Định nghĩa ([1]) Trong đồ thị có hướng bậc vào của đỉnh v được ký hiệu là deg - (v) là số các cạnh có đỉnh cuối là v Bậc ra của đỉnh v được ký hiệu là deg + (v) là số các cạnh có đỉnh đầu là v

Ta thấy: deg + (v) + deg - (v) = deg(v)

1.1.7 Định lí Cho G = (V,E) là một đồ thị vô hướng, có số cạnh là n

Theo định nghĩa bậc của đỉnh v, tổng bậc của các đỉnh trong đồ thị G gấp hai lần số cạnh của nó, vì mỗi cạnh được tính hai lần trong tổng bậc.

1.1.8 Định lí Trong một đồ thị tùy ý, số các đỉnh có bậc lẻ luôn là một số chẵn

Chứng minh Giả sử V 1 , V 2 tương ứng là tập hợp các bậc chẵn và tập hợp các bậc lẻ Khi đó 2n =  

V v V v V v v v v Vì v là số chẵn với mọi v V 1 do đó tổng 

V v v là số chẵn Mặt khác vế phải của tổng trên là chẵn

(theo Định lí 1.1.7), do đó ta suy ra 

Bậc lớn nhất của đồ thị G, ký hiệu là (G):

Bậc nhỏ nhất của đồ thị G, ký hiệu là  (G):

Đồ thị liên thông

Đồ thị G được xem là liên thông khi mọi cặp đỉnh của nó có thể được kết nối bằng một đường đi Ngược lại, nếu đồ thị không liên thông, nó sẽ là sự kết hợp của nhiều đồ thị con không có điểm chung, và những đồ thị con này được gọi là các thành phần liên thông của đồ thị G.

 Đường kính của một đồ thị liên thông G, kí hiệu d (G ) là khoảng cách lớn nhất giữa hai đỉnh bất kỳ trong G

 Đồ thị đơn vô hướng có n đỉnh và có đường kính bằng 1 được gọi là đồ thị đầy đủ n đỉnh và kí hiệu K n

 Một đỉnh của đồ thị liên thông G được gọi là đỉnh mút nếu đồ thị thu được sau khi xóa đỉnh này đi không còn liên thông

1.2.2 Ví dụ Đồ thị ở Hình 1.5 là một ví dụ về đồ thị không liên thông, nó có

1.2.3 Định lý ([2]) Đồ thị liên thông khi và chỉ khi nó chỉ có một thành phần liên thông

Để chứng minh một đồ thị G không liên thông, cần xem xét các điều kiện cần và đủ Giả sử G có hai thành phần liên thông X và Y tách biệt, theo định nghĩa, G không thể liên thông Điều này xảy ra khi trong thành phần X có đỉnh A và trong thành phần Y có đỉnh B mà không tồn tại đường đi nào nối A với B.

1.2.4 Chú ý Từ nay về sau ta sử dụng đến các thuật toán xóa đỉnh và xóa cạnh của đồ thị Khi nói xóa một đỉnh nào đó nghĩa là xóa đi đỉnh đó cùng với tất cả các cạnh kề đỉnh đó, khi nói xóa một cạnh nào đó thì không xóa đi các điểm mút của nó

1.2.5 Định nghĩa i) Một tập đỉnh của đồ thị liên thông G được gọi là tập đỉnh tách nếu ta xóa các đỉnh này đi (theo quy tắc xóa nói trên) thì phần còn lại của G không liên thông Tập đỉnh cắt của đồ thị G là tập đỉnh tách mà mọi tập con thực sự của nó không phải là tập đỉnh tách ii) Số liên thông (nói đầy đủ là số liên thông đỉnh) của đồ thị liên thông

Đồ thị G, ký hiệu là k(G), đại diện cho số đỉnh tối thiểu trong tất cả các tập đỉnh cắt của G Đồ thị G được gọi là k-liên thông (hay k-liên thông đỉnh) nếu k là một số tự nhiên thỏa mãn điều kiện 0 < k ≤ k(G).

Một tập cạnh tách trong đồ thị liên thông G là tập hợp các cạnh, khi bị xóa đi, làm cho phần còn lại của G không còn liên thông Tập cạnh cắt của đồ thị G là tập cạnh tách mà không có tập con thực sự nào của nó cũng là tập cạnh tách.

 Số liên thông cạnh của đồ thị liên thông, kí hiệu là  (G ) là số cạnh ít nhất trong tất cả các tập cạnh cắt của G

 Ta nói đồ thị G là k - liên thông cạnh nếu k là số tự nhiên thỏa mãn

 Cạnh e được gọi là cầu nếu loại bỏ nó ra khỏi đồ thị thì làm tăng số thành phần liên thông

1.2.7 Nhận xét i) Số liên thông đỉnh k (G ) là số nhỏ nhất sao cho nếu xóa đi ít hơn

(G k đỉnh bất kỳ của G thì phần còn lại liên thông Như vậy nếu xóa đi ít hơn

Đỉnh k của đồ thị G được coi là đỉnh quan trọng, vì khi xóa đỉnh này, phần còn lại của G vẫn liên thông Tuy nhiên, tồn tại k đỉnh trong G, khi bị xóa, sẽ làm cho phần còn lại không còn liên thông Số liên thông cạnh (G) là giá trị nhỏ nhất, đảm bảo rằng nếu xóa đi ít hơn số này, đồ thị vẫn giữ được tính liên thông.

 (G cạnh bất kỳ của G thì phần còn lại liên thông Như vậy nếu xóa đi ít hơn

Khi xóa một cạnh bất kỳ của đồ thị G, phần còn lại vẫn giữ được tính liên thông Tuy nhiên, nếu xóa các cạnh thuộc một tập cạnh cắt, đồ thị sẽ phân tách thành đúng hai thành phần không liên thông.

1.2.8 Ví dụ Xét đồ thị trong Hình 1.6

- Các tập cạnh {1,2},  1; 2;5  và tập  3;6;7;8  trong Hình 1.6 là các tập cạnh tách

- Tập cạnh {1,2} là tập cạnh cắt

- Các tập đỉnh {A, D}, {A, B, D} trong Hình 1.6 là tập đỉnh tách

- Tập đỉnh {A, D} là tập đỉnh cắt

- Cạnh e trong Hình 1.9 là một cầu vì khi ta xóa cạnh này đi thì nó làm tăng số thành phần liên thông lên là 2

1) Đồ thị G cho trong Hình 1.6 thì ta thấy k (G )= 2, bởi vì xóa đi 1 đỉnh bất kỳ thì phần còn lại liên thông và nếu xóa đi 2 đỉnh A và D thì phần còn lại là đồ thị trong Hình 1.7 là không liên thông

Vậy G là 1-liên thông đỉnh, 2- liên thông đỉnh nhưng không là 3- liên thông đỉnh

2) Đồ thị trong Hình 1.6 thì ta thấy (G ) = 2 vì xóa đi 1 cạnh bất kỳ thì phần còn lại liên thông và nếu xóa đi hai cạnh 1 và 2 thì phần còn lại là Hình 1.8 không liên thông Do đó G là 1-liên thông cạnh, 2-liên thông cạnh nhưng không 3-liên thông cạnh

3) Mỗi thành phần liên thông của đồ thị trong Hình 1.10 là đồ thị 2- liên thông vì khi ta xóa đi một đỉnh tùy ý cùng với các cạnh kề của nó đồ thị thu được vẫn là đồ thị liên thông Ngoài ra chúng không phải là đồ thị 3-liên thông

4) Mỗi thành phần liên thông của đồ thị trong Hình 1.10 là một đồ thị 2-liên thông cạnh vì khi ta xóa đi một cạnh tùy ý thì phần còn lại vẫn liên thông nhưng nó không phải là đồ thị 3-liên thông cạnh vì khi ta xóa đi hai cạnh tùy ý thì phần còn lại không liên thông nữa

5) Đồ thị đầy đủ K n có k ( K n )  n  1 (ta quy ước  là đồ thị liên thông)

1.2.10 Định lý Nếu G là một đồ thị hai thành phần thì mỗi chu trình của G có độ dài là một số chẵn

Chứng minh rằng đồ thị G là đồ thị hai thành phần cho phép chia đỉnh thành hai tập rời A và B, với mỗi cạnh nối một đỉnh từ A đến một đỉnh từ B Giả sử có chu trình v0 → v1 → → vm → v0 trong G, trong đó v0 thuộc tập A, thì v1 sẽ thuộc tập B, v2 thuộc A, và tiếp tục như vậy Do đó, đỉnh vm cũng thuộc B, dẫn đến việc chu trình trong G có độ dài là một số chẵn.

1.2.11 Định lý Giả sử G là một đồ thị đơn với n đỉnh Nếu G có k thành phần thị số m cạnh của G thỏa mãn :

Chứng minh Ta chứng minh m  n  k bằng phương pháp quy nạp theo số cạnh của G Nếu G là một đồ thị rỗng thì kết quả là hiển nhiên

Nếu đồ thị G chứa một cạnh (ví dụ m0), khi xóa một cạnh bất kỳ của G, số thành phần của đồ thị sẽ tăng lên 1 Đồ thị còn lại sẽ có n đỉnh, k + 1 thành phần và m0 - 1 cạnh Từ giả thiết m0 - 1 ≥ n - (k + 1), ta suy ra rằng m0 ≥ n - k.

Ta có thể tổng quát rằng mỗi thành phần của G là một đồ thị liên thông Giả sử rằng có hai thành phần C i và C j với n i và n j đỉnh, ở đây

 j i n n Nếu ta thay C i và C j bỏi các đồ thị đầy đủ với n i  1 đỉnh và

 1 n j đỉnh thì tổng số đỉnh còn lại không thay đổi và số cạnh là

 j i j j j i j i i i n n n n n n n n n n là một đại lượng dương

1.2.12 Hệ quả Một đồ thị đơn bất kỳ với n đỉnh và nhiều hơn

Chu số, sắc tố

1.3.1 Định nghĩa ([2]) Cho G là một đa đồ thị có n đỉnh, m cạnh, p thành phần liên thông Ta đặt  ( ) G   n p ; c G ( )   m  ( ) G    m n p Số c G ( )được gọi là chu số của đồ thị G

1.3.3 Định lí ([3]) Cho G là một đồ thị kép, giả sử G’ là đa đồ thị thu được từ G bằng cách nối hai đỉnh A và B của G bởi một cạnh mới i) Nếu A và B trùng nhau hoặc có thể nối với nhau bởi một đường đi trong

G thì ta có :  ( ') G   ( ) G , c G ( ')  c G ( ) 1  ii) Trong trường hợp ngược lại thì  ( ') G   ( ) 1 G  và c G ( ')  c G ( )

Chứng minh rằng đồ thị G' có n đỉnh và m + 1 cạnh, với p thành phần liên thông Trong trường hợp này, A và B vẫn duy trì tính liên thông, cho thấy phép biến đổi từ G đến G' là hợp lệ.

G sang G ' không làm thay đổi số thành phần liên thông, dẫn đến p ' = p và  (') G = - n ' p ' =  ( ) G Do đó, c G (') = m ' -  (') G = - m  ( ) 1 G +, suy ra c G (') = c G ( ) 1 + Mặt khác, vì A và B không liên thông trong G nhưng lại liên thông trong G ' nên phép biến đổi từ G sang G ' làm giảm bớt một thành phần liên thông (p ' = - p 1), do đó  (') G = - n ' p '.

Trong đồ thị G, việc tô màu các đỉnh là rất quan trọng Một đỉnh A được coi là tô màu ổn định khi không có bất kỳ láng giềng nào của A cũng được tô màu giống như A.

 Một cách tô màu các đỉnh của đồ thị G được gọi là một cách tô màu ổn định nếu như đỉnh nào của G cũng được tô màu ổn định

Giả sử G là một đồ thị được tô màu ổn định, thì số lượng màu tối thiểu cần thiết để tô các đỉnh của G một cách ổn định được gọi là sắc tố, ký hiệu là p(G).

 Đồ thị có khuyên thì không có cách tô màu ổn định các đỉnh của nó

 Nếu G’ là đồ thị thị p(G’) = p(G) với G là đồ thị đơn thu được từ G’ bằng cách thay cạnh kép của G’ bởi một cạnh đơn

 Với mỗi đồ thị đơn G với n đỉnh ta có thể tô màu ổn đỉnh của chúng bởi n màu, với mỗi một đỉnh ta tô một màu

 Đồ thị điểm có sắc tố bằng 1

 Đồ thị rỗng có sắc tố bằng 0

1.3.6 Định lý Cho mỗi đồ thị G với bậc lớn nhất  ta có p(G)    1

Chứng minh Đồ thị G có bậc lớn nhất , nghĩa là mỗi đỉnh của G có số láng giềng không vượt quá 

Nếu có   1 màu khác nhau, ta có thể tô màu ổn định n đỉnh của đồ thị từ đỉnh 1 đến đỉnh n Cụ thể, ta tô màu đỉnh thứ nhất bằng một trong   1 màu, trong khi số láng giềng của đỉnh này không vượt quá.

Trong quá trình tô màu đồ thị, ta sẽ chọn số màu tương ứng với số láng giềng của đỉnh đầu tiên trong tập màu còn lại Tiếp theo, từ một đỉnh kề của đỉnh đầu tiên, ta tiếp tục tô màu cho các đỉnh láng giềng sao cho màu sắc của chúng khác với màu của đỉnh kề Quá trình này sẽ tiếp tục cho đến khi tất cả các đỉnh của đồ thị G được tô màu, vì số đỉnh không vượt quá số màu đã chọn.

1.3.7 Định lý Một đồ thị cho trước G với ít nhất một cạnh có sắc tố bằng 2 khi và chỉ khi G không có chu trình lẻ cạnh

Để chứng minh rằng đồ thị liên thông có sắc tố bằng 2, ta chỉ cần xem xét trường hợp này Nếu đồ thị có nhiều thành phần liên thông, sắc tố của nó sẽ bằng sắc tố lớn nhất của các thành phần đó Điều kiện cần là nếu đồ thị G có ít nhất một cạnh có sắc tố bằng 2, thì G không có chu trình lẻ cạnh Điều này có thể được chứng minh bằng cách xem xét một chu trình bất kỳ C trong G, trong đó các đỉnh sẽ được tô màu xen kẽ, dẫn đến số đỉnh và số cạnh của chu trình đều chẵn Điều kiện đủ cho đồ thị G là nếu G có ít nhất một cạnh và không có chu trình lẻ cạnh, thì G sẽ có sắc tố bằng 2, cho phép tô màu ổn định bằng 2 màu Bắt đầu từ một đỉnh P0, luôn tồn tại một con đường W nối P0 với bất kỳ đỉnh P nào trong đồ thị G, nhờ vào tính liên thông của nó.

Đỉnh P sẽ được tô màu đỏ nếu độ dài l (W) là số chẵn, và màu xanh nếu l (W) là số lẻ Màu sắc của đỉnh P không phụ thuộc vào lựa chọn con đường, vì bất kỳ con đường W’ nào nối P0 với P cũng sẽ có độ dài chẵn hoặc lẻ tương tự như W.

Thật vậy, giả sử W có độ dài cạnh chẵn, nếu tồn tại con đường W’ nối

P0 với P mà có độ dài lẻ cạnh thì khi đó trong G có chu trình lẻ cạnh Điều này mâu thuẫn với giả thiết G không có chu trình lẻ cạnh

Tiếp theo, chúng ta sẽ tô màu các đỉnh láng giềng của đỉnh P trong đồ thị G Giả sử Q là một đỉnh láng giềng của P, được nối với P bằng một cạnh k Chúng ta sẽ xem xét con đường W0 ngắn nhất nối P0 với P và lựa chọn con đường nối P0 với Q, tùy thuộc vào việc Q có nằm trong W0 hay không.

- Nếu Q nằm trên W0 thì ta thu được một con đường nối P0 với Q có độ dài là l (W ) 1 0 

- Nếu Q không nằm trên W0 ta nối thêm cạnh k vào W0 và thu được con đường nối P 0 với Q có độ dài là l (W ) 1 0 

Do tính chẵn lẻ khác nhau giữa con đường nối P0 với P và Q, màu sắc của P và Q cũng khác nhau Vì vậy, tất cả các đỉnh láng giềng của P sẽ được tô màu khác với P, dẫn đến việc P được tô màu ổn định Như vậy, phương pháp tô màu này là một cách tô màu ổn định.

Cây và bụi

 Một cây là đồ thị đơn vô hướng không có chu trình với ít nhất một đỉnh (Hình 1.11 là hình gồm có hai cây)

 Một đồ thị mà mỗi thành phần liên thông của nó đều là cây được gọi là bụi, (Hình 1.11 là một bụi nó gồm hai thành phần liên thông)

1.4.2 Định lý ([1]) Một cây bất kỳ với ít nhất hai đỉnh luôn có ít nhất hai đỉnh treo

Trong một cây, chỉ tồn tại hữu hạn con đường Xét con đường W = (P1, P2, , Pk) có nhiều cạnh nhất, với k ≠ 1 vì cây có ít nhất hai đỉnh Hai đỉnh cuối của W, P1 và Pk, là các đỉnh treo Nếu giả sử P1 không phải là đỉnh treo, thì P1 sẽ được nối với một đỉnh Q ≠ P2 nào đó Khi đó, Q sẽ trùng với một đỉnh Pi (i ≠ 2), dẫn đến việc W có nhiều nhất một cạnh, nhưng điều này tạo ra một chu trình K = (P1, P2, , Pi, P1), trái với giả thiết rằng đồ thị đã cho là cây.

1.4.3 Định lý ([1]) Một cây có n đỉnh thì có đúng n-1 cạnh

Chứng minh Ta chứng minh bằng phương pháp quy nạp theo n

Với n = 1 thì cây với một đỉnh không có cạnh nào

Giả sử cây tùy ý với n đỉnh có đúng n-1 cạnh

Xét G là một cây có n + 1 đỉnh, theo định lý 1.4.2, G sẽ có ít nhất một đỉnh treo P Khi xem xét đồ thị G    P, do P là đỉnh treo, nên G    P sẽ là một đồ thị liên thông Giả sử ngược lại, G    P có ít nhất hai thành phần liên thông.

Trong đồ thị G liên thông, tồn tại con đường nối hai đỉnh G1 và G2, và con đường này phải đi qua đỉnh P, coi P là điểm trong của nó Do đó, bậc của P ít nhất là 2, điều này mâu thuẫn với việc P được xác định là đỉnh treo trong đồ thị G.

Mặt khác, do G là cây nên G không có chu trình suy ra G    P không có chu trình Vậy G    P là một cây có n đỉnh Theo giả thiết quy nạp thì

G  P có đúng n  1 cạnh Do đó G có n cạnh, vì P có bậc là 1 (đỉnh treo)

1.4.4 Định nghĩa ([1]) Một cây được gọi là cây biểu diễn của đồ thị cho trước nếu nó và đồ thị cho trước có cùng tập đỉnh

1.4.5 Chú ý Một đồ thị cho trước có thể có nhiều cây biểu diễn khác nhau 1.4.6 Định lý ([1]) Một đồ thị vô hướng G cho trước có một cây biểu diễn khi và chỉ khi G là một đồ thị liên thông

Chứng minh Nếu G không liên thông thì không có đồ thị con liên thông nào chứa hết các đỉnh của G và do đó nó không có cây biểu diễn

Nếu G là một cây liên thông, chúng ta cần kiểm tra xem đồ thị có chu trình hay không Nếu G không chứa chu trình, điều này xác nhận rằng G thực sự là một cây theo định nghĩa.

Nếu đồ thị G có chu trình, ta có thể loại bỏ một cạnh trên chu trình đó để tạo ra một đồ thị liên thông mới với số chu trình giảm ít nhất một Tiếp tục quá trình này, sau một số bước hữu hạn, ta sẽ thu được một đồ thị con của G liên thông không có chu trình, tức là một cây biểu diễn.

1.4.7 Định lý ([1]) Đồ thị liên thông G có n đỉnh và n- 1 cạnh thì là cây

Vì đồ thị G là liên thông, theo định lý 1.4.6, G có một cây biểu diễn Đồ thị G có n-1 cạnh, số cạnh này tương đương với số cạnh của cây biểu diễn, do đó, G trùng với cây biểu diễn của nó.

1.4.8 Định lý ([1]) Trong mỗi cây G cho trước, giữa hai đỉnh P và Q của nó chỉ có đúng một con đường nối duy nhất

G là đồ thị liên thông, do đó tồn tại một con đường nối giữa P và Q trong G Vì G là cây, nên G không có chu trình, điều này chứng tỏ rằng không có con đường thứ hai nào nối P và Q.

1.4.9 Định lý ([1]) Một bụi có n đỉnh và c thành phần liên thông thì có đúng n- c cạnh

1.4.10 Định lý ([1]) Nếu G là một đồ thị đơn vô hướng với n đỉnh và c thành phần liên thông có (n- c) cạnh thì G là một bụi

Giả sử các thành phần liên thông của đồ thị G có n1, n2, , nk đỉnh Mỗi thành phần liên thông thứ i với ni đỉnh có thể loại bỏ cạnh để trở thành một cây, do đó số cạnh tối thiểu của nó là ni - 1 Vì vậy, đồ thị G có ít nhất tổng số cạnh là ∑(ni - 1) cho k thành phần liên thông.

)1( cạnh Đẳng thức này xẩy ra khi mỗi thành phần liên thông của nó là một cây Vậy đồ thị đã cho là một cây.

Đồ thị Euler

Đồ thị liên thông G được gọi là đồ thị Euler nếu tồn tại một chu trình khép kín đi qua tất cả các cạnh của G đúng một lần Chu trình này được gọi là đường Euler.

 Một đồ thị không là đồ thị Euler gọi là nửa Euler nếu tồn tại một con đường chứa mọi cạnh của G

1.5.2 Ví dụ Đồ thị trong Hình 1.12 là một đồ thị Euler vì có một đường khép kín là ABCDBGEDGAEFA, còn đồ thị trong Hình 1.13 là một đồ thị nửa Euler vì có một con đường chứa tất cả các cạnh của nó là ABCEAFCDEFB, đồ thị trong Hình 1.14 không phải là một đồ thị Euler, cũng không phải là một đồ thị nửa Euler

1.5.3 Định lý Nếu G là một đồ thị đơn mà bậc của mỗi đỉnh không nhỏ hơn

2 thì G có một chu trình

Để chứng minh, nếu đồ thị G có một vòng hoặc một cạnh kép, điều này là hiển nhiên Do đó, ta giả sử G là một đồ thị đơn và chọn v là một đỉnh bất kỳ trong G.

Chúng ta xây dựng một chuỗi đỉnh từ v đến v1, v2, bằng phương pháp quy nạp, trong đó v1 được chọn là một đỉnh kề bất kỳ của v Đối với mỗi i > 1, v i + 1 sẽ là một đỉnh kề bất kỳ của v i, ngoại trừ đỉnh v i - 1 Sự tồn tại của các đỉnh này được đảm bảo bởi giả thiết quy nạp Do đồ thị G chỉ có hữu hạn đỉnh, việc chọn đỉnh đã được chọn trước đó là điều không thể tránh khỏi.

Nếu v k là đỉnh đầu tiên thì một phần của đường đi nằm giữa hai đỉnh của v k là một chu trình cần tìm

1.5.4 Định lý (Euler,1736) Đồ thị liên thông G là đồ thị Euler khi và chỉ khi bậc của mỗi đỉnh của G là một số chẵn

Để chứng minh, giả sử P là một đường Euler trong đồ thị G Đường P đi qua các đỉnh, do đó tại mỗi đỉnh sẽ có hai hướng Mỗi cạnh trong đồ thị chỉ xuất hiện một lần.

Mỗi đỉnh trong đồ thị G phải có bậc là một số chẵn, điều này được chứng minh bằng phương pháp quy nạp theo số đỉnh Giả sử bậc của mỗi đỉnh là chẵn, và vì G là liên thông, nên mỗi đỉnh có bậc tối thiểu là 2 Theo Định lý 1.5.3, G sẽ chứa ít nhất một chu trình C Nếu chu trình C bao gồm tất cả các cạnh của G, thì việc chứng minh sẽ được hoàn tất.

Nếu không, ta xóa các cạnh của C từ G để tạo thành đồ thị mới H, không liên thông với một số đỉnh trong G nhưng mỗi đỉnh của H vẫn có bậc chẵn Theo giả thiết quy nạp, mỗi thành phần của H có một đường Euler Vì mỗi thành phần của H có ít nhất một đỉnh chung với C, ta có thể thu được đường Euler của G qua các cạnh của C cho đến khi không còn đỉnh cô lập nào của H Quá trình này kết thúc khi ta quay trở lại đỉnh ban đầu, vẽ đường Euler của thành phần H chứa đỉnh và tiếp tục dọc theo cạnh của C.

1.5.5 Hệ quả Một đồ thị liên thông là đồ thị Euler khi và chỉ khi tập cạnh của nó có thể chia thành các chu trình rời nhau

1.5.6 Hệ quả Một đồ thị liên thông là đồ thị nửa Euler khi và chỉ khi nó có đúng hai đỉnh bậc lẻ.

ĐƯỜNG KÍNH KHUYẾT HỖN HỢP

Các định nghĩa và ví dụ

Trong chương này chúng ta sử dụng ký hiệu V G ( ), E G ( ) lần lượt là tập đỉnh và tập cạnh của G

 Đồ thị G được gọi là ( p , q ) - liên thông nếu nó thỏa mãn các điều kiện sau đây:

- Xóa đi p đỉnh bất kỳ và q -1 cạnh bất kỳ của G thì phần còn lại vẫn liên thông

- Xóa đi p -1 đỉnh bất kỳ và q cạnh bất kỳ của G thì phần còn lại vẫn liên thông

Chú ý rằng các khái niệm "xóa đỉnh" và "xóa cạnh" của đồ thị đã được đề cập ở mục 1.2.4 Do đó, (p, q)-liên thông tổng quát áp dụng cho cả liên thông đỉnh và liên thông cạnh.

2.1.2 Nhận xét i) Đồ thị G là ( k ( G ), 0 ) - liên thông và ( 0 ,  ( G ))- liên thông ii) Mối liên hệ giữa số liên thông đỉnh k( G ), số liên thông cạnh  (G ) và bậc nhỏ nhất  (G) của G như sau: k( G )   (G )  (G) iii) Nếu G là (k , 0 )- liên thông thì G là ( k  i , i )- liên thông, trong đó với i bất kỳ thỏa mãn: 0  i  k

Chứng minh i) Theo định nghĩa thì xóa đi k G ( ) 1  đỉnh bất kỳ của G thì phần còn lại liên thông, vậy G là ( k ( G ), 0 )- liên thông Tương tự, G là

Nếu G là đồ thị k-liên thông (đỉnh), thì G cũng là đồ thị k-liên thông cạnh Khi xóa k cạnh của G, ta thu được đồ thị G’ và cần chứng minh rằng G’ vẫn liên thông Bằng cách lấy các điểm mút của k cạnh đã xóa, ký hiệu là A1,…, Ak, và xóa các đỉnh tương ứng, ta có đồ thị G’’ Vì G là k-liên thông, nên G’’ cũng liên thông Ta nhận thấy G’ = G’’ ∪ H, trong đó H là tập hợp các cạnh của G đi qua ít nhất một trong các đỉnh A1,…, Ak Do G’’ liên thông, nên G’ cũng liên thông.

Chúng ta sẽ chứng minh bất đẳng thức thứ hai: \( (G) \leq \delta(G) \) Giả sử A là đỉnh có bậc là \( \delta(G) \) Nếu xóa tất cả các cạnh đi qua A, phần còn lại của G sẽ tạo thành hình G’ gồm một hình H (khác rỗng) nào đó kết hợp với A, và A không nối với bất kỳ đỉnh nào của H, dẫn đến G’ không liên thông Giả sử G là (k, 0)-liên thông và \( 1 \leq i \), chúng ta cần chứng minh rằng G là (k-1, 1)-liên thông Áp dụng kết quả này, G sẽ là (k-2, 2)-liên thông (nếu \( 2 \leq i \)), và tiếp tục quá trình này i lần, chúng ta có điều cần chứng minh Để chứng minh G là (k-1, 1)-liên thông, ta xem xét hai trường hợp.

 Trường hợp 1 Xóa đi k  1 đỉnh và 0 cạnh của G, khi đó phần còn lại liên thông (theo điều kiện thứ 2 của Định nghĩa 2.1.1)

Trong trường hợp xóa đi k - 2 đỉnh và 1 cạnh của đồ thị G, ta thu được đồ thị G' Để chứng minh G' liên thông, ta lấy một điểm mút của cạnh c, ký hiệu là A, và xóa các đỉnh d1,…, dk-2 cùng với A từ G, tạo thành G'' Vì G là (k, 0)-liên thông, nên G'' cũng liên thông theo định nghĩa Rõ ràng, G' được hình thành từ G'' bằng cách thêm vào một số cạnh nối đỉnh A với các đỉnh của G'' Do G'' liên thông, nên G' cũng sẽ liên thông.

Đường kính khuyết cạnh, đỉnh

Giả sử G là đồ thị k - liên thông cạnh và 0  a  k Đường kính khuyết a - cạnh của G được định nghĩa bởi:

D a E ( G )  max d ( G \ X ) | X  E ( G ), | X |  a , trong đó |A| là kí hiệu số phần tử của tập hợp A

Giả sử G là đồ thị k -liên thông và 0  a  k Đường kính khuyết a - đỉnh của G được định nghĩa bởi:

2.2.3 Chú ý D a E (G ) là đường kính lớn nhất trong tất cả các đường kính của đồ thị con của G thu được từ G sau khi xóa đi a cạnh bất kỳ và D a V (G )là đường kính lớn nhất trong tất cả các đồ thị con của G thu được từ G sau khi xóa đi a đỉnh bất kỳ

 Đặc biệt: D 0 E ( G )  D 0 V ( G )  d ( G ) (đường kính của G )

 Với p  k (G ) và q   (G ) thì ta có D V p ( G )   , D q E ( G )  

2.2.4 Nhận xét Dễ dàng thấy rằng cho bất cứ đồ thị liên thông các bất đẳng thức dưới đây là đúng

Trong phần sau đây chúng ta sẽ so sánh đường kính khuyết cạnh và đường kính khuyết đỉnh với cùng một số cạnh hoặc số đỉnh bị xóa

2.2.5 Định lý Cho đồ thị G là k -liên thông và 0  a  k  k ( G ) Khi đó

Chứng minh Giả sử G là đồ thị k -liên thông và X E  E (G ) mà k a

Giả sử u và v là hai đỉnh khác nhau trong đồ thị G Để chứng minh bất đẳng thức trong Định lý, chúng ta sẽ xây dựng một quỹ đạo P từ u đến v trong G X với chiều dài (P) không vượt quá D V a (G) + 1 Đầu tiên, chúng ta xem xét trường hợp u và v không kề nhau trong G.

Giả sử Y  V (G )là tập đỉnh bất kỳ mà thỏa mãn các điều kiện sau đây +) Y  a

+) Với mỗi cạnh e  X ít nhất một trong những đỉnh mút của nó là nằm trong Y

Vì G \ Y là đồ thị con của G với tối đa a đỉnh bị xóa, ta có d(G \ Y) ≤ D_a V(G) Do đó, tồn tại một quỹ đạo P từ đỉnh u đến đỉnh v trong G \ X với chiều dài l(P) ≤ D_V a(G) + 1 Từ cách xây dựng Y, ta có G \ Y ⊆ G \ X, vì vậy P ⊆ G \ X Nếu u và v là hai đỉnh kề nhau trong G và cạnh uv không thuộc X, thì có một quỹ đạo từ u đến v trong G \ X với độ dài bằng 1.

Ta xét trường hợp uv  X Giả sử m là số cạnh trong X nối đỉnh u tới đỉnh khác trong G ( m  a )

Vì đồ thị G là k-liên thông và a < k ≤ k(G) ≤ δ(G), nên có ít nhất a + 1 láng giềng của đỉnh u trong G Điều này dẫn đến việc tồn tại ít nhất a + 1 - m láng giềng của u mà không nằm trong tập X Trong khi đó, tập X chỉ chứa m cạnh nối đỉnh u với một đỉnh khác trong G, do đó có nhiều nhất a - m + 1 cạnh trong X nối đỉnh v với các đỉnh khác trong G Như vậy, đỉnh v có a - m + 1 láng giềng trong G mà các cạnh nối từ v đến những láng giềng này thuộc tập X Một trong số các láng giềng này là đỉnh u, dẫn đến việc có nhiều nhất a - m láng giềng của đỉnh v trong G khác với u.

Láng giềng của đỉnh u nhiều hơn láng giềng của đỉnh v, với cạnh trong E G ( ) \ X Do đó, tồn tại một lân cận w của đỉnh u mà uw không thuộc X, và nếu vw thuộc E (G), thì vw cũng không thuộc X.

Nếu v và w không kề nhau trong đồ thị G, thì tồn tại một quỹ đạo Q trong G X \ với chiều dài l(Q) ≤ D(G, a, V) Theo cách xây dựng, u không nằm trong Q, do đó có một quỹ đạo P từ u tới v trong G X \ Quỹ đạo P từ u đến w và sau đó đến v có độ dài l(P) ≤ 1 + D(G, V, a).

(ở đây w  Q  v là kí hiệu quỹ đạo từ đỉnh w tới đỉnh v )

+) Nếu vw E (G )thì Q là một quỹ đạo có độ dài 1

Sau đây là một vài ví dụ minh họa cho định lý trên

2.2.6 Ví dụ Với chu trình C n (n  3 )

Với n = 4 Hình 2.1 biểu diễn một chu trình C 4 với một đường khuyết và một giao điểm khuyết

2.2.7 Ví dụ Với đồ thị đầy đủ K n ( n  3 )

Rõ ràng ta có: k ( K n )   ( K n )  n  1 , d ( K n )  1 và với mỗi a   n 2 thì

2.2.8 Ví dụ Cho siêu lập phương Q3

Trong Hình 2.2 có bốn đồ thị Q3 với một hoặc hai thành phần đó bị hụt

Đường kính khuyết hỗn hợp

2.3.1 Định nghĩa Giả sử G là đồ thị ( p , q )- liên thông (0  a  p và

( a b - đường kính khuyết hỗn hợp của G là

2.3.2 Chú ý Theo Định nghĩa 2.3.1 thì đỉnh mút của các cạnh của X E có thể nằm trong X V Trong trường hợp này ta có một đồ thị con của G với a đỉnh và ít hơn b cạnh bị xóa Dễ thấy rằng đường kính của đồ thị con bị xóa như vậy nhỏ hơn hoặc bằng đường kính của đồ thị con của G bị xóa đúng a đỉnh và đúng b cạnh Vì vậy điều kiện mà đỉnh mút của các cạnh của X E không nằm trong X V là không cần chứa trong định nghĩa 2.3.1 tuy nhiên ta chỉ ra max ở vế phải đạt trên tập các đồ thị bị xóa mà đỉnh mút của X E không nằm trong X V

2.3.3 Nhận xét Đường kính khuyết hỗn hợp D ( M p , q ) là đường kính lớn nhất trong tất cả các đường kính của đồ thị con thu được từ G bằng cách xóa đi p đỉnh và q cạnh Do đó:

Khi đó: i) max  D b E ( H ) | H  H V a = D ( M a , b ) ( G ) ii) max  D V a ( H ) | H  H E b  = D ( M a , b ) ( G )

Chứng minh i) Theo Định nghĩa 2.2.1 ta có

= max  d G X ( \ ) | X E  E G ( ),| X E |  b X , V  V G ( ), X V  a  (do H H V a ) Suy ra max  D b E ( H ) | H  H V a 

= D ( M a , b ) ( G ) Vậy max  D b E ( H ) | H  H V a = D ( M a , b ) ( G ) ii) Theo Định nghĩa 2.2.2 ta có

= max  d G X ( \ ) | X E  E G ( ),| X E |  b X , V  V G ( ), X V  a (do H  H E b) Suy ra max  D a V ( H ) | H  H E b 

2.3.5 Mệnh đề Nếu G là một đồ thị ( p , q ) - liên thông và a, b là các số tự nhiên thỏa mãn 0  a  p và 0   b q hoặc 0  a  p và 0   b q thì

Giả sử G là đồ thị (p, q)-liên thông, chúng ta sẽ chứng minh rằng trong bất kỳ đồ thị con của G với a đỉnh và b cạnh (b ≠ 0) bị xóa, luôn tồn tại một quỹ đạo nối hai đỉnh bất kỳ có độ dài không quá D(Ma + λ, b - λ)(G), với λ là giá trị tùy ý thỏa mãn 0 ≤ λ ≤ min{b - 1, p - a}.

Gọi u , v  G \ X là hai đỉnh khác nhau và 0    min b  1 , p  a 

Giả sử Y '  X E sao cho Y '   và uv  Y ' Gọi Y E  X E \ Y ' thì Y E  b  

Với mỗi cạnh từ Y ' ta có thể chọn một đỉnh mút khác u và v

Nếu Y' V ⊆ V(G) là một trong các tập đã chọn, thì Y' V ≤ λ vì một số cạnh của Y' có thể chia sẻ đỉnh Cần lưu ý rằng một số đỉnh trong các đỉnh này có thể thuộc vào X V Do đó, X V ∪ Y' V ≤ λ + a Giả sử Y V ⊆ V(G).

Y   a  X U Y  Y và u , v  Y V Giả sử H  G \  Y V U Y E  thì H là một đồ thị con của G với a   đỉnh và b   cạnh bị xóa và u , v  H

Do a    p , b    q và ( a    p hoặc b    q ) và H liên thông, cho nên có một quỹ đạo P giữa u và v trong H với chiều dài  ( P )  D ( M a   , b   ) ( G )

Rõ ràng H không chứa bất kỳ đỉnh nào thuộc X V và bất kỳ cạnh nào thuộc X E

2.3.6 Hệ quả Nếu G là đồ thị k - liên thông và 0  a  k thì

2.3.7 Mệnh đề Nếu G là đồ thị k - liên thông, 0  p  q  k thì

Chứng minh Giả sử a  p  q theo hệ quả 2.3.6 ta chỉ cần chứng minh

D M a V a Đầu tiên chúng ta xóa ( a  1 ) đỉnh trong G , trong G có

C a  cách chọn khác nhau bộ ( a  1 )đỉnh để xóa nên có C a V  ( 1 G ) đồ thị con khác nhau của G với ( a  1 ) đỉnh bị xóa

Gọi H=H V a-1 = G \ X | X  V ( G ), X  a  1  là họ của tất cả các đồ thị con Mỗi đồ thị con H H ít nhất là 2-liên thông và theo Định lí 2.2.5

 D V ( H ) | H  max 1 H = D ( M a , 0 ) ( G )  D V a ( G ) Mệnh đề 2.3.7 và Hệ quả 2.3.6 cho ta kết luận sau

2.3.8 Định lí Nếu G là một k - đồ thị liên thông , 0  a  k thì

2.3.9 Ví dụ Giả sử W6 là một đồ thị “ bánh xe “ gồm 6 đỉnh (Hình 2.4)

2.3.10 Ví dụ Một đồ thị “ bánh xe” gồm 7 đỉnh W 7 (Hình 2.5) Với đồ thị này thì ta có:

Hình 2.3 Đồ thị W6 của ví dụ 2.3.9

Hình 2.4 Đồ thị W7 của ví dụ 2.3.10