Giáo trình Toán rời rạc - Chương 3: Đồ thị

Đồ thị G là liên thông, nhưng đồ thị G’ không liên thông và có 3 thành phần liên thông. 
3.6.3. Định nghĩa: Một đỉnh trong đồ thị G mà khi xoá đi nó và tất cả các cạnh liên 
thuộc với nó ta nhận được đồ thị con mới có nhiều thành phần liên thông hơn đồ thị G 
được gọi là đỉnh cắt hay điểm khớp. Việc xoá đỉnh cắt khỏi một đồ thị liên thông sẽ tạo 
ra một đồ thị con không liên thông. Hoàn toàn tương tự, một cạnh mà khi ta bỏ nó đi sẽ 
tạo ra một đồ thị có nhiều thành phần liên thông hơn so với đồ thị xuất phát được gọi là 
cạnh cắt hay là cầu. 
Thí dụ 19: 
x y z 
v w u 
x 
t 
u 
y 
w 
z 
v 
a 
d c h 
b 
i 
k 
l 
g 
x 
v 
y 
w 
z 
s 
u 
t 
 49 
 Trong đồ thị trên, các đỉnh cắt là v, w, s và các cầu là (x,v), (w,s). 
3.6.4. Mệnh đề: Giữa mọi cặp đỉnh phân biệt của một đồ thị liên thông luôn có đường 
đi sơ cấp. 
Chứng minh: Giả sử u và v là hai đỉnh phân biệt của một đồ thị liên thông G. Vì G liên 
thông nên có ít nhất một đường đi giữa u và v. Gọi x0, x1, ..., xn, với x0=u và xn=v, là dãy 
các đỉnh của đường đi có độ dài ngắn nhất. Đây chính là đường đi sơ cấp cần tìm. Thật 
vậy, giả sử nó không là đường đi đơn, khi đó xi=xj với 0  i < j. Điều này có nghĩa là 
giữa các đỉnh u và v có đường đi ngắn hơn qua các đỉnh x0, x1, ..., xi-1, xj, ..., xn nhận 
được bằng cách xoá đi các cạnh tương ứng với dãy các đỉnh xi, ..., xj-1. 
3.6.5. Mệnh đề: Mọi đơn đồ thị n đỉnh (n  2) có tổng bậc của hai đỉnh tuỳ ý không 
nhỏ hơn n đều là đồ thị liên thông. 
Chứng minh: Cho đơn đồ thị G=(V,E) có n đỉnh (n  2) và thoả mãn yêu cầu của bài 
toán. Giả sử G không liên thông, tức là tồn tại hai đỉnh u và v sao cho không có đường 
đi nào nối u và v. Khi đó trong đồ thị G tồn tại hai thành phần liên thông là G1 có n1 
đỉnh và chứa u, G2 chứa đỉnh v và có n2 đỉnh. Vì G1, G2 là hai trong số các thành phần 
liên thông của G nên n1+n2  n. ta có: 
deg(u)+deg(v)  (n1 1)+(n2  1) = n1+n22  n2 <n. 
Điều mâu thuẫn ở trên dẫn đến kết luận là đồ thị G phải liên thông. 
3.6.6. Hệ quả: Đơn đồ thị mà bậc của mỗi đỉnh của nó không nhỏ hơn một nửa số đỉnh 
là đồ thị liên thông. 
3.6.7. Mệnh đề: Nếu một đồ thị có đúng hai đỉnh bậc lẻ thì hai đỉnh này phải liên 
thông, tức là có một đường đi nối chúng. 
Chứng minh: Cho G=(V,E) là đồ thị thị có đúng hai đỉnh bậc lẻ là u và v. Giả sử u và v 
không liên thông với nhau. Khi đó chúng phải thuộc hai thành phần liên thông nào đó 
của đồ thị G, G1 chứa u và G2 chứa v. 
 Bậc của đỉnh u trong G1 cũng chính là bậc của u trong G, nên trong G1 đỉnh u vẫn 
có bậc lẻ và G1 có duy nhất một đỉnh bậc lẻ. Điều này mâu thuẫn. Vậy hai đỉnh u và v 
phải liên thông. 
3.6.8. Mệnh đề: Cho G=(V,E) là một đồ thị liên thông. Khi đó một đỉnh của G là điểm 
khớp khi và chỉ khi trong G tồn tại hai đỉnh u và v sao cho mỗi đường đi nối u và v đều 
phải đi qua đỉnh này. 
Chứng minh: Điều kiện cần: Giả sử đỉnh x là điểm khớp trong đồ thị G. Khi đó đồ thị 
con G1 của G nhận được bằng cách xoá x và các cạnh liên thuộc với nó là không liên 
thông. Giả sử G2, G3 là hai trong các thành phần liên thông của G1. Lấy u là đỉnh trong 
G2 và v là đỉnh trong G3. Do u, v thuộc hai thành phần liên thông khác nhau, nên trong 
G1 các đỉnh u, v không liên thông. Nhưng trong G các đỉnh u, v lại liên thông, nên mọi 
đường đi nối u, v đều phải đi qua đỉnh x. 
 50 
