Bài giảng Toán tổ hợp - Chương 6: Các bài toán về đường đi - Nguyễn Anh Thi

CÁC BÀI TOÁN VỀ ĐƯỜNG ĐI 
Chương 6 
2 
1. Tìm đường đi ngắn nhất 
2. Đồ thị Euler 
3. Đồ thị Hamilton 
Nội dung 
3 
1. TÌM ĐƯỜNG ĐI NGẮN 
NHẤT 
4 
Định nghĩa. Cho G = (V,E) là đồ thị có trọng số. Với 
H G thì trọng lượng của H là tổng trọng lượng của 
các cạnh của H. 
 Nếu H là đường đi, chu trình, mạch thì w(H) được 
gọi là độ dài của H. 
 Nếu mạch H có độ dài âm thì H được gọi là mạch 
âm. 
 Khoảng cách giữa 2 đỉnh u và v là độ dài ngắn 
nhất của các đường đi từ u đến v. 
(H) ( )
e H
w w e
 
Định nghĩa 
5 
Định nghĩa. Cho đồ thị G = (V, E), V = {v1,v2,,vn} 
có trọng số. Ma trận khoảng cách của G là ma 
trận D= (dij) xác định như sau: 
0
( )ij i j i j
i j
khi i j
d w v v khi v v E
khi v v E
Nhận xét. Mọi đồ thị được hoàn toàn xác định bởi 
ma trận khoảng cách. 
Ma trận khoảng cách 
6 
0 5 31 40
0 27 73
26 0 8 49 25 38
0 16
70 0 9
23 0 12
10 0
D
Ví dụ. Tìm ma trận khoảng 
cách của đồ thị sau 
7 
Ví dụ. Tìm đồ thị có ma trận khoảng cách sau: 
0 12 7 5
12 0 15 16 6
7 15 0 10
5 16 0 5
6 10 5 0
Đáp án. 
C 
A B 
D 
E 
12 
7 
15 
6 
5 
5 
10 
16 
8 
Bài toán. Cho G = (V, E) là đồ thị có trọng số. Tìm 
đường đi ngắn nhất từ u đến v và tính khoảng cách 
d(u ,v). 
Nhận xét. Nếu đồ thị G có mạch âm  trên một 
đường đi từ u tới v thì đường đi ngắn nhất từ u đến v 
sẽ không tồn tại. 
u v 
 
9 
Khi tìm đường đi ngắn nhất ta có thể bỏ bớt đi các 
cạnh song song và chỉ để lại một cạnh có trọng 
lượng nhỏ nhất. 
Đối với các khuyên có trọng lượng không âm thì 
cũng có thể bỏ đi mà không làm ảnh hưởng đến kết 
quả của bài toán. 
Đối với các khuyên có trọng lượng âm thì có thể 
đưa đến bài toán tìm đường đi ngắn nhất không có 
lời giải. 
Một số lưu ý 
10 
Gọi P là đường đi ngắn nhất từ đỉnh u đến đỉnh v; t 
P. Giả sử P=P1P2 với P1 là đường đi con của P từ u 
đến t và P2 là đường đi con của P từ t đến v. Khi đó 
P1 cũng là đường đi ngắn nhất từ u đến t. 
w(P1’) < w(P1) w(P1’P2) < w(P1P2)=w(P) 
u v 
t 
P1 
P1
’ 
P2 
Nguyên lý Bellman 
Chứng minh. Giả sử tồn tại P1
’ là đường đi ngắn hơn 
P1
 ta có 
Vô lý vì P là đường đi ngắn nhất từ u đến v 
11 
Để tìm đường đi ngắn nhất, chúng ta quan tâm tới 
hai thuật toán: 
 Thuật toán Dijkstra không thể thực hiện khi đồ thị 
có cạnh âm 
 Thuật toán Ford – Bellman xác định các mạch 
(chu trình) âm hay trả về cây đường đi ngắn nhất 
Thuật toán tìm đường đi ngắn nhất 
12 
Thuật toán Dijkstra 
Xác định tuần tự các đỉnh có khoảng cách đến u0 từ nhỏ 
đến lớn. 
 Trước tiên đỉnh có khoảng cách nhỏ nhất đến u0 là u0. 
 Trong V\{u0} tìm đỉnh có khoảng cách đến u0 nhỏ nhất 
