Bài giảng Toán rời rạc và lý thuyết đồ thị - Chương 5: Đường đi trên đồ thị - Võ Tấn Dũng

Company L/O/G/O
Chương 5
ĐƯỜNG ĐI TRÊN
ĐỒ THỊ
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
MỞ ĐẦU
Bài toán về những cây cầu ở Konigsber
Năm 1736 Euler, cha đẻ của lý thuyết đồ thị, đã giải 
được bài toán hóc búa nổi tiếng thời đó về những cây 
cầu ở Konigberg.
Thành phố Königsberg, Đức (nay là Kaliningrad, Nga) 
nằm trên sông Pregel, bao gồm 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. 
Câu hỏi đặ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 2
3
4
Euler đã chứng minh rằng bài toán không có lời giải
bằng ngôn ngữ đồ thị. Ông biểu diễn 2 hòn đảo và 2 
bờ sông bằng 4 điểm và 7 cây cầu bằng các cạnh nối 
các điểm như sau: 
Việc đi qua 7 cây cầu tương 
đương với việc vẽ đồ thị trên 
bằng 1 nét.
Sau này ta sẽ thấy đồ thị trên không thể vẽ bằng 1 nét.
1 2
3
4
ĐỒ THỊ EULER
Định nghĩa
Cho đồ thị vô hướng G = (V, E)
 Đường đi Euler: Đường đi đơn trong G đi qua mọi 
cạnh của nó, mỗi cạnh chỉ đi qua một lần được gọi là 
đường đi Euler
 Chu trình Euler: Chu trình đơn trong đồ thị G đi 
qua mọi cạnh của nó, mỗi cạnh chỉ đi qua một lần 
được gọi là chu trình Euler. 
Cho đồ thị có hướng G = (V, E)
 Đường đi có hướng Euler là đường đi đơn có
hướng qua mọi cạnh của đồ thị.
 Chu trình có hướng Euler là chu trình đơn có
hướng qua mọi cạnh đồ thị.
Đồ thị chứa chu trình Euler gọi là đồ thị Euler
Ví dụ
a
b c
d
e f
Đồ thị Euler
Chu trình Euler: a, b, c, f, e, b, d, c, a
Ví dụ
Đồ thị về 7 cây cầu của thành phố Konigsberg
1 2
3
4
Không có chu trình và đường đi Euler
 Thí dụ: Đồ thị G1 trong hình 1 là đồ thị Euler vì nó có chu trình Euler a, e, c, d, e, b, a. Đồ thị 
G3 không có chu trình Euler nhưng nó có đường đi Euler a, c, d, e, b, d, a, b, vì thế G3 là đồ 
thị cửa Euler. Đồ thị G2 không có chu trình cũng như đường đi Euler.
Đồ thị G1, G2, G3
 Điều kiện cần và đủ để một đồ thị là một đồ thị Euler được Euler tìm ra 
vào năm 1736 khi ông giải quyết bài toán hóc búa nổi tiếng thế giới 
thời đó về bảy cái cầu ở thành phố Konigsberg và đây là định lý đầu 
tiên của lý thuyết đồ thị.
Điều kiện cần và đủ để đồ thị có chu trình 
và đường đi Euler
 Đồ thị G có đường đi Euler khi và chỉ khi G liên 
thông và có không quá 2 đỉnh bậc lẻ.
 Đồ thị G có chu trình Euler khi và chỉ khi G liên 
thông và mọi đỉnh đều có bậc (chẵn khác 0). 
Đồ thị vô hướng:
 Đồ thị có hướng G có chu trình có hướng Euler 
khi và chỉ khi G liên thông mạnh và mọi đỉnh đều 
có nửa bậc ra bằng nửa bậc vào.
Chú thích:
Đồ thị liên thông mạnh là đồ thị có hướng mà 
mọi cặp đỉnh của nó đều có đường đi có hướng nối 
chúng với nhau.
Đồ thị có hướng:
dv(v) = dr(v)
Ví dụ
Đồ thị nào sau đây có chu trình Euler? Nếu không, 
liệu có đường đi Euler không?
a
b c
ed
a b c
def
a
b
c
d
e
Đồ thị nào sau đây có chu trình có hướng Euler? 
Nếu không, liệu có đường đi có hướng Euler không?
Ví dụ
a b
cd
a
b
c
d
e
f
ĐỒ THỊ HAMINTON
Định nghĩa Cho đồ thị G = (V, E)
 Đường đi Haminton là đường đi qua tất cả các 