Điều kiện đủ: Giả sử mọi đường đi nối u, v đều đi qua đỉnh x, nên nếu bỏ đỉnh x và các 
cạnh liên thuộc với x thì đồ thị con G1 nhận được từ G chứa hai đỉnh u, v không liên 
thông. Do đó G1 là đồ thị không liên thông hay đỉnh x là điểm khớp của G. 
3.6.9. Định lý: Cho G là một đơn đồ thị có n đỉnh, m cạnh và k thành phần liên thông. 
Khi đó 
2
)1)(( 

knkn
mkn . 
Chứng minh: Bất đẳng thức mkn  được chứng minh bằng quy nạp theo m. Nếu 
m=0 thì k=n nên bất đẳng thức đúng. Giả sử bất đẳng thức đúng đến m1, với m  1. 
Gọi G’ là đồ thị con bao trùm của G có số cạnh m0 là nhỏ nhất sao cho nó có k thành 
phần liên thông. Do đó việc loại bỏ bất cứ cạnh nào trong G’ cũng tăng số thành phần 
liên thông lên 1 và khi đó đồ thị thu được sẽ có n đỉnh, k+1 thành phần liên thông và 
m01 cạnh. Theo giả thiết quy nạp, ta có m01  n(k+1) hay m0  nk. Vậy m  n-k. 
 Bổ sung cạnh vào G để nhận được đồ thị G’’ có m1 cạnh sao cho k thành phần 
liên thông là những đồ thị đầy đủ. Ta có m  m1 nên chỉ cần chứng minh 
m1  
2
)1)((  knkn
. 
Giả sử Gi và Gj là hai thành phần liên thông của G’’ với ni và nj đỉnh và ni  nj >1 (*). 
Nếu ta thay Gi và Gj bằng đồ thị đầy đủ với ni+1 và nj1 đỉnh thì tổng số đỉnh không 
thay đổi nhưng số cạnh tăng thêm một lượng là: 
1
2
)2)(1(
2
)1(
2
)1(
2
)1(





 







 


ji
jjjjiiii nn
nnnnnnnn
. 
Thủ tục này được lặp lại khi hai thành phần nào đó có số đỉnh thoả (*). Vì vậy m1 là lớn 
nhất (n, k là cố định) khi đồ thị gồm k-1 đỉnh cô lập và một đồ thị đầy đủ với n-k+1 
đỉnh. Từ đó suy ra bất đẳng thức cần tìm. 
3.6.10. Định nghĩa: Đồ thị có hướng G được gọi là liên thông mạnh nếu với hai đỉnh 
phân biệt bất kỳ u và v của G đều có đường đi từ u tới v và đường đi từ v tới u. 
 Đồ thị có hướng G được gọi là liên thông yếu nếu đồ thị vô hướng nền của nó là 
liên thông. 
 Đồ thị có hướng G được gọi là liên thông một chiều nếu với hai đỉnh phân biệt 
bất kỳ u và v của G đều có đường đi từ u tới v hoặc đường đi từ v tới u. 
Thí dụ 20: 
 G G’ 
u v 
y s 
w 
t 
x 
u v w 
y s t 
x 
 51 
 Đồ thị G là liên thông mạnh nhưng đồ thị G’ là liên thông yếu (không có đường 
đi từ u tới x cũng như từ x tới u). 
3.6.11. Mệnh đề: Cho G là một đồ thị (vô hướng hoặc có hướng) với ma trận liền kề A 
theo thứ tự các đỉnh v1, v2, ..., vn. Khi đó số các đường đi khác nhau độ dài r từ vi tới vj 
trong đó r là một số nguyên dương, bằng giá trị của phần tử dòng i cột j của ma trận A
r
. 
Chứng minh: Ta chứng minh mệnh đề bằng quy nạp theo r. Số các đường đi khác nhau 
độ dài 1 từ vi tới vj là số các cạnh (hoặc cung) từ vi tới vj, đó chính là phần tử dòng i cột 
j của ma trận A; nghĩa là, mệnh đề đúng khi r=1. 
 Giả sử mệnh đề đúng đến r; nghĩa là, phần tử dòng i cột j của A
r
 là số các đường 
đi khác nhau độ dài r từ vi tới vj. Vì A
r+1
=A
r
.A nên phần tử dòng i cột j của A
r+1
 bằng 
bi1a1j+bi2a2j+ ... +binanj, 
trong đó bik là phần tử dòng i cột k của A
r
. Theo giả thiết quy nạp bik là số đường đi 
khác nhau độ dài r từ vi tới vk. 
 Đường đi độ dài r+1 từ vi tới vj sẽ được tạo nên từ đường đi độ dài r từ vi tới đỉnh 
trung gian vk nào đó và một cạnh (hoặc cung) từ vk tới vj. Theo quy tắc nhân số các 
đường đi như thế là tích của số đường đi độ dài r từ vi tới vk, tức là bik, và số các cạnh 
(hoặc cung) từ vk tới vj, tức là akj. Cộng các tích này lại theo tất cả các đỉnh trung gian vk 
ta có mệnh đề đúng đến r+1. 
BÀI TẬP CHƢƠNG III: 
1. Cho G là đồ thị có v đỉnh và e cạnh, còn M, m tương ứng là bậc lớn nhất và nhỏ nhất 
của các đỉnh của G. Chứng tỏ rằng 
m  
2e
v
  M. 
2. Chứng minh rằng nếu G là đơn đồ thị phân đôi có v đỉnh và e cạnh, khi đó 
e  v2/4. 
3. Trongmột phương án mạng kiểu lưới kết nối n=m2 bộ xử lý song song, bộ xử lý P(i,j) 
được kết nối với 4 bộ xử lý (P(i1) mod m, j), P(i, (j1) mod m), sao cho các kết nối 
bao xung quanh các cạnh của lưới. Hãy vẽ mạng kiểu lưới có 16 bộ xử lý theo phương 
án này. 
4. Hãy vẽ các đồ thị vô hướng được biểu diễn bởi ma trận liền kề sau: 
a) 
1 2 3
2 0 4
3 4 0










, b) 
1 2 0 1
2 0 3 0
0 3 1 1
1 0 1 0