(đỉnh này phải là một trong các đỉnh kề với u0) giả sử 
đó là u1 
 Trong V\{u0,u1} tìm đỉnh có khoảng cách đến u0 nhỏ 
nhất (đỉnh này phải là một trong các đỉnh kề với u0 
hoặc u1) giả sử đó là u2
13 
Tiếp tục như trên cho đến bao giờ tìm được khoảng 
cách từ u0 đến mọi đỉnh. 
Nếu G có n đỉnh thì: 
 0 = d(u0,u0) < d(u0,u1) d(u0,u2)  d(u0,un-1) 
14 
Bước 1. i:=0, S:=V\{u0}, L(u0):=0, L(v):= với mọi v S 
và đánh dấu đỉnh v bởi ( ,-). Nếu n=1 thì dừng và xuất 
d(u0,u0)=0=L(u0) 
Bước 2. Với mọi v S và kề với ui (nếu đồ thị có hướng 
thì v là đỉnh sau của ui), đặt 
 L(v):= min{ L(v), L(ui)+w(ui v)}. 
Xác định k= min L(v) , v S. 
Nếu k= L(vj) thì xuất d(u0,vj )= k và đánh dấu đỉnh vj bởi 
(k; ui). Đặt ui+1:= vj và S:=S\{ui+1} 
Bước 3. i:=i+1. Nếu i = n-1 thì kết thúc. 
Nếu không thì quay lại Bước 2 
Thuật toán Dijkstra 
15 
Bài tập 1. Tìm đường đi ngắn nhất từ u đến các đỉnh 
còn lại. 
7 
1 
3 
5 3 
1 
2 
3 
3 
1 
4 
u 
r 
s 
x 
w 
z y 
t 
4 
Một số ví dụ 
u r s t x y z w 
0* ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) 
- (4,u0) ( ,-) ( ,-) ( ,-) (1,u0)* ( ,-) ( ,-) 
- (3,y)* ( ,-) ( ,-) ( ,-) - (4,y) ( ,-) 
7 
1 
3 
5 3 
1 
2 
3 
3 
1 
4 
u 
r 
s 
x 
w 
z 
y 
t 
4 
7 
1 
3 
5 3 
1 
2 
3 3 
1 
4 
u 
r s 
x 
w z y 
t 
4 
u r s t x y z w 
0* ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) 
- (4,u0) ( ,-) ( ,-) ( ,-) (1u0)* ( ,-) ( ,-) 
- (3,y)* ( ,-) ( ,-) ( ,-) - (4,y) ( ,-) 
- - (10,r) (6,r) ( ,-) - (4,y)* ( ,-) 
- - (10,r) (6,r)* ( ,-) - - (9,z) 
- - (9,t) - (7,t)* - - (9,z) 
- - (8,x)* - - - - (9,z) 
- - - - - - - (9,z)* 
18 
Cây đường đi 
u 
y z 
w 
r 
t x 
s 
1 
2 
3 
1 
1 
3 5 
Ví dụ. Cho đồ thị có trọng số G = (V, E), V = { v1, v2, v3, 
v4, v5, v6, v7} xác định bởi ma trận trọng số D. Dùng 
thuật toán Dijkstra tìm đường đi ngắn nhất từ v1 đến 
các đỉnh v2, v3, v4, v5, v6, v7 
0 5 31 40
0 27 73
26 0 8 49 25 38
0 16
70 0 9
23 0 12
10 0
D
20 
21 
v1 v2 v3 v4 v5 v6 v7 
0* ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) 
- (5,v1)* (31,v1) (40,v1) ( ,-) ( ,-) ( ,-) 
- - (31,v1)* (40,v1) (78,v2) ( ,-) ( ,-) 
- - - (39,v3)* (78,v2) (56,v3) (69,v3) 
- - - - (78,v2) (55,v4)* (69,v3) 
- - - - (78,v2) - (67,v6)* 
- - - - (77,v7) - - 
22 
Cây đường đi 
23 
Ví dụ. Dùng thuật toán Dijsktra để tìm đường đi ngắn 
nhất từ đỉnh a đến đỉnh z. 
a b c d e f g z 
0* ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) 
- (4,a) (3,a)* ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) 
- (4,a)* - (6,c) (9,c) ( ,-) ( ,-) ( ,-) 
- - - (6,c)* (9,c) ( ,-) ( ,-) ( ,-) 
- - - - (7,d)* (11,d) ( ,-) ( ,-) 
- - - - - (11,d)* (12,e ) ( ,-) 
- - - - - - (12,e )* (18,f ) 
- - - - - - - (16,g )* 
e 
3 
b 5 
c 
d f 
z 
5 
4 
a 
4 
3 
1 
g 
Cây đường đi 
26 
Tìm đường đi ngắn nhất từ u0 đến các đỉnh khác 
hoặc chỉ ra đồ thị có mạch âm. 
Bước 1. L0(u0) =0 và L0(v) =  v u0. Đánh dấu 
đỉnh v bằng ( ,-) ; k=1. 
Bước 2. Lk(u0) = 0 và 
 Lk(v) = min { Lk-1(u)+w(uv) | u là đỉnh trước của v } 
Nếu Lk(v) = Lk-1(t)+w(tv) thì đánh dấu đỉnh v bởi 
(Lk(v),t) 
Bước 3. Nếu Lk(v) =Lk-1(v) với mọi v, tức Lk(v) ổn 
định thì dừng. Ngược lại đến bước 4. 
Thuật toán Ford - Bellman 
27 
Bước 4. Nếu k = n thì dừng, kết luận G có mạch 
âm. Nếu k n-1 thì trở về bước 2 với k:=k+1 
 Ví dụ. Dùng thuật toán Ford-Bellman để tìm đường đi 
ngắn nhất từ 1 cho đến các đỉnh còn lại 
1 
2 3 
6 
4 5 
7 
4 
2 
1 
8 
2 2 -2 
3 
2 
1 
2 3 
6 
4 5 
7 
4 
2 
1 
8 
2 2 -2 
3 
2 
k 1 2 3 4 5 6 
0 0 ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) 
1 0 (7,1) ( ,-) (8,1) ( ,-) ( ,-) 
2 0 (7,1) (11,2) (8,1) (9,2) (8,2) 
3 0 (7,1) (10,6) (6,6) (9,2) (8,2) 
4 0 (7,1) (10,6) (6,6) (8,4) (8,2) 
5 0 (7,1) (10,6) (6,6) (8,4) (8,2) 
29 
1 
2 3 
6 
4 5 
7 2 1 
-2 
2 
4 0 (7,1) (10,6) (6,6) (8,4) (8,2) 
5 0 (7,1) (10,6) (6,6) (8,4) (8,2) 
Ta có Lk(i) ổn định nên cây đường đi là 
30 
1 
2 3 
6 
4 5 
7 
4 
2 
1 
8 
2 2 -6 
3 
2 
 Ví dụ. Dùng thuật toán để tìm đường đi ngắn nhất từ 
1 cho đến các đỉnh còn lại 
1 
2 3 
6 
4 5 
7 
4 
2 
1 
8 
2 2 -6 
3 
2 
k 1 2 3 4 5 6 
0 0 ( ,-) ( ,-) ( ,-) ( ,-) ( ,-) 
2 0 (7,1) (11,2) (8,1) (9,2) (8,2) 
1 0 (7,1) ( ,-) (8,1) ( ,-) ( ,-) 
3 0 (7,1) (10,6) (2,6) (9,2) (8,2) 
4 0 (4,4) (10,6) (2,6) (4,4) (8,2) 
5 0 (4,4) (8,2) (2,6) (4,4) (5,2) 
6 0 (4,4) (7,6) (-1,6) (4,4) (5,2) 
32 
k = n = 6 . Lk(i) chưa ổn định nên đồ thị có mạch 
âm. Chẳng hạn: 
 4→2→6→4 có độ dài -3 
5 0 (4,4) (8,2) (2,6) (4,4) (5,2) 
6 0 (4,4) (7,6) (-1,6) (4,4) (5,2) 
33 
1 
1 
2 
-2 
3 
2 
4 
8 
5 
6 5 
1 
4 
-1 
2 
Ví dụ. Tìm đường đi ngắn 
nhất từ đỉnh 
a) 1 đến các đỉnh còn lại 
b) 3 đến các đỉnh còn lại 
34 
2. ĐỒ THỊ EULER 
35 
ĐỒ THỊ EULER 
Leonhard Euler 
(1707 – 1783) 
Giới thiệu 
36 
Thành phố Konigsberg (Đức) bị chia thành 4 vùng do 
2 nhánh của 1 dòng sông. Có 7 chiếc cầu nối những 
vùng nầy với nhau. 
Bài toán: Xuất phát từ một vùng đi dạo qua mỗi 
chiếc cầu đúng một lần và trở về nơi xuất phát. 
Năm 1736, nhà toán học Euler đã mô hình bài toán 
nầy bằng một đồ thị vô hướng với mỗi đỉnh ứng với 
một vùng, mỗi cạnh ứng với một chiếc cầu 
37 
A 
B 
C 
D 
C 
A 
D 
B 
38 
Đường đi Euler là đường đi qua tất cả các cạnh của 
đồ thị, mỗi cạnh đúng một lần. 
Chu trình Euler đường đi Euler có đỉnh đầu trùng với 
đỉnh cuối. 
Đồ thị Euler là đồ thị có chứa một chu trình Euler. 
Định nghĩa 
Có đường đi Euler 
là 4 3 0 1 2 0 
Có chu trình Euler 
là 4 3 0 1 2 0 4 
39 
Cho G=(X, E) là đô thị vô hướng liên thông. Khi đó 
a) G là đồ thị Euler Tất cả các cạnh của đồ G đều 
có bậc chẵn. 
b) G có đường đi Euler và không có chu trình Euler 
 G có đúng hai đỉnh bậc lẻ. 
Định lý Euler 
Nhận xét. Nếu G là đồ thị vô hướng liên thông chỉ có 
2k đỉnh bậc lẻ thì ta có thể vẽ đồ thị bằng k nét. 
40 
Cho G=(X, E) là đô thị có hướng liên thông mạnh. 
Khi đó 
a) G là đồ thị Euler d+(x)=d-(x) x X. 
b) G có đường đi Euler G có 2 đỉnh u, v sao cho: 
 deg (u) = deg (u) + 1 
 deg (v) = deg (v) + 1 
 d+(x)=d-(x) với mọi x khác u và v 
Định lý Euler 
41 
a 
b c 
d 
e 
a 
b c 
d 
a 
b c 
d 
e 
(G1) (G2) (G3) 
Liên thông và có 2 
đỉnh bậc lẻ có 
đường đi Euler: 
 bacdaedbc 
Liên thông và các 
đỉnh đều có bậc 
chẵn. Suy ra có chu 
trình Euler: 
 bacdaedbcb 
Có đường đi Euler: 
bacbd 
Ví dụ 
42 
Dùng để tìm chu trình Euler của đồ thị từ một đỉnh bất 
kỳ, ta áp dụng 2 quy tắc sau: 
Quy tắc 1. Xóa các cạnh đã đi qua và các đỉnh cô lập 
nếu có 
Quy tắc 2. Không bao giờ đi qua một cầu trừ khi 
không còn cách đi nào khác. 
Thuật toán Fleurey 
43 
a b 
c 
d 
e 
f g h 
43 
Ví dụ. Đồ thị sau có là đồ thị Euler không. Nếu có, 
hãy tìm một chu trình Euler 
Đáp án. Chu trình Euler là: 
 a b c f d c e f g h b g a 
44 
Ví dụ. Đồ thị sau có chu trình hay đường đi Euler 
không? Nếu có, hãy xác định chúng 
45 
Ví dụ. Đồ thị sau có là đồ thị Euler không. Nếu có, 
hãy tìm một chu trình Euler 
46 
3. ĐỒ THỊ HAMILTON 
47 
Sir William Rowan Hamilton 
(1805-1865) 
Năm 1857 W. R. Hamilton đưa trò chơi sau đây: Trên 
mỗi đỉnh trong số 20 đỉnh của khối đa diện ngũ giác đều 
12 mặt ghi tên một thành phố trên thế giới. Hãy tìm 
cách đi bằng các cạnh của khối đa diện để qua tất cả 
các thành phố, mỗi thành phố đúng một lần, sau đó trở 
về điểm xuất phát. 
Giới thiệu 
48 
49 
 Tổ chức tour du lịch sao cho người du lịch thăm 
quan mỗi thắng cảnh trong thành phố đúng một lần 
 Bài toán mã đi tuần: Cho con mã đi trên bàn cờ 
vua sao cho nó đi qua mỗi ô đúng một lần. 
 Đường Hamilton biểu diễn nước đi của con mã trên bàn cờ 3x4 
1 2 3 4 
5 6 7 8 
9 10 11 12 
H = [ 8, 10, 1, 7, 9, 2, 11, 5, 3, 12, 6, 4 ] 
Một số bài toán 
50 
Định nghĩa. Đường đi Hamilton là đường đi qua tất 
cả các đỉnh của đồ thị mỗi đỉnh đúng một lần. 
a. Định nghĩa tương tự cho chu trình Hamilton 
b. Đồ thi gọi là đồ thị Hamilton nếu nó có chu trình 
Hamilton 
G1 có đường đi và 
chu trình Hamilton 
G2 có đường đi 
nhưng không có 
chu trình Hamilton 
G3 không có đường đi 
và không có chu trình 
Hamilton 
Định nghĩa 
51 
Định lý. Cho G =(V,E) là đồ thị đơn vô hướng cón n 
 3 đỉnh. Khi đó 
 Nếu với u và v là hai đỉnh 
không kề nhau tuỳ ý thì G là Hamilton. 
 Nếu với mọi đỉnh u thì G là Hamilton 
deg(u) deg(v) n 
deg(u)
2
n
Ví dụ. Đây là đồ thị Hamilton? 
Một số điều kiện đủ 
52 
Quy tắc để xây dựng một chu trình Hamilton H hoặc chỉ 
ra đồ thị vô hướng không là Hamilton 
Quy tắc 1. Tất cả các cạnh kề với đỉnh bậc 2 phải ở 
trong H. 
Quy tắc 2. Không có chu trình con nào được tạo thành 
trong quá trình xây dựng H. 
Quy tắc 3. Khi chu trình Hamilton mà ta đang xây dựng 
đi qua đỉnh i thì xoá tất cả các cạnh kề với i mà ta chưa 
dùng. Điều này lại có thể cho ta một số đỉnh bậc 2 và ta 
lại dùng quy tắc 1. 
Quy tắc 4. Không có đỉnh cô lập hay cạnh treo nào 
được tạo nên sau khi áp dụng quy tắc 3. 
Quy tắc xây dựng chu trình Hamilton 
53 
Ví dụ. Đồ thị sau có phải là đồ thị Hamilton không? 
Nếu có hãy tìm chu trình Hamilton 
Đáp án. Có, ví dụ a, b, c, e, f, i, h, g, d, a. 
Một số ví dụ 
54 
Ví dụ. Đồ thị sau có phải là đồ thị Hamilton không? 
1 2 3 
4 5 6 
7 8 9 
Giải. Giả sử G có chu trình Hamilton H, theo quy tắc 
1, tất cả các cạnh kề với đỉnh bậc 2 đều ở trong H: 
 12, 14, 23, 36, 47, 78, 69, 89. 
Khi đó ta có chu trình con là: 1, 2, 3, 6, 9, 8, 7, 4, 1. 
Vậy G không là đồ thị Hamilton 
55 
Ví dụ. Đồ thị sau có phải là đồ thị Hamilton không? 
Nếu có hãy tìm chu trình Hamilton 
56 
Ví dụ. Đồ thị sau có phải là đồ thị Hamilton không?