Bài giảng Toán tổ hợp - Chương 4: Đại cương về đồ thị - Nguyễn Anh Thi

ĐẠI CƯƠNG VỀ ĐỒ THỊ 
Chương 4. 
2 
Nội dung 
1. Giới thiệu 
2. Các khái niệm cơ bản 
3. Biểu diễn đồ thị 
4. Đẳng cấu đồ thị 
5. Đường đi, chu trình 
3 
Bài toán. Thành phố Königsberg, Đức nằm trên một 
con sông, có hai hòn đảo lớn nối với nhau và với đất 
liền bởi bảy cây cầu. Bài toán đặt ra là có thể đi theo 
một tuyến đường mà đi qua mỗi cây cầu đúng một 
lần rồi quay lại điểm xuất phát hay không? 
1. Giới thiệu 
4 
Năm 1736, nhà toán học 
Leonhard Euler đã chứng 
minh rằng điều đó là không 
thể được. 
5 
Bài toán 1. Có thể vẽ hình phong bì thư bởi một nét 
bút hay không? Nếu có hãy chỉ ra tuần tự các nét vẽ 
1 
3 2 
4 5 
6 
Bài toán 2. Một đoàn kiểm tra chất lượng các con 
đường. Để tiết kiệm thời gian, đoàn kiểm tra muốn đi 
qua mỗi con đường đúng 1 lần. Kiểm tra xem có cách 
đi như vậy không? 
2 
1 
3 
4 
5 
6 
7 
8 
7 
Bài toán 3. Một sinh viên muốn đi từ nhà đến trường 
thì phải đi như thế nào? Cách đi nào là ngắn nhất? 
8 
Định nghĩa. Một đồ thị vô hướng 
(undirected graph) G=(V, E) được 
định nghĩa bởi: 
• Tập hợp V  được gọi là tập các 
đỉnh (vertex) và n = |V| gọi là cấp 
của đồ thị; 
• Tập hợp E là tập các cạnh (edge) 
của đồ thị; Mỗi cạnh e E được liên 
kết với một cặp đỉnh {i, j}, không 
phân biệt thứ tự 
2. Các khái niệm cơ bản 
9 
Định nghĩa. Trên đồ thị vô hướng, xét cạnh e được 
liên kết với cặp đỉnh {i, j}: 
 Cạnh e kề với đỉnh i và đỉnh j (hay đỉnh i và đỉnh j kề 
với cạnh e); có thể viết tắt e=ij 
 Đỉnh i và đỉnh j được gọi là 2 đỉnh kề nhau (hay đỉnh i 
kề với đỉnh j và ngược lại, đỉnh j kề với đỉnh i) 
 Hai cạnh nối cùng một cặp đỉnh gọi là hai cạnh song 
song. 
 Cạnh có hai đỉnh trùng nhau gọi là một khuyên 
Đỉnh kề 
10 
( ) { : ( , ) }v u V v u E 
Tập các đỉnh kề với đỉnh v được viết là 
Nhận xét. Đồ thị G hoàn toàn được xác định nếu 
chúng ta biết 
Vvv  ),(
nên đồ thị G cũng có thể định nghĩa như sau: 
( , )G V 
Đỉnh kề 
11 
 Cạnh song song: e1, e7 
 Khuyên: e9 
 Đỉnh treo: 5 
 Đỉnh cô lập: 6 
 
(2) {1, 3, 4} 
Đỉnh kề 
12 
Định nghĩa. Cho G là đồ thị vô hướng. Khi đó G 
được gọi là: 
a) đơn đồ thị (hay đồ thị đơn) nếu G không có 
khuyên và không có cạnh song song 
b) đa đồ thị nếu G không có khuyên, cho phép có 
cạnh song song 
c) giả đồ thị nếu G cho phép có cạnh song song và 
có khuyên 
Một số loại đồ thị vô hướng 
13 
b 
d a 
k 
e 
h 
g 
c 
a 
b 
c d 
b 
c 
a 
d 
14 
 Đồ thị rỗng: tập cạnh là tập rỗng 
 Đồ thị đủ: đồ thị vô hướng, đơn, 
giữa hai đỉnh bất kỳ đều có đúng 
một cạnh. 
 Đồ thị đủ n đỉnh ký hiệu là Kn. 
 Kn có 
𝑛 n−1
2
 cạnh. 
 Đồ thị k-đều: là đồ thị mà mọi đỉnh 
đều có bậc bằng nhau và bằng k. 
C 
A B 
Các dạng đồ thị 
15 
 Đồ thị lưỡng phân: đồ thị vô 
hướng G=(V, E) được gọi là đồ thị 
lưỡng phân nếu tập V được chia 
thành hai tập V1 và V2 thỏa: 
 V1 và V2 phân hoạch V; 
 Cạnh chỉ nối giữa V1 và V2. 
 Đồ thị lưỡng phân đủ: là đồ thị 
lưỡng phân thỏa điều kiện mỗi đỉnh 
trong V1 kề với mọi đỉnh trong V2. 
• V1=n và V2=m, ký hiệu Kn,m 
C 
A 
B 
D 
E 
16 GV: Döông Anh Ñöùc 16 
K4 
K4 
K3, 3 
K2, 3 
K2  K1, 1 
K3 
17 
Định nghĩa. Một đồ thị có hướng 
G=(V, U) được định nghĩa bởi: 
• Tập hợp V  được gọi là tập 
các đỉnh. 
• Tập hợp U là tập các cạnh (cung) 
của đồ thị; Mỗi cạnh u U được 
liên kết với một cặp đỉnh (i, j) V2. 
Ký hiệu u=(i,j) hoặc u=ij. 
Đồ thị có hướng 
18 
Trên đồ thị có hướng, xét cạnh u được liên kết với 
cặp đỉnh (i, j): 
 i được gọi là đỉnh đầu, j được gọi là đỉnh cuối 
 Cạnh u kề với đỉnh i và đỉnh j (hay đỉnh i và đỉnh j 
kề với cạnh u); có thể viết tắt u=(i, j). Cạnh u đi ra 
khỏi đỉnh i và đi vào đỉnh j. 
Đỉnh kề 
19 
( ), ( )v v  
Định nghĩa. Cho đồ thị có hướng G=(V, E) và e=(u, v) E 
• v là đỉnh sau của u 
• u là đỉnh trước của v 
• Tập hợp các đỉnh sau và đỉnh trước của v lần lượt là 
Nhận xét. Đồ thị G hoàn toàn được xác định 
nếu chúng ta biết 
Vvv  ),(
nên đồ thị G cũng có thể được định nghĩa như sau: 
),(  VG
Đỉnh kề 
20 
)(v
Ví dụ. 
 1 
2 
3 5 
6 
4 
a 
b 
c 
d 
e 
f 
g 
h 
i 
j k 
l 
v 
1 
2 
3 
5 
6 
)(v 
Đỉnh kề 
21 
 Cạnh song song 
- u1, u7 cùng chiều 
- u5, u8 ngược chiều 
 Khuyên: u2 
 Đỉnh treo: 6 
 Đỉnh cô lập: 5 
22 
 Đồ thị có tập đỉnh và tập cạnh hữu hạn được gọi 
là đồ thị hữu hạn 
 Trong học phần này ta chỉ làm việc với các đồ thị 
hữu hạn. Để ngắn gọn chúng ta chỉ dùng thuật 
ngữ ĐỒ THỊ và hiểu ngầm đó là đồ thị hữu hạn. 
Đồ thị hữu hạn 
23 
Định nghĩa. Cho hai đồ thị G = (V,E) và G’ = (V’,E’) 
(cùng vô hướng hoặc cùng có hướng). 
 G’ được gọi là đồ thị con của G, ký hiệu G’ G, 
nếu V’ V và E’  E 
 Nếu V’= V và E’  E thì G’ được gọi là đồ thị con 
khung của G. 
Đồ thị con 
G H 
24 
Định nghĩa. Xét đồ thị vô 
hướng G. Bậc của đỉnh x 
trong đồ thị G là số các cạnh 
kề với đỉnh x, mỗi khuyên 
được tính hai lần, ký hiệu là 
degG(x) (hay deg(x) nếu 
đang xét một đồ thị nào đó). 
Bậc của đỉnh 
25 
Ví dụ. 
1 
2 
3 
4 
6 
8 
7 
5 
i 
deg(i) 
1 2 3 4 5 6 7 8 
Bậc của đỉnh 
26 
Ví dụ. H là đơn đồ thị vô hướng có n đỉnh (n 2). 
a) Mỗi đỉnh của H có bậc tối đa là bao nhiêu ? H có 
tối đa bao nhiêu cạnh ? 
b) Chứng minh rằng H có ít nhất 2 đỉnh cùng bậc. 
Bậc của đỉnh 
Giải. a) Vì H là đơn đồ thị vô hướng nên mỗi đỉnh 
của H không có khuyên và chỉ có thể nối với các 
đỉnh khác không quá một cạnh, nghĩa là mỗi đỉnh của 
H có bậc tối đa là (n 1). 
Suy ra H có tối đa là n(n 1) / 2 cạnh 
27 
b) Giả sử bậc của các đỉnh của H đều khác nhau. 
Khi đó bậc của n đỉnh của H lần lượt là 0, 1, , (n -
1), nghĩa là H phải có đỉnh cô 0. 
 Do H có đỉnh bậc 0 nên các đỉnh khác của H có 
bậc tối đa là (n 2) : mâu thuẫn. Vậy có ít nhất 2 
đỉnh của H có cùng bậc. 
Bậc của đỉnh 
Ví dụ. Hãy vẽ một đồ thị đơn vô hướng gồm 6 đỉnh 
với bậc các đỉnh lần lượt là: 2,2,3,3,3,3 
28 
Định nghĩa. Xét đồ thị có hướng G 
Bậc của đỉnh 
Nửa bậc ngoài của đỉnh x là số 
các cạnh đi ra khỏi đỉnh x, ký 
hiệu deg+(x). 
Nửa bậc trong của đỉnh x là số 
các cạnh đi vào đỉnh x, ký hiệu 
deg-(x). 
Bậc của đỉnh x: 
 deg(x)=deg+(x)+deg-(x) 
29 
v deg (v) deg (v) deg(v) 
a 
b 
c 
d 
e 
f 
Chú ý. 1 khuyên được tính 1 lần bậc vào và 1 lần bậc ra 
Ví dụ. 
 a 
c 
b d 
f 
e 
Bậc của đỉnh 
30 
 Đỉnh TREO là đỉnh có bậc bằng 1. 
 Đỉnh CÔ LẬP là đỉnh có bậc bằng 0. 
C 
A B 
D 
Bậc của đỉnh 
31 
Định lý. 
 Xét đồ thị có hướng G=(X, U). Ta có: 
 Xét đồ thị vô hướng G=(X, E). Ta có: 
   
x X x X x X
vaødeg x deg x deg x 2 U
 
x X
deg x 2 E
Hệ quả. Số đỉnh có bậc lẻ trong một đồ thị là một số 
chẵn. 
Mối liên hệ giữa bậc và số cạnh 
32 
Ví dụ. Trong một bữa tiệc, mọi người bắt tay nhau. 
Chứng minh rằng số người bắt tay mới một số lẻ 
người khác là số chẵn. 
Giải. Lập đồ thị hướng G như sau: 
 Mỗi đỉnh là đại diện cho một người 
 Hai đỉnh nối với nhau bằng một cạnh nếu hai 
người đó bắt tay nhau 
Một người bắt tay với một số lẻ người khác, có nghĩa 
đỉnh tương ứng có bậc là lẻ. Theo hệ quả trên ta có 
điều chứng minh. 
33 
Ví dụ. Cho G là đồ thị vô hướng liên thông có 6 
đỉnh với các bậc lần lượt là 1, 2, 2, 2, 3 và 4. Tính 
số cạnh của G. Hãy vẽ phác họa đồ thị G. (một 
trường hợp là đơn đồ thị và một trường hợp là đồ thị 
có cả khuyên và các cạnh song song). 
Bậc của đỉnh 
Ví dụ. Cho H là đồ thị vô hướng có 34 cạnh, 3 đỉnh 
bậc 6, một số đỉnh bậc 5 và các đỉnh còn lại có bậc 
8. Hãy xác định số đỉnh của H. 
Ví dụ. Vẽ đồ thị đơn vô hướng gồm 6 đỉnh với bậc 
2,2,3,3,3,5 
34 
3. Biểu diễn đồ thị 
A 
B 
C 
D 
u1 
u2 
u3 
u4 
u5 
u6 
A 
B 
C 
D 
e1 
e2 
e3 
e4 
e5 
e6 
G 
H 
35 
Định nghĩa. Cho G=(V,E) với V ={1,..,n} và E ={e1,em}. 
Ma trận liên kết của G là ma trận A=(aij) cấp nXm được 
định nghĩa như sau: 
 a) Nếu G vô hướng thì aij {0,1} xác định bởi 
 b) Nếu G có hướng thì aij {-1,0,1} xác định bởi 
j
ij
j
1 neáu i keàvôùi e
a
0 neáu i khoâng keàvôùi e
j
ij j
j
1 neáu e rôøi khoûi i
a 1 neáu e ñi vaøo i
0 neáu e khoângkeàvôùi i
Ma trận liên kết 
36 
G 
1 2 3 4 5 6
1 1 1 1 0 0
1 1 0 0 1 0
A
0 0 1 0 1 1
0 0 0 1 0 1
e e e e e e
1
2
3
4
1 
2 
3 
4 
e1 
e2 
e3 
e4 
e5 
e6 
Ma trận liên kết 
37 
G 
1 
2 
3 
4 
u1 
u2 
u3 
u4 
u5 
u6 
Ma trận liên kết 
1 2 3 4 5 6
1 1 1 1 0 0
1 1 0 0 1 0
A
0 0 1 0 1 1
0 0 0 1 0 1
u u u u u u
1
2
3
4
38 
Ví dụ. Cho G là đồ thị có ma trận liên kết 
Đáp án. 
Hãy vẽ đồ thị G 
Ma trận liên kết 
39 
Định nghĩa. Cho G=(V,E) với V ={1,..,n}. Ma trận kề 
(adjacency matrix) của G là ma trận vuông A=(aij) cấp n 
xác định bởi 
 aij= số cạnh từ đỉnh i đến j 
c 
a 
b 
d 
0 1 0 0
1 0 0 2
1 1 1 1
0 0 0 0
b a c d 
a 
b 
c 
d 
Ma trận kề 
40 
0 2 1 0 0 0
2 0 1 0 1 1
1 1 0 0 0 1
0 0 0 0 0 0
20 1 0 0 0
0 1 1 0 0 0
a b c d e f
a
b
c
d
e
f
a b 
d c e 
Ma trận kề 
Lưu ý. Với đồ thị vô hướng, nếu đỉnh i có 1 khuyên thì 
aii được tính thêm 2 
41 
Tính chất 
1. Ma trận kề của đồ thị vô hướng là đối xứng 
aij = aji. Ngược lại, ma trận (0,1) bậc n sẽ tương 
ứng với đơn đồ thị vô hướng n đỉnh 
2. Nếu đồ thị vô hướng: 
Tổng dòng thứ i = Tổng cột thứ i = bậc của đỉnh 
3. Nếu đồ thị có hướng: 
Tổng dòng i = nửa bậc ngoài của i 
Tổng cột i =nửa bậc trong của i 
42 
Ví dụ. Lập ma trận kề của đồ thị sau: 
Ma trận kề 
43 
Ví dụ. Cho đồ thị vô hướng G với ma trận kề sau: 
Hãy vẽ đồ thị G 
Đáp án 
Ma trận kề 
44 
Xét hai đồ thị sau: chúng giống nhau hay khác nhau? 
1 
2 3 
4 
1 
2 
3 
4 
1 
2 3 
4 1 
2 3 
4 
(2’) (3’) 
(4’) (1’) 
4. Đẳng cấu đồ thị 
45 
4. Đẳng cấu đồ thị 
Định nghĩa. Cho hai đồ thị đơn G = (V,E) và G’=(V’,E’). 
Ta nói rằng G đẳng cấu G’, ký hiệu G  G’, nếu tồn tại 
song ánh f :V→ V’sao cho: 
 ij là cạnh của G f(i)f(j) là cạnh của G’ 
46 
Chú ý. Nếu G và G’ là các đồ thị đơn vô hướng đẳng 
cấu qua ánh xạ f thì chúng có: 
 Cùng số đỉnh 
 Cùng số cạnh 
 Cùng số đỉnh với bậc cho sẵn 
 deg i = deg f(i) 
 . 
47 
Ví dụ. 
48 
 a 
 b 
 c 
 d e 
 a 
 b 
 c 
 d 
 e 
 deg(e) = 1 
Không đẳng cấu 
49 
a 
b 
c d 
e 
f 
1 
2 
3 
6 
5 4 
a 
b 
4 
d 
e 
1 
2 
3 c 
5 
50 
Ví dụ. Hãy tìm các đồ thị đẳng cấu trong các đồ thị sau: 
(G1) (G2) (G3) (G4) (G5) (G6) (G7) 
1 6
3 5
4 7
G G
G G
G G



51 
Ví dụ. Các đồ thị sau có đẳng cấu không? Tại sao? 
g – B – 2 
f – D – 4 
i – A – 1 
j – E – 5 
h – C - 3 
52 
Ví dụ. Hai đồ thị sau có đẳng cấu không? Tại sao? 
53 
5. Đường đi, chu trình 
Định nghĩa. Cho G = (V, E) là đồ thị vô hướng u,v V 
a) Đường đi (dây chuyền) có chiều dài k nối hai đỉnh 
u,v là dãy đỉnh và cạnh liên tiếp nhau v0e1v1e2vk-
1ekvk sao cho: 
 v0=u, vk = v và e i=vi-1vi , i=1,2,,k 
 Đường đi đơn nếu không có cạnh nào xuất hiện quá 
một lần và gọi là sơ cấp nếu không có đỉnh nào xuất 
hiện quá một lần 
b) Nếu x trùng với y thì đường đi sẽ được chu trình 
Khái niệm chu trình đơn, sơ cấp tương tự như đường 
đi 
54 
Chu trình sơ 
cấp nào 
không? 
 a,e1,b,e2,c,e3,d,e4,b là đường đi từ đỉnh a tới đỉnh b 
có chiều dài là 4. Vì đồ thị đơn, nên ta có thể viết ngắn 
gọn là: (a,b,c,d,b) 
 Chu trình sơ cấp: (b,c,d,b) (b,f,e,b) 
55 
Định nghĩa. Cho G = (V,E). Trên V ta định nghĩa quan 
hệ tương đương như sau: 
 u~v u = v hay có một đường đi từ u đến v 
a) Nếu u~v thì ta nói hai đỉnh u và v liên thông với 
nhau 
b) Mỗi lớp tương đương được gọi là một thành phần 
liên thông của G 
c) Nếu G chỉ có một thành phần liên thông thì G gọi là 
liên thông 
Liên thông 
56 
Ví dụ. Đồ thị nào sau đây liên thông? 
d 
a 
b 
c 
e 
G1 
d 
a b 
c 
e 
d 
a 
b 
c 
e d 
a b 
c 
e 
f 
G2 
G3 G4 
Liên thông 
57 
Ví dụ. Cho đồ thị đơn vô hướng G có 7 đỉnh trong đó 
có một đỉnh bậc 6. Hỏi G có liên thông không? 
Liên thông 
Giải. Đỉnh bậc 6 nối với 6 đỉnh còn lại. Do đó hai đỉnh 
bất kỳ đều có một đường đi qua đỉnh bậc 6. Suy ra G 
liên thông 
Ví dụ. Cho đồ thị vô hướng G liên thông mà mỗi đỉnh 
đều có bậc bằng 10. Chứng minh rằng nếu xoá đi một 
cạnh bất kỳ thì đồ thị thu được vẫn còn liên thông 
58 
Giải. Giả sử ta xóa cạnh uv. Ta chỉ cần chứngminh 
vẫn có đường đi từ u đến v. 
Phản chứng. Giả sử không có đường đi từ u đến v. 
Khi đó thành phần liên thông G’ chứa u mà không 
chứa v. 
Trong G’, u có bậc 9, mọi đỉnh khác đều có bậc 10. 
Tổng các bậc trong G’ là số lẻ .Vô lý. 
Liên thông 
59 
Ví dụ. Xét đồ thị đơn vô hướng G với 6 đỉnh, trong đó 
có một đỉnh bậc 1 và 5 đỉnh bậc 3. Chứng minh rằng 
G liên thông. 
Liên thông 
Giải. Giả sử G không liên thông. Gọi G1, G2, ,Gk là 
các thành phần liên thông của G (k 2). 
Vì G không có đỉnh cô lập nên mỗi thành phần liên 
thông đều phải có ít nhất hai đỉnh. Như vậy mỗi thành 
phần liên thông đều phải có ít nhất một đỉnh bậc 3. 
Suy ra mỗi thành phần liên thông phải có ít nhất 4 đỉnh. 
Vậy G phải có ít nhất 4k 8 đỉnh . Trái giả thiết 
60 
Định nghĩa. Cho G = (V,E) là đồ thị vô hướng liên 
thông 
a) Đỉnh v được gọi là đỉnh khớp nếu G – v 
không liên thông (G – v là đồ thị con của G có 
được bằng cách xoá v và các cạnh kề với v) 
b) Cạnh e được gọi là cầu nếu G-e không liên 
thông (G-e là đồ thị con của G có được bằng 
cách xoá cạnh e). 
Liên thông 
61 
Ví dụ. Tìm đỉnh khớp và cầu của đồ thị sau 
Đáp án: Đỉnh khớp: w,s 
 Cầu : ws, xv 
62 
Định nghĩa. Cho G = (V,E) vô hướng liên thông, 
không phải Kn, n>2. 
 a) Số liên thông cạnh của G, ký hiệu e(G) là số 
cạnh ít nhất mà khi xoá đi G không còn liên thông 
nữa. 
 b) Số liên thông đỉnh của G, ký hiệu v(G) là số 
đỉnh ít nhất mà khi xoá đi G không còn liên thông 
nữa. 
63 
Ví dụ. Tìm số liên thông cạnh và liên thông đỉnh của 
các đồ thị sau 
64 
Liên thông mạnh 
Định nghĩa. Cho G =(V,E) là đồ thị có hướng u,v V 
a) Đường đi có chiều dài k nối hai đỉnh u,v là dãy đỉnh 
và cung liên tiếp nhau 
 v0e1v1e2.vk-1ekvk 
sao cho: 
 v0 = u, vk = v 
 ei = vi-1vi , i = 1,2,,,k. 
b) Đường đi không có cạnh nào xuất hiện quá một lần 
gọi là đường đi đơn. 
65 
c) Đường đi không có đỉnh nào xuất hiện quá một 
lần gọi là đường đi sơ cấp. 
d) Đường đi được gọi là mạch (chu trình) nếu nó 
bắt đầu và kết thúc tại cùng một đỉnh. 
Ví dụ. 
Đường đi có độ dài 4 từ đỉnh 1 tới đỉnh 2 là : (1,2,3,4,2) 
66 
Định nghĩa. Cho đồ thị có hướng G = (V,E). Trên V 
ta định nghĩa quan hệ tương đương như sau: 
 u~v u = v hay có một đường đi từ u đến v và 
đường đi từ v đến u . 
a) Nếu u~v thì ta nói hai đỉnh u và v liên thông 
mạnh với nhau . 
b) Mỗi lớp tương đương được gọi là một thành 
phần liên thông mạnh của G . 
c) Nếu G chỉ có một thành phần liên thông mạnh thì 
G gọi là liên thông mạnh. 
Liên thông mạnh 
67