, c) 
0 1 3 0 4
1 2 1 3 0
3 1 1 0 1
0 3 0 0 2
4 0 1 2 3
















. 
 52 
5. Nêu ý nghĩa của tổng các phần tử trên một hàng (t.ư. cột) của một ma trận liền kề đối 
với một đồ thị vô hướng ? Đối với đồ thị có hướng ? 
6. Tìm ma trận liền kề cho các đồ thị sau: 
a) Kn , b) Cn, c) Wn , d) Km,n , e) Qn. 
7. Có bao nhiêu đơn đồ thị không đẳng cấu với n đỉnh khi: 
a) n=2, b) n=3, c) n=4. 
8. Hai đơn đồ thị với ma trận liền kề sau đây có là đẳng cấu không? 














0111
1000
1001
1010
, 














0111
1001
1001
1110
. 
9. Hai đơn đồ thị với ma trận liền kề sau đây có là đẳng cấu không? 














01110
11000
10101
00011
, 














10101
01001
01110
10010
. 
10. Các đồ thị G và G’ sau có đẳng cấu với nhau không? 
a) 
b) 
11. Cho V={2,3,4,5,6,7,8} và E là tập hợp các cặp phần tử (u,v) của V sao cho u<v và 
u,v nguyên tố cùng nhau. Hãy vẽ đồ thị có hướng G=(V,E). Tìm số các đường đi phân 
biệt độ dài 3 từ đỉnh 2 tới đỉnh 8. 
12. Hãy tìm số đường đi độ dài n giữa hai đỉnh liền kề (t.ư. không liền kề) tùy ý trong 
K3,3 với mỗi giá trị của n sau: 
a) n=2, b) n=3, c) n=4, d) n=5. 
u1 
u2 
u3 
u4 
u5 u6 
v1 v2 
v4 v3 
v5 v6 
u1 u2 u3 
u4 u5 u6 
v1 v2 
v6 v3 
v5 v4 
 53 
14. Một cuộc họp có ít nhất ba đại biểu đến dự. Mỗi người quen ít nhất hai đại biểu 
khác. Chứng minh rằng có thể xếp được một số đại biểu ngồi xung quanh một bàn tròn, 
để mỗi người ngồi giữa hai người mà đại biểu đó quen. 
15. Một lớp học có ít nhất 4 sinh viên. Mỗi sinh viên thân với ít nhất 3 sinh viên khác. 
Chứng minh rằng có thể xếp một số chẵn sinh viên ngồi quanh một cái bàn tròn để mỗi 
sinh viên ngồi giữa hai sinh viên mà họ thân. 
16. Trong một cuộc họp có đúng hai đại biểu không quen nhau và mỗi đại biểu này có 
một số lẻ người quen đến dự. Chứng minh rằng luôn luôn có thể xếp một số đại biểu 
ngồi chen giữa hai đại biểu nói trên, để mỗi người ngồi giữa hai người mà anh ta quen. 
17. Một thành phố có n (n  2) nút giao thông và hai nút giao thông bất kỳ đều có số 
đầu mối đường ngầm tới một trong các nút giao thông này đều không nhỏ hơn n. Chứng 
minh rằng từ một nút giao thông tuỳ ý ta có thể đi đến một nút giao thông bất kỳ khác 
bằng đường ngầm.