đỉnh của đồ thị mỗi đỉnh đúng một lần được gọi là 
đường đi Hamilton. 
 Chu trình Hamintơn là chu trình bắt đầu từ một 
đỉnh v nào đó qua tất cả các đỉnh còn lại mỗi đỉnh 
đúng một lần rồi quay trở về v được gọi là chu trình 
Hamilton.
Đồ thị chứa chu trình Hamintơn gọi là đồ thị Hamintơn
Định nghĩa tương tự đối với đồ thị có hướng
Ví dụ
Cho đồ thị:
e
d c
ba
f
g
Đồ thị trên không có chu trình và đường đi Euler 
nhưng có chu trình Hamintơn.
Đồ thị Hamintơn
Chu trình Hamintơn có độ dài bằng số đỉnh và mọi 
đường đi Hamintơn có độ dài bằng số cạnh.
Chú ý
Xét đồ thị:
a
b
c
de
Đồ thị trên có chu trình Hamintơn không? Vì sao?
Định lý (Dirak). Đơn đồ thị vô hướng G với n>2 
đỉnh, mỗi đỉnh có bậc không nhỏ hơn n/2 là đồ thị 
Hamilton.
Đồ thị Hamilton G3, đường đi Hamilton 
trong G2 , và G1.
Cho G là đơn đồ thị n đỉnh (n 3). Nếu:
Gv,
2
n
)v(d  
thì G có chu trình Hamintơn
Cho G là đơn đồ thị n đỉnh (n 3). Nếu:
Gv,
2
1n
)v(d 
thì G có chu trình Hamintơn
Định lí 1
Định lí 2
Định lí 3
Nếu G là đồ thị có hướng liên thông mạnh và:
Gv,
2
n
)v(d&
2
n
)v(d vr  
thì G có chu trình có hướng Hamintơn
Ví dụ
Các đồ thị sau có chu trình hay đường đi Hamintơn 
không? Nếu có hãy chỉ ra chu trình hay đường đi 
Hamintơn. 
1 2 3
456
78
a.
1 2 3 4 5
67
8
11 12 13 14 15
910
b.
TÌM ĐƯỜNG ĐI NGẮN NHẤT
4.5.1 Đồ thị có trọng số:
Là đồ thị mà mỗi cạnh của nó được gán 1 số.
Trong đồ thị có trọng số, độ dài trọng số của 
đường đi  là tổng các trọng số trên đường đi đó.
4.5.2 Phát biểu bài toán:
Cho đồ thị có trọng số G = (V, E). Tìm đường đi 
ngắn nhất từ đỉnh a đến đỉnh z của đồ thị
Thuật toán Dijkstra:
Tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z trong
đồ thị có trọng số. Trọng số của cạnh (i,j) là w(i,j) > 0
và đỉnh x sẽ mang nhãn L(x). Khi kết thúc thuật giải
L(z) chính là chiều dài đường đi ngắn nhất từ a đến z.
Đầu vào: Đồ thị liên thông G = (V, E) có trọng số 
w(i, j) > 0 với mọi cạnh (i, j), đỉnh a và đỉnh z.
Đầu ra: Chiều dài đường đi ngắn nhất và đường đi 
ngắn nhất.
Phương pháp:
(1) Gán L(a)  0. Với mọi đỉnh x a gán L(x) = . 
Kí hiệu T  V
(2) Chọn v T sao cho L(v) có giá trị nhỏ nhất. Đặt:
T  T – {v}
(3) Nếu z T Kết thúc.
L(z) là đường đi ngắn nhất từ a đến z. Từ z lần ngược 
theo các đỉnh được ghi nhớ ta có đường đi ngắn nhất. 
Ngược lại sang bước 4.
(4) Với mỗi x T kề với v gán:
L(x)  min{L(x), L(v) + w(v, x)}
Nếu L(x) này thay đổi thì ghi nhớ đỉnh v cạnh x 
để sau này xây dựng đường đi ngắn nhất.
Quay về bước 2.
Ví dụ:
Tìm đường đi ngắn nhất từ đỉnh a đến z trong đồ 
thị sau:
a
f
ed
cb
g
z
2
1
2
14 3
4
2
67
5
3
Ví dụ trên đồ thị vô hướng
Nguồn: ThS. Trịnh Thanh Đèo 28
Ví dụ trên đồ thị có hướng
Nguồn: ThS. Trịnh Thanh Đèo 29
Hết chương