Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Bài tập chương 9
Đường đi và chu trình
1 Dẫn nhập
Trong bài tập dưới đây, chúng ta sẽ làm quen với các lý thuyết liên quan tới đường đi và
chu trình. Sinh viên cần ôn lại các lý thuyết liên quan được trình trong chương 9, trước
khi làm bài tập bên dưới.
2 Bài tập mẫu
Đồ thị G
1
như hình bên dưới đây.
S
A
B
C
D
E
F
G
H
(G
1
)
10
10
14
11
6
8
5

• S → B → C → E
• S → B → C → F
• S → G
• S → G → H
✷
Câu 2.
Tìm đường đi ngắn nhất xuất phát từ S đến tất cả các đỉnh còn lại bằng thuật giải
Bellman-Ford trong đồ thị G
1
.
Lời giải.
i S A B C D E F G H
π(0) 0 +∞ +∞ +∞ +∞ +∞ +∞ +∞ +∞
π(1) 0 10 10 +∞ +∞ +∞ +∞ 14 +∞
π(2) 0 10 10 21 +∞ +∞ +∞ 14 +∞
π(3) 0 10 10 16 18 +∞ +∞ 14 +∞
π(4) 0 10 10 16 18 21 18 14 +∞
π(5) 0 10 10 16 18 21 18 14 25
π(6) 0 10 10 16 18 21 18 14 25
π(7) 0 10 10 16 18 21 18 14 20
Giáo trình Toán Rời Rạc 1 Trang 2/17
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Từ bảng trên, ta có thể xác đinh đường đi ngắn nhất từ A đến các đỉnh còn lại.
• S → A
• S → B
• S → B → C
• S → B → D
• S → B → C → E
• S → B → C → F

Khoa Khoa Học và Kỹ Thuật Máy Tính
k = 1 A B C D
A 0 2 6 +∞
B 1 0 4 +∞
C 5 4 0 2
D +∞ 3 1 0
k = 2 A B C D
A 0 2 6 +∞
B 1 0 4 +∞
C 5 4 0 2
D 4 3 1 0
k = 3 A B C D
A 0 2 6 8
B 1 0 4 6
C 5 4 0 2
D 4 3 1 0
k = 4 A B C D
A 0 2 6 8
B 1 0 4 6
C 5 4 0 2
D 4 3 1 0
✷
3 Bài tập cần giải
Câu 4.
Hãy xác định xem các đồ thị vô hướng sau (G
10
), (G
11
), (G
12

Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
G F E
A B C
D
(G
11
)
G F E
A B C
D
(G
12
)
Lời giải.
1. (G
10
)
• Chu trình Euler: không có, vì tồn tại đỉnh S có số bậc là lẻ (bằng 3).
• Đường đi Euler: không có, vì tồn tại 3 đỉnh S, B, H có số bệc là lẻ (đều bằng 3).
• Chi trình Hamilton: B → S → A → C → E → H → G → F → D → B.
• Đường đi Hamilton: S → A → C → B → D → F → E → H → G.
2. (G
11
)
• Chu trình Euler: All of the vertices have even degree except B (degree 3) and
D (degree 3). According to Euler’s Theorems, there is no Euler circuit for this
graph.
• Đường đi Euler: there is an Euler path, starting at one of the odd vertices and
ending at the other. B → A → G → F → A → D → C → F → E → C → B

(G
13
)
6
3
3
1
1
4
2
2
Câu 6.
Hãy dùng thuật giải Dijsktra để tìm đường đi ngắn nhất của đỉnh A đến một đỉnh bất kỳ
khác trong đồ thị G
3
như sau.
Lời giải. Dựa theo thuật giải Dijkstra, chúng ta cần xây dựng bảng sau.
Giáo trình Toán Rời Rạc 1 Trang 6/17
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
A
B
C
D
E
F
(G
3
)
4

Từ đỉnh C được chọn này có thể đi một bước đến các đỉnh D và F với trọng số là 6
Giáo trình Toán Rời Rạc 1 Trang 7/17
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
và 7. Do đó đường đi từ A → C đến D là 1 + 6 = 7 < +∞ => cập nhật lại +∞
thành 7 , từ A → C đến F là 1 + 7 = 8 < +∞, do đó cập nhật lại +∞ thành 8.
Cột nào đã được đánh dấu trước đó thì không cập nhật nữa, ví dụ số 0 ớ bước π(0).
• Bước π(2), chọn số nhỏ nhất (mà chưa từng được chọn) trong bước π(1) và π(0), ở
đây π(1) có 4, 1, 7, 8 trong đó 1 đã được đánh dấu do đó không tính. Chọn 4, đánh
dấu 4.
Chọn 4 tức là đang ở B, B có thể đi một bước đến E và D với trọng số lần lượt là 6
và 2. Do đó đường đi từ A → B đến D là 4 + 2 = 6 < 7 => cập nhật lại 7 thành 6
, từ A → B đến E là 4 + 6 = 10 < +∞, do đó cập nhật lại +∞ thành 10.
Tại sao biết là từ A → B ở bước này?
Backtracking, để track lại đường đi, đỉnh 4 ở đây đang là B ở π(2), từ chỗ này nhìn
thẳng lên thấy hàng nào B đổi số thì lùi xuống một hàng và gióng sang trái để biết
đi từ đỉnh nào đến B.
Ở đây từ 4 của π(2) nhìn thẳng lên π(1) và π(0), không thấy chỗ nào B đổi số, thì
nhìn vào hàng cuối là π(0), nhìn sang trái thấy số nào được đánh dấu (gạch dưới)
thì nghĩa là đi từ đỉnh đó đến B, ở đây ta thấy 0 bị gạch dưới tức là đi từ A đến B.
• Tại π(3):
Chọn số nhỏ nhất ở π(2) mà chưa bị gạch dưới, tức là 6 và là D, từ D có thể đi một
bước đến E và F với trọng số lần lượt là 2 và 4. Do đó đường đi từ A → B → D đến
E là 4 + 2 + 2 = 8 < 10, cập nhật lại tại E là 8. Đường đi từ A → B → D đến F
là 4 + 2 + 4 = 10 > 8, không cập nhật. Do đó π(3) là 6, 8, 8.
Tại sao biết track ở đây là A → B → D?
Backtracking: 6 được chọn tức là D, nhìn thẳng lên chỗ đổi số gần nhất là π(1) (tại
π(1), D có số 7, không phải số 6) thì lùi xuống một hàng là π(2), nhìn sang trái số
bị gạch dưới là 4, tức là B (vậy là B qua D), từ B này ở π(2), nhìn thẳng lên tìm chỗ
số bị đổi, không có thì chọn π(0), nhìn sang trái thấy A bị gạch dưới, tức là A qua

7
5
9
8
1
-3
2
2
5
8
1
-6
-4
10
3
Lời giải.
i A B C D E F G H
π(0) 0 +∞ +∞ +∞ +∞ +∞ +∞ +∞
π(1) 0 7 +∞ 5 +∞ +∞ 9 +∞
π(2) 0 7 15 5 +∞ +∞ 9 +∞
π(3) 0 7 15 5 17 +∞ 9 +∞
π(4) 0 7 15 5 7 +∞ 9 10
π(5) 0 7 15 5 7 15 9 8
π(6) 0 7 9 5 7 15 9 8
π(7) 0 7 9 5 7 15 9 8
Từ bảng trên, ta có thể xác đinh đường đi ngắn nhất từ A đến các đỉnh còn lại.
• A → B
• A → D → E → F → C
• A → D
• A → D → E

A → D → E → H = 8 < 10 => cập nhật lại.
Backtracking: Tương tự trong diễn giải Dijkstra. Tại sao biết là A → D → E ở đây?
Backtracking: Tương tự trong diễn giải Dijkstra. Từ E là số 7 ở π(5), nhìn thẳng lên
thấy đổi số ở π(3) (từ 7 sang 17), lùi xuống một hàng là π(4), nhìn sang trái thấy 5
bị gạch dưới là D, vậy là D → E .
Từ D là số 5 ở π(4), nhìn thẳng lên tìm hàng đổi số đầu tiên, ở đây là π(0), lùi
xuống 1 hàng là π(1), nhìn sang trái số bị gạch dưới là A (0). Do đó đường đi là
A → D → E.
Giáo trình Toán Rời Rạc 1 Trang 10/17
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
• Tại bước π(6), chọn F(15), do chọn từ trái sang phải. Từ F đi một bược tới được C
với trọng số là -6. Do đó A → D → E → F =→ C = 9 = 9 hiện tại => không có gì
thay đổi.
Backtracking: Tương tự trong diễn giải Dijkstra. Tại sao biết là A → D → E → F ở
đây?
Backtracking: Tương tự trong diễn giải Dijkstra. Từ F là số 15 ở π(6), nhìn thẳng
lên thấy đổi số ở π(4) (từ 15 sang +∞), lùi xuống một hàng là π(5), nhìn sang trái
thấy 7 bị gạch dưới là E, vậy là E → F .
Từ E là số 7 ở π(5), nhìn thẳng lên thấy đổi số ở π(3) (từ 7 sang 17), lùi xuống một
hàng là π(4), nhìn sang trái thấy 5 bị gạch dưới là D, vậy là D → E.
Từ D là số 5 ở π(4), nhìn thẳng lên tìm hàng đổi số đầu tiên, ở đây là π(0), lùi
xuống 1 hàng là π(1), nhìn sang trái số bị gạch dưới là A (0). Do đó đường đi là
A → D → E → F .
• Tại bước π(7), chọn G(9), do chọn từ trái sang phải. Từ G đi một bược tới được D
và H với trọng số là -4 và 10. Do đó A → G → D = 5 = 5 hiện tại => không có gì
thay đổi. A → G → H = 19 > 8 => không cập nhật
Backtracking: Tương tự trong diễn giải Dijkstra. Tại sao biết là A → G ở đây?
Backtracking: Tương tự trong diễn giải Dijkstra. Từ G là số 9 ở π(7), nhìn thẳng lên
thấy đổi số ở π(0) (từ 9 sang +∞), lùi xuống một hàng là π(1), nhìn sang trái thấy

7
Lời giải.
Giáo trình Toán Rời Rạc 1 Trang 11/17
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
k = 0 A B C D E F G H
A 0 8 +∞ 6 +∞ +∞ 7 +∞
B 3 0 2 1 +∞ +∞ +∞ +∞
C +∞ +∞ 0 +∞ 2 5 +∞ +∞
D +∞ +∞ +∞ 0 4 1 +∞ +∞
E +∞ +∞ +∞ +∞ 0 9 +∞ 1
F +∞ +∞ 4 +∞ +∞ +∞ 0 3
G 5 +∞ +∞ +∞ +∞ +∞ 0 4
H +∞ +∞ +∞ +∞ +∞ 7 +∞ 0
k = 1 A B C D E F G H
A 0 8 +∞ 6 +∞ +∞ 7 +∞
B 3 0 2 1 +∞ +∞ 10 +∞
C +∞ +∞ 0 +∞ 2 5 +∞ +∞
D +∞ +∞ +∞ 0 4 1 +∞ +∞
E +∞ +∞ +∞ +∞ 0 9 +∞ 1
F +∞ +∞ 4 +∞ +∞ 0 +∞ 3
G 5 13 +∞ 11 +∞ +∞ 0 4
H +∞ +∞ +∞ +∞ +∞ 7 +∞ 0
k = 2 A B C D E F G H
A 0 8 10 6 +∞ +∞ 7 +∞
B 3 0 2 1 +∞ +∞ 10 +∞
C +∞ +∞ 0 +∞ 2 5 +∞ +∞
D +∞ +∞ +∞ 0 4 1 +∞ +∞
E +∞ +∞ +∞ +∞ 0 9 +∞ 1
F +∞ +∞ 4 +∞ +∞ 0 +∞ 3

G 5 13 15 11 15 12 0 4
H +∞ +∞ +∞ +∞ +∞ 7 +∞ 0
k = 6 A B C D E F G H
A 0 8 10 6 10 7 7 10
B 3 0 2 1 4 2 10 5
C +∞ +∞ 0 +∞ 2 5 +∞ 3
D +∞ +∞ 5 0 4 1 +∞ 4
E +∞ +∞ 13 +∞ 0 9 +∞ 1
F +∞ +∞ 4 +∞ 6 0 +∞ 3
G 5 13 15 11 15 12 0 4
H +∞ +∞ 11 +∞ 13 7 +∞ 0
k = 7 A B C D E F G H
A 0 8 10 6 10 7 7 10
B 3 0 2 1 4 2 10 5
C +∞ +∞ 0 +∞ 2 5 +∞ 3
D +∞ +∞ 5 0 4 1 +∞ 4
E +∞ +∞ 13 +∞ 0 9 +∞ 1
F +∞ +∞ 4 +∞ 6 0 +∞ 3
G 5 13 15 11 15 12 0 4
H +∞ +∞ 11 +∞ 13 7 +∞ 0
Diễn giải
Giáo trình Toán Rời Rạc 1 Trang 13/17
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
• Lấy một ví dụ đơn giản để minh hoạ:
item Đầu tiên đánh index số cho các đỉnh, nếu là đỉnh chữ thì gán cho đỉnh một số
thứ tự index. Giải thuật sẽ duyệt qua các đỉnh có trong đồ thị.
item Bước k = 0, liệt kê hết tất cả các cạnh và trọng số, 1 bước đi. Cập nhật table
cho k = 0.
item Bước k = 1, chọn đỉnh có số thứ tự index bằng 1, liệt kê tất cả đường đi mà đỉnh

C có độ là A → B → C (độ dài là 14). Nếu tăng trọng số của mỗi cạnh bởi một hằng số
∆ = 2 thì đường đi ngắn nhất sẽ chuyển thành A → C (độ dài là 17). ✷
Giáo trình Toán Rời Rạc 1 Trang 14/17
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
Câu 10.
Liệu có thể dùng thuật giải Dijsktra để giải bài toán tìm đường đi ngắn nhất xuất phát từ
một đỉnh bất kỳ đến một đỉnh bất kỳ khác không ? Nếu có hãy minh họa bằng áp dụng
vào các đồ thị G
7
và G
8
.
Lời giải.Chỉ có thể dùng Dijkstra nếu đồ thị thỏa mãn điều kiện là không có cạnh với
trọng số âm. Với đội thị G
7
thì không thể áp dụng Dijkstra. Với G
8
thì ta có thể áp dụng
thuật toán với các đỉnh của đồ thị lần lượt là đỉnh xuất phát. ✷
4 Bài tập làm thêm
Câu 11.
Hãy thiết kế một giải thuật để đếm số đường đi ngắn nhất trong một đồ thị cho sẵn.
Lời giải. ✷
Câu 12.
a) Làm thế nào đếm được số đường đi khác nhau xuất phát từ một đỉnh u và đến một
đỉnh v trong một đồ thị G cho trước?
b) Hãy vẽ một đồ thị và minh họa việc đếm.
c) Liệu có tồn tại giải thuật đếm số đường đi có thể có từ u đến v không?
Lời giải. ✷

100
500
500
Giáo trình Toán Rời Rạc 1 Trang 16/17
Trường Đại Học Bách Khoa Tp.Hồ Chí Minh
Khoa Khoa Học và Kỹ Thuật Máy Tính
5 Tổng kết
Thông qua các bài tập trong phần này, chúng ta đã làm quen với lý thuyết về đường đi
và chu trình (tham khảo chi tiết lý thuyết trong chương 5). Và các bài tập này cũng đã
giúp chúng ta phần nào hiểu thêm về các ý tưởng, các hướng giải thuật để giải được vài
bài toán thực tế đơn giản chung quanh chúng ta.
Giáo trình Toán Rời Rạc 1 Trang 17/17