Bài giảng Toán rời rạc & Lý thuyết đồ thị - Chương 5: Đường đi trên đồ thị

Chương 5. Đường đi trên đồ thị 
I. ĐƯỜNG ĐI VÀ CHU TRÌNH EULER 
Định nghĩa 1. 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. Đườ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. Đồ 
thị được gọi là đồ thị Euler nếu nó có chu trình Euler, và gọi là đồ thị nửa Euler 
nếu nó có đường đi Euler. 
Rõ ràng mọi đồ thị Euler luôn là nửa Euler, nhưng điều ngược lại không luôn 
đúng. 
Thí dụ 1. Đồ 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. 
Hình 1. Đồ thị G1, G2, G3 
Thí dụ 2. Đồ thị H2 trong hình 2 là đồ thị Euler vì nó có chu trình Euler a, b, 
c, d, e, a. Đồ thị H3 không có chu trình Euler nhưng nó có đường đi Euler c, a, 
b, c, d, b vì thế H3 là đồ thị nửa Euler. Đồ thị H1 không có chu trình cũng như 
đường đi Euler. 
Hình 2. Đồ thị H1, H2, H3 
Đ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ị. 
Định lý 1 (Euler). Đồ thị vô hướng liên thông G là đồ thị Euler khi và chỉ khi 
mọi đỉnh của G đều có bậc chẵn. 
Hệ quả. Đồ thị vô hướng liên thông G là nửa Euler khi và chỉ khi nó có không 
quá 2 đỉnh bậc lẻ. 
Định lý 2 (Euler tổng quát). Đồ thị vô hướng liên thông G có k đỉnh bậc lẻ (k 
luôn là số chẵn) thì cần ít nhất k/2 con đường để đi qua tất cả các cạnh của đồ 
thị, mỗi cạnh chỉ đi qua đúng 1 lần. Hơn nữa để đi được như vậy mỗi con 
đường cần xuất phát từ một đỉnh bậc lẻ và kết thúc ở một đỉnh bậc lẻ khác. 
Giả sử G là đồ thị Euler, thuật toán đơn giản sau đây cho phép xác định chu 
trình Euler khi làm bằng tay. 
Thuật toán Flor 
Xuất phát từ một đỉnh u nào đó của G ta đi theo các cạnh của nó một cách tuỳ ý 
chỉ cần tuân thủ 2 qui tắc sau: 
(1) Xoá bỏ cạnh đã đi qua đồng thời xoá bỏ cả những đỉnh cô lập tạo thành. 
(2) Ở mỗi bước ta chỉ đi qua cầu khi không còn cách lựa chon nào khác. 
Định lý 2. Đồ thị có hướng liên thông mạnh là đồ thị Euler khi và chỉ khi 
Deg+(v)=deg- (v),  v V. 
II. ĐƯỜNG ĐI VÀ CHU TRÌNH HAMILTON 
Trong mục này chúng ta xét bài toán tương tự như trong mục trước chỉ khác là 
ta quan tâm đến đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một 
lần. Sự thay đổi tưởng chừng như là không đáng kể này trên thực tế đã dẫn đến 
sự phức tạp hoá vấn đề cần giải quyết. 
Định nghĩa 2. Đườ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 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ị G được gọi là đồ thị Hamilton nếu nó chứa chu trình 
Hamilton và gọi là đồ thị nữa Hamilton nếu nó có đường đi Hamilton. 
Rõ ràng đồ thị Hamilton là nửa Hamilton, nhưng điều ngược lại không còn 
đúng. 
Thí dụ 3. Trong hình 4: G3 là Hamilton, G2 là nửa Hamilton còn G1 không là 
nửa Hamilton. 
 Hình 4. Đồ thị Hamilton G3, nửa Hamilton G2 , và G1. 
Cho đến nay việc tìm một tiêu chuẩn nhận biết đồ thị Hamilton vẫn còn là mở, 
mặc dù đây là một vấn đề trung tâm của lý thuyết đồ thị. Hơn thế nứa, cho đến 
nay cũng chưa có thuật toán hiệu quả để kiểm tra một đồ thị có là Hamilton hay 
không. Các kết quả thu được phần lớn là điều kiện đủ để một đồ thị là đồ thị 
Hamilton. Phần lớn chúng điều có dạng "nếu G có số cạnh đủ lớn thì G là 
Hamilton". Một kết quả như vậy được phát biểu trong định lý sau đây. 
Định lý 3 (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. 
Định lý sau là tổng quát hoá của định lý Dirak cho đồ thị có hướng: 
Định lý 4. Giả sử G là đồ có hướng liên thông với n đỉnh. Nếu deg+ (v)≥n/2, 
deg – (v) ≥ n/2,  v thì G là Hamilton. 
III.BÀI TOÁN ĐƯỜNG ĐI TỐT NHẤT 
 Trong các ứng dụng thực tế, bài toán tìm đường đi ngắn nhất giữa hai đỉnh của 
một đồ thị liên thông có một ý nghĩa to lớn. Có thể dẫn về bài toán như vậy 
nhiều bài toán thực tế quan trọng. Ví dụ, bài toán chọn một hành trình tiết kiệm 
nhất (theo tiêu chuẩn hoặc khoảng cách hoặc thời gian hoặc chi phí) trên một 
mạng giao thông đường bộ, đường thủy hoặc đường không; bài toán chọn một 
phương pháp tiết kiệm nhất để đưa ra một hệ thống động lực từ trạng thái xuất 
phát đến trạng một trạng thái đích, bài toán lập lịch thi công các công các công 
đoạn trong một công trình thi công lớn, bài toán lựa chọn đường truyền tin với 
chi phí nhỏ nhất trong mạng thông tin, v.v Hiện nay có rất nhiều phương 
pháp để giải các bài toán như vậy. Thế nhưng, thông thường, các thuật toán 
được xây dựng dựa trên cơ sở lý thuyết đồ thị tỏ ra là các thuật toán có hiệu 
quả cao nhất. Trong phần này chúng ta sẽ xét một số thuật toán như vậy. 
1. KHÁI NIỆM 
Trong phần này chúng ta xét đồ thị G =(V,E) có trọng số dương, nghĩa là, mỗi 
cạnh (u,v) E của nó được đặt tương ứng với một số thực dương a[u,v] gọi là 
trọng số của nó. Chúng ta sẽ đặt a[u,v] = , nếu không có cạnh (u,v). 
Nếu dãy v0, v1, . . ., vp là một đường đi trên G, thì độ dài của nó được 
định nghĩa là tổng sau 
 p 
a[vi-1, vi]. 
 i=1 
tức là, độ dài của đường đi chính là tổng của các trọng số trên các cung của nó. 
(Chú ý rằng nếu chúng ta gán trọng số cho tất cả cung đều bằng 1, thì ta thu 
được định nghĩa độ dài của đường đi như là số cung của đường đi phải đi qua). 
2. ĐƯỜNG ĐI NGẮN NHẤT XUẤT PHÁT TỪ MỘT ĐỈNH - THUẬT 
TOÁN DIJKSTRA 
Thuật toán Dijkstra tìm ra các đường đi tốt nhất xuất phát từ đỉnh s đến mỗi 
đỉnh v còn lại trên đồ thị G=(V,E), có ma trận trọng số với a[u,v] là trọng số 
cạnh (u,v). Việc tìm mỗi đường đi tốt nhất có hai vấn đề: 
 Tìm ra độ dài tốt nhất của đường đi. 
 Tìm ra lộ trình của đường đi. 
Ta sẽ dùng hai mảng để giải quyết hai vấn đề này. 
 Mảng d[v] để lưu trữ độ dài đường đi từ s đến v. 
 Mảng p[v] để lưu trữ đỉnh kế ngay trước đỉnh v trên con đường tốt nhất đi từ 
s đến v. (mảng này là cơ sở để xác định lộ trình tốt nhất đi từ s đến v) 
Bước khởi đầu: Với mỗi đỉnh v V, ta tạm xem đường đi từ s đến v là đi trực 
tiếp (tức không qua đỉnh trung gian nào). Các việc của bước khởi đầu gồm: 
 Đặt d[v] = a[s,v] 
 Đặt p[v] = s 
 Đánh dấu đã tìm ra đường đi tốt nhất cho đỉnh xuất phát s 
Bước lặp: Mỗi bước lặp tìm ra một đường đi tốt nhất từ đỉnh s đến đỉnh vmin 
(bước lặp kết thúc khi đã tìm ra đường đi tốt nhất tới mọi đỉnh). Các công việc 
của bước lặp gồm: 
 Tìm ra đỉnh vmin là đỉnh có d[vmin] nhỏ nhất trong các đỉnh chưa được đánh 
dấu đã tìm ra đường đi tốt nhất. 
 Đánh dấu đã tìm ra đường đi tốt nhất cho đỉnh vmin 
 Với mỗi đỉnh v chưa được đánh dấu đã tìm ra đường đi tốt nhất, và kề với 
vmin , thực hiện: 
Nếu d[v] > d[vmin] + a[vmin,v] thì 
o d[v]= d[vmin] + a[vmin,v] 
o p[v] = vmin 
Chú í: khi kết thúc thuật tóan thì với mỗi đỉnh v V 
1. Độ dài con đường tốt nhất từ s đến v là: d[v]. 
2. Lộ trình từ s đế v được xác định như sau: v <- p[v] <- p[p[v]] <-  <- s 
Ví dụ: Tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại của đồ thị sau. 
 Hình : Đồ thị và ma trận trọng số tương ứng của nó 
Kết quả tính toán theo thuật toán được trình bày theo bảng dưới đây. Qui ước 
viết hai thành phần trong cột theo thứ tự là: d[v],p[v] của đỉnh ứng với cột đó. 
Ở mỗi bước đỉnh được đánh dấu * là đỉnh vmin ở bước lặp đang xét. Ta đánh 
dấu - ở cột ứng với đỉnh đã tìm ra đường đi tốt nhất. 
Bước 
lặp 
Đỉnh 
1 
Đỉnh 
2 
Đỉnh 
3 
Đỉnh 
4 
Đỉnh 
5 
Đỉnh 
6 
Khởi 
tạo 
0,1 1,1* ,1 ,1 ,1 ,1 
1 - - 6,2 3,2* ,1 8,2 
2 - - 4,4* - 7,4 8,2 
3 - - - - 7,4 5,3* 
4 - - - - 6,6* - 
Từ bảng trên rút ra kết quả như sau: 
 1 2 3 4 5 6 
1 0 1 ∞ ∞ ∞ ∞ 
2 ∞ 0 5 2 ∞ 7 
3 ∞ ∞ 0 ∞ ∞ 1 
4 2 ∞ 1 0 4 ∞ 
5 ∞ ∞ ∞ 3 0 ∞ 
6 ∞ ∞ ∞ ∞ 1 0 
o Đường đi tốt nhất từ 1 đến 2 dài: 1 Lộ trình: 2 <- 1. 
o Đường đi tốt nhất từ 1 đến 3 dài: 4 Lộ trình: 3 <- 4 <- 2 <- 1. 
o Đường đi tốt nhất từ 1 đến 4 dài: 3 Lộ trình: 4 <- 2 <- 1. 
o Đường đi tốt nhất từ 1 đến 5 dài: 6 Lộ trình: 5 <- 6 <- 3 <- 4 <- 2 <- 1. 
o Đường đi tốt nhất từ 1 đến 6 dài: 5 Lộ trình: 6 <- 3 <- 4 <- 2 <- 1. 
Chú ý: Nếu chỉ cần tìm đường đi ngắn nhất từ s đến một đỉnh t nào đó thì có 
thể kết thúc thuật toán khi đỉnh t đã đuợc đánh dấu tìm ra đường đi ngắn nhất. 
BÀI TẬP. 
Bài 1: Một nét vẽ là một lần đặt bút xuống vẽ cho đến khi nhấc bút lên. Để vẽ 
hình sau phải cần ít nhất bao nhiêu nét vẽ, giải thích, chỉ ra cách vẽ. 
Bài 2: 
Cho đơn đồ thị có trọng số G=(V,E) có ma trận trọng số như sau (dấu - là 
giữa 2 đỉnh không có cạnh): 
 1 2 3 4 5 6 
1 0 - 2 7 1 - 
1 
2 3 
7 
4 
5 
8 
6 
10 
11 12 
9 
13 
17 
16 
14 
15 
2 - 0 1 4 - 2 
3 2 1 0 - 6 5 
4 7 4 - 0 3 5 
5 1 - 6 3 0 - 
6 - 2 5 5 - 0 
Vẽ đồ thi. Thể hiện sự hoạt động của thuật toán Dijkstra với đồ thị trên, để tìm 
đường đi ngắn nhất từ đỉnh 5 đến các đỉnh còn lại. Liệt kê các lộ trình này. 
Bài 3: 
Cho đơn đồ thị có hướng G=(V,E) có ma trận trọng số như sau (dấu - là giữa 
2 đỉnh không có cung): 
 1 2 3 4 5 6 7 
1 0 - 4 - - - 30 
2 5 0 10 - 16 - - 
3 - - 0 6 - - 27 
4 - - - 0 7 - 20 
5 - - - - 0 3 11 
6 - - - - - 0 7 
7 - - - - - - 0 
Vẽ đồ thị. Thể hiện sự hoạt động của thuật toán Dijkstra với đồ thị trên, để tìm 
đường đi ngắn nhất từ đỉnh 2 đến các đỉnh còn lại. Liệt kê các lộ trình này. 
Bài 4: 
Cho đơn đồ thị có hướng G=(V,E) có ma trận trọng số như sau (dấu - là giữa 
2 đỉnh không có cung): 
 1 2 3 4 5 6 
1 0 8 5 6 - - 
2 - 0 - - - 9 
3 - - 0 15 3 - 
4 - 1 - 0 - - 
5 4 - - - 0 4 
6 - 7 - 2 - 0 
Vẽ đồ thị. Thể hiện sự hoạt động của thuật toán Dijkstra với đồ thị trên, để tìm 
đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại. Liệt kê các lộ trình này. 
Bài 5: 
Cho đơn đồ thị có trọng số G=(V,E) như sau: 
Viết ma trận trọng số của nó. Thể hiện sự hoạt động của thuật toán Dijkstra với 
đồ thị trên, để tìm đường đi ngắn nhất từ E đến các đỉnh còn lại. Liệt kê các lộ 
trình này. 
4 
5 
2 
3 
2 
6 
1 
7 5 
1 
B 
D 
E 
A 
C 
F