Bài giảng Toán rời rạc và lý thuyết đồ thị - Chương 4: Các khái niệm về đồ thị - Võ Tấn Dũng

GV: Võ Tấn Dũng
TRƯỜNG CAO ĐẲNG CÔNG NGHỆ THÔNG TIN TP.HCM
MÔN TOÁN RỜI RẠC
ĐƠN ĐỒ THỊ VÔ HƯỚNG
 Đơn đồ thị vô hướng G = (V,E) là một bộ gồm hai tập 
hợp V và E.
 V là tập các đỉnh (vertices).
 E là tập các cạnh (edges), mỗi cạnh là một cặp không có 
thứ tự gồm 2 đỉnh khác nhau của tập V.
3 Ví dụ: Đơn đồ thị G1 = (V1, E1), trong đó
V1={a, b, c, d, e, f, g, h},
E1={(a,b), (b,c), (c,d), (a,d), (d,e), (a,e), (d,b), (f,g)}.
Đồ thị G1
a
b
e
d
c g
f
h
ĐA ĐỒ THỊ VÔ HƯỚNG
 Đa đồ thị vô hướng G= (V, E) bao gồm V là tập các 
đỉnh, và E là tập các cặp không có thứ tự gồm hai phần 
tử khác nhau của V gọi là các cạnh. 
 Hai cạnh e1 và e2 được gọi là cạnh song song nếu 
chúng cùng tương ứng với một cặp đỉnh.
 Ví dụ: Đa đồ thị G2 = (V2, E2), trong đó
V2={a, b, c, d, e, f, g, h},
E2={(a,b), (b,c), (b,c), (c,d), (a,d), (d,e),
(a,e), (a,e), (a, e), (d,b), (f,g)}.
Đồ thị G2
d
Cạnh song song
e
a
b
c
f
g
h
Cạnh song song, cạnh vòng
 Cạnh song song (cạnh bội)
 Hai hay nhiều cạnh phân 
biệt cùng tương ứng với 
một cặp đỉnh
 Cạnh vòng (cạnh loop):
 Một cạnh tương ứng với 
hai đỉnh trùng nhau.
 Đơn đồ thị
 Đồ thị không có vòng và 
cạnh song song
 Đa đồ thị
 Các đồ thị không phải là 
đơn đồ thị
x
y z 
A
B
C
D
ĐỒ THỊ CÓ HƯỚNG
 Đơn đồ thị có hướng G = (V, E) bao gồm V là tập các 
đỉnh và E là tập các cặp có thứ tự gồm hai đỉnh khác 
nhau của V gọi là các cạnh (cung).
 G = (V, E)
 Tập đỉnh V
 Tập cạnh (cung)
E = { (a, b) | a,b V }
 e = (a, b) E
 Ký hiệu: e = 
 e có hướng từ a đến b
 a: đỉnh đầu; b: đỉnh cuối
 e là cạnh vòng ab
ab
CÁC THUẬT NGỮ CƠ BẢN
 Hai đỉnh u và v của đồ thị 
vô hướng G được gọi là kề 
nhau nếu (u,v) là cạnh 
của đồ thị G.
 Nếu e = (u, v) là cạnh của 
đồ thị ta nói cạnh này là 
cạnh liên thuộc với hai 
đỉnh u và v (hoặc cũng nói 
là nối đỉnh u và đỉnh v)
 Đồng thời các đỉnh u và v 
sẽ được gọi là các đỉnh 
đầu của cạnh (u, v).
BẬC CỦA ĐỈNH
 Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh 
liên thuộc với nó và sẽ ký hiệu là deg(v).
deg(a) = 1, deg(b) = 4, deg(c) = 4, deg(f) = 3,
deg(d) = 1, deg(e) = 3, deg(g) = 0
 Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 được gọi 
là đỉnh treo. Trong ví dụ trên đỉnh g là đỉnh cô lập, 
a và d là các đỉnh treo.
 Bậc của đỉnh
 Đỉnh của đồ thị G có bậc là 
n nếu nó kề với n đỉnh 
khác.
 Ký hiệu: deg(v) hay d(v)
 Mỗi vòng được kể là 2 
cạnh tới một đỉnh
 Đỉnh cô lập  deg(v)=0
 Đỉnh treo  deg(v)=1
 Cạnh treo có đầu mút là 
một đỉnh treo
 Đồ thị rỗng: deg(v)=0 v
a b c d 
efg
Tính chất bậc của đỉnh
 Định lý 1. Giả sử G = (V, E) là đồ thị vô hướng với |E| 
cạnh. Khi đó tổng bậc của tất cả các đỉnh bằng hai lần 
số cạnh.
 Hệ quả. Trong đồ thị vô hướng thì:
 Tổng bậc là một số chẵn.
 Số đỉnh bậc lẻ (nghĩa là có bậc là số lẻ) là một số chẵn.
32
Ví dụ. 
Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) 
với 14 đỉnh và 25 cạnh đều có bậc là 3 hoặc 5.
Hỏi G có bao nhiêu đỉnh bậc 3?
Giải. Giả sử G có x đỉnh bậc 3. 
Khi đó có 14-x đỉnh bậc 5.
Do | E | = 25, nên tổng tất cả các bậc là 50. 
Từ đó, 3x + 5(14-x) = 50
Suy ra x = 10.
Cạnh vào, cạnh ra
 Nếu e = (u, v) là cung của đồ thị có hướng G thì ta 
nói hai đỉnh u và v là kề nhau.
 Và nói cung (u, v) nối đỉnh u với đỉnh v
 Hoặc cũng có thể nói là cung này là đi ra khỏi đỉnh u 
và vào đỉnh v.
 Đỉnh u(hoặc v) sẽ được gọi là đỉnh đầu (cuối) của cung 
(u,v).
Bậc vào, bậc ra
 Ta gọi bậc ra của đỉnh v trong đồ thị có hướng là số 
cung của đồ thị đi ra khỏi nó và ký hiệu là deg+(v)
 Ta gọi bậc vào của đỉnh v trong đồ thị có hướng là số 
cung của đồ thị vào nó và ký hiệu là deg-(v)
deg-(a)=1, deg-(b)=2, deg-(c)=2, deg-(d)=2, deg-(e) = 2.
deg+(a)=3, deg+(b)=1, deg+(c)=1, deg+(d)=2, deg+(e)=2.
Định lý:
 Giả sử G = (V, E) là đồ thị có hướng. Khi đó:
Ví dụ
f
a
b c
ed
deg-(d) = 2
deg+(d)= 1
deg-(f) = 0
deg+(f)= 0
b kề tới c và c kề từ b
deg-(a) = 0
deg+(a)= 2
a- đỉnh nguồn
deg-(e) = 2
deg+(e)= 0
e – đỉnh đích (target)
Ví dụ: hai đồ thị sau đẳng cấu
1  DN, 2  CT, 3  BD, 4  AG
17
ĐỒ THỊ ĐẲNG CẤU
18
Điều kiện cần nhưng không phải là đủ
để G1=(V1, E1) là đẳng cấu với G2=(V2, E2):
Ta phải có |V1|=|V2|, và |E1|=|E2|.
Số lượng đỉnh bậc k ở hai đồ thị là như
nhau.
ĐỒ THỊ ĐẲNG CẤU
•Tính chất trên chỉ có 
điều kiện cần
•Ví dụ: hai đồ thị sau 
không đẳng cấu
?
19
ĐỒ THỊ ĐẲNG CẤU
Xét sự đẳng cấu của các cặp đồ thị sau. Chỉ ra song ánh 
nếu chúng đẳng cấu
20
BÀI TẬP
21
Sự đẳng cấu giữa các đồ thị
 Chứng minh 2 đồ thị đẳng cấu
 Nếu là đẳng cấu thì hãy gán tên cho đồ thị thứ hai
để thấy rõ sự đẳng cấu, trái lại hãy nêu rõ sự khác
biệt.
a
b
cd
e
f
b
d
a
e
fc
BÀI TẬP
Có đẳng cấu không?
 Nếu là đẳng cấu thì hãy gán tên cho đồ thị thứ hai để 
thấy rõ sự đẳng cấu, trái lại hãy nêu rõ sự khác biệt.
a
b
c
d
e
• Cùng số 
lượng đỉnh
• Cùng số 
lượng 
cạnh
• Khác số lượng 
đỉnh bậc 2 
(1 3)
CHU TRÌNH (vô hướng)
 Đườ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, x1,, xn-1, xn
trong đó 
 Đườ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 đ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.
CHU TRÌNH (có hướng)
 Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số 
nguyên dương, trên đồ thị có hướng G = (V, E) là dãy
x0, x1,, xn-1, xn
trong đó 
 Đườ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 đ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.
26
 Ví dụ: đường đi
 Ví dụ: chu trình
Ví dụ: 1, 2, 5, 3, 4 hoặc 1, a, 2, c, 5, d, 3, e, 4
• Là đường đi đơn
Ví dụ: 5, 2, 3, 4 hoặc 5, c, 2, b, 3, e, 4.
Không có đỉnh lặp nên là đường đi đơn
2 3 4
a b
c
1
5
d
e
2 3 4
a b
c
1
5
d
e
Đường đi (Path)
28
P1
Ví dụ (tiếp)
P1=(1,b,2,h,3) là đường
đi đơn
P2=(4,c,5,e,2,g,6,f,5,d,1)
là đường đi nhưng
không là đường đi đơn
24
1
5
3
6
a
c
b
e
d
f
g
hP2
P1
Ví dụ (tiếp)
P1=(1, b, 2, h, 3) là
đường đi đơn
P2=(4,c,5,e,2,g,6,f,5,d,1)
là đường đi nhưng
không là đường đi đơn
24
1
5
3
6
a
c
b
e
d
f
g
hP2
Chu trình
1, 2, 3, 1. (hay 1, a, 2, b, 3, e)
• Chu trình đơn
Chu trình: (1, 2, 3, 4, 1) hay 
1, a, 2, b, 3, c, 4, d, 1
• Chu trình đơn
2
3
4
a b
cd
1
e
2
3
4
a b
cd
1
e
Chu trình (Cycle)
Ví dụ: Chu trình trên đồ thị vô hướng
 C1=(V,b,X,g,Y,f,W,c,U,a,V) là chu trình đơn
 C2=(U,c,W,e,X,g,Y,f,W,d,V,a,U) là chu trình nhưng không 
là chu trình đơn
C1
XU
V
W
Z
Y
a
c
b
e
d
f
g
h
C2
 C1=(V,b,X,g,Y,f,W,c,U,a,V) là chu trình đơn
 C2=(U,c,W,e,X,g,Y,f,W,d,V,a,U) là chu trình nhưng không 
là chu trình đơn
C1
XU
V
W
Z
Y
a
c
b
e
d
f
g
hC2
Ví dụ: Chu trình trên đồ thị vô hướng
LIÊN THÔNG
Đồ thị G = (V, E) được gọi là liên thông nếu luôn tìm 
được đường đi giữa hai đỉnh bất kỳ của nó.
 Ví dụ. Đồ thị gồm các đỉnh a,b,c,d,e,f,g là liên thông. 
Còn đồ thị H tạo ra từ H1,H2,H3 là không liên thông.
34
Tính liên thông
 Tính liên thông trong đồ thị vô hướng
 Đỉnh cắt và cầu
 u là một đỉnh cắt số thành phần liên thông tăng 
lên nếu bỏ u và các cạnh liên thuộc với nó
 e là một cầu số thành phần liên thông tăng lên 
nếu bỏ cạnh e
ĐỒ THỊ CON
CÁC THÀNH PHẦN LIÊN THÔNG
 Ta gọi đồ thị con của đồ thị G = (V, E) là đồ thị H = (W, F), 
trong đó 
 Trong trường hợp đồ thị là không liên thông, nó sẽ rã ra 
thành một số đồ thị con liên thông đôi một không có đỉnh 
chung. Những đồ thị con liên thông như vậy ta sẽ gọi là các 
thành phần liên thông của đồ thị.
 Ví dụ. Đồ thị H trong hình dưới gồm 3 thành phần liên 
thông H1, H2, H3.
MỘT SỐ DẠNG ĐẶC BIỆT CỦA ĐỒ THỊ
 Đồ thị đầy đủ.
 Đồ thị hai phía
 Đồ thị hai phía đầy đủ
37
 Đồ thị đầy đủ Kn
 Đơn đồ thị
 Số đỉnh: |V| = n
 Bậc: deg(v) = n – 1 v V
 Số cạnh: |E| = n(n - 1) / 2
K5K4
K1 K2 K3 K6
ĐỒ THỊ ĐẦY ĐỦ
Đồ thị đầy đủ Kn có tất cả n(n-1)/2 cạnh, nó là đơn đồ 
thị có nhiều cạnh nhất.
38
 Một đồ thị G được gọi là đồ thị lưỡng phân nếu tập các 
đỉnh của G có thể phân thành 2 tập hợp không rỗng, rời 
nhau sao cho mỗi cạnh của G nối một đỉnh thuộc tập 
này đến một đỉnh thuộc tập kia.
 Ký hiệu: Km,n
ĐỒ THỊ LƯỠNG PHÂN
(HAI PHÍA)
ĐỒ THỊ LƯỠNG PHÂN ĐẦY ĐỦ
 Đồ thị hai phía 
được gọi là đồ thị hai phía đầy đủ nếu mỗi đỉnh của phía 
này đều có một cạnh nối đến từng đỉnh của phía kia. Và 
ký hiệu là Km,n. 
 Ví dụ: K2,3, K3,3, K3,4 được cho trong hình dưới.
ĐỒ THỊ PHẲNG
 Đồ thị được gọi là đồ thị phẳng nếu ta có thể vẽ nó 
trên mặt phẳng sao cho các cạnh của nó không cắt 
nhau ngọai trừ ở đỉnh. 
 Ví dụ đồ thị K4 là phẳng.
CÔNG THỨC EUCLER
 Euler đã chứng minh được rằng: các cách biểu diễn 
phẳng khác nhau của một đồ thị phẳng, đều chia mặt 
phẳng ra thành cùng một số miền. Euler đã tìm được 
mối liên hệ giữa số miền, số đỉnh và số cạnh của đồ thị 
phẳng như sau.
 Giả sử G=(V,E) là đồ thị phẳng liên thông với |V| đỉnh, 
|E| cạnh. Gọi |R| là số miền của mặt phẳng bị chia bởi 
biểu diễn phẳng của G. Khi đó
 Ví dụ: Cho G là đồ thị phẳng liên thông với 20 đỉnh, 
mỗi đỉnh đều có bậc là 3. Hỏi mặt phẳng bị chia làm 
bao nhiêu phần bởi biểu diễn phẳng của đồ thị G?
 Giải. Do mỗi đỉnh của đồ thị đều có bậc là 3, nên tổng 
bậc của các đỉnh là 3x20=60. Từ đó suy ra số cạnh của 
đồ thị |E|=60/2=30. Vì vậy, theo công thức Euler, số 
miền cần tìm là 
|R|=30-20+2=12.
MA TRẬN KỀ
 Xét đơn đồ thị vô hướng G=(V,E), với tập đỉnh V={ 1, 
2,. . . ,n} , tập cạnh E={ e1, e2,. . .,em} . Ta gọi ma trận kề 
của đồ thị G là ma trận vuông.
 A={ ai,j : i,j=1, 2,. . . ,n}
 Với các phần tử được xác định theo qui tắc sau đây:
Ví dụ ma trận kề
Lưu ý rằng ma trận kề của đồ thị có 
hướng không phải là ma trận đối xứng.
Ví dụ ma trận kề
TÍNH CHẤT MA TRẬN KỀ
 Các tính chất của ma trận kề:
 1) Rõ ràng ma trận kề của đồ thị vô hướng là ma trận 
đối xứng, tức là
 a[i,j]=a[j,i], i,j=1,2,. . .,n.
 2) Tổng các phần từ trên dòng i (cột j) của ma trận kề 
chính bằng bậc của đỉnh i (đỉnh j).
 Ma trận kề của đồ thị có hướng được định nghĩa một 
cách hoàn toàn tương tự.
MA TRẬN TRỌNG SỐ
 Trong rất nhiều vấn đề ứng dụng của lý thuyết đồ thị, 
mỗi cạnh e=(u,v) của đồ thị được gán với một con số 
a(e) [còn viết là a(u,v)] gọi là trọng số của cạnh e. Đồ 
thị trong trường hợp như vậy được gọi là đồ thị có 
trọng số. Trong trường hợp đồ thị có trọng số, thay vì 
mà trận kề, để biểu diễn đồ thị ta sử dụng ma trận 
trọng số.
MA TRẬN TRỌNG SỐ
Hết chương