TRƯỜNG ĐẠI HỌC CẦN THƠ
KHOA SƯ PHẠM
*****************

CHUYÊN ĐỀ 4
LÀM QUEN VỚI MỘT SỐ YẾU TỐ
CỦA LÍ THUYẾT ĐỒ THỊ
NHÓM 3 :
Ngô Thảo Uyên

B1900382

Đỗ Nguyễn Như Ngọc B1900367
Dương Trọng Nghĩa

B2000219

Từ Văn Nghi Thức

B2007539

Giáo viên hướng dẫn :
Bùi Anh Tuấn

Cần Thơ , 25 tháng 4 năm 2022

MỤC LỤC
I. LÝ THUYẾT.............................................................................................................................. 1
1. Khái niệm đồ thị ................................................................................................................. 1
a) Định nghĩa đồ thị ............................................................................................................ 1
b) Một số khái niệm liên quan đến đồ thị ......................................................................... 1
2. Một số đồ thị đặc biệt......................................................................................................... 2
a) Đơn đồ thị........................................................................................................................ 2
b) Đa đồ thị .......................................................................................................................... 2
c) Đồ thị đầy đủ................................................................................................................... 2
d) Đồ thị lưỡng phân........................................................................................................... 3
e) Đồ thị lưỡng phân đầy đủ .............................................................................................. 3
3. Bậc của đỉnh ....................................................................................................................... 3
4. Đường đi, chu trình, tính liên thông ................................................................................. 4
a) Đường đi .......................................................................................................................... 4
b) Chu trình ......................................................................................................................... 5
c) Tính liên thông................................................................................................................ 5
5. Đồ thị Euler ........................................................................................................................ 6
6. Đồ thị Hamilton……………………………………………….…………………………………...6
II. CÁC DẠNG BÀI TẬP ............................................................................................................. 7
1. Thuật toán tìm đường đi Euler ......................................................................................... 7
a) Phương pháp................................................................................................................... 7
b) Ví dụ ................................................................................................................................ 7
2. Bài toán người đưa thư Trung Hoa.................................................................................. 8
a) Phương pháp................................................................................................................... 8
b) Ví dụ ................................................................................................................................ 9
3. Bài toán người bán hàng ................................................................................................... 9
a) Phương pháp: Sử dụng thuật toán láng giềng gần nhất ........................................... 10
b) Ví dụ .............................................................................................................................. 10
4. Bài toán tìm đường đi tối ưu (thuật toán)...................................................................... 11
❖ Thuật toán Dijkstra ....................................................................................................... 11
❖ Thuật toán Floyd-Warshall........................................................................................... 14
III. BÀI TẬP VẬN DỤNG ......................................................................................................... 15
IV. TÀI LIỆU THAM KHẢO ................................................................................................... 24

CHUYÊN ĐỀ 4: LÀM QUEN VỚI MỘT SỐ YẾU TỐ
CỦA LÝ THUYẾT ĐỒ THỊ
I. LÝ THUYẾT
1. Khái niệm đồ thị
a) Định nghĩa đồ thị
Một đồ thị 𝐺 là một bộ ba (𝑉(𝐺), 𝐸(𝐺), 𝜓𝐺 ) bao gồm một tập khác rỗng 𝑉(𝐺)
các đỉnh của 𝐺 , một tập 𝐸(𝐺) các cạnh của 𝐺 và một hàm liên thuộc 𝜓𝐺 đặt tương
ứng mỗi cạnh với một cặp đỉnh không theo thứ tự (hai đỉnh không nhất thiết phải
khác nhau). Nếu 𝑒 là một cạnh và 𝑢, 𝑣 là hai đỉnh sao cho 𝜓𝐺 (𝑒) = 𝑢𝑣, thì ta nói 𝑒
nối 𝑢 và 𝑣 ; các đỉnh 𝑢 và 𝑣 được gọi là các điểm đầu mút của 𝑒.
Ví dụ: Ta xét đồ thị 𝐺 = (𝑉(𝐺), 𝐸(𝐺), 𝜓𝐺 ) với 𝑉(𝐺) = {𝑣1 ; 𝑣2 ; 𝑣3 ; 𝑣4 } ; 𝐸(𝐺) =
{𝑒1 ; 𝑒2 ; 𝑒3 ; 𝑒4 ; 𝑒5 } và 𝜓𝐺 được xác định bởi 𝜓𝐺 (𝑒1 ) = 𝑣1 𝑣2 , 𝜓𝐺 (𝑒2 ) =
𝑣1 𝑣2 ; 𝜓𝐺 (𝑒3 ) = 𝑣2 𝑣3 ; 𝜓𝐺 (𝑒4 ) = 𝑣3 𝑣4 ; 𝜓𝐺 (𝑒5 ) = 𝑣4 𝑣4 . Hình 1.1 là một biểu diễn
hình học của đồ thị 𝐺.

b) Một số khái niệm liên quan đến đồ thị
Nếu 𝑢 là một điểm đầu mút của cạnh 𝑒 thì ta nói 𝑢 và 𝑒 liên thuộc với nhau.
Hai đỉnh liên thuộc với cùng một cạnh được gọi là hai đỉnh liền kề.
Hai cạnh (hai cung) liên thuộc với cùng một đỉnh được gọi là hai cạnh (hai cung)
liền kề.
Một cạnh (một cung) có hai điểm đầu mút trùng nhau được gọi là một vòng (hay
khuyên).
Hai hay nhiều cạnh (cung) mà có hai đầu mút giống nhau được gọi là các cạnh
song song hay còn được gọi là các cạnh bội.
Đồ thị hữu hạn là đồ thị có cả tập hợp cạnh và tập hợp đỉnh đều hữu hạn.
Đồ thị tầm thường là đồ thị chỉ có một đỉnh và không có cạnh.
Đồ thị rỗng là đồ thị không có cạnh.
Nếu mỗi phần tử 𝑒 = 𝑢𝑣 ∈ 𝐸 là không phân biệt thứ tự thì 𝐺 được gọi là một đồ
thị vô hướng.
1

Nếu mỗi phần tử 𝑒 = 𝑢𝑣 ∈ 𝐸 là phân biệt thứ tự 𝑢 trước 𝑣 sau thì 𝐺 được gọi là
một đồ thị có hướng.
2. Một số đồ thị đặc biệt
a) Đơn đồ thị
Đồ thị không có cạnh bội và không có khuyên được gọi là đơn đồ thị.

b) Đa đồ thị
Đồ thị tồn tại ít nhất một cạnh bội và không có khuyên được gọi là đa đồ thị.

c) Đồ thị đầy đủ
Đồ thị mà mọi cặp đỉnh của nó đều kề nhau được gọi là đồ thị đầy đủ. Đơn đồ thị
đầy đủ bao gồm n đỉnh được ký hiệu là 𝐾𝑛 .

2

d) Đồ thị lưỡng phân
Đồ thị 𝐺 = (𝑉1 ∪ 𝑉2 , 𝐸) với 𝑉1 , 𝑉2 là hai tập khác rỗng rời nhau, có mỗi cạnh là
một đỉnh của 𝑉1 tương ứng với một đỉnh của 𝑉2 được gọi là đồ thị lưỡng phân.

e) Đồ thị lưỡng phân đầy đủ
Đồ thị 𝐺 = (𝑉1 ∪ 𝑉2 , 𝐸) với 𝑉1 , 𝑉2 là hai tập khác rỗng rời nhau, có mỗi đỉnh của
𝑉1 đều kề với một đỉnh của 𝑉2 được gọi là đồ thị lưỡng phân đầy đủ.

Đồ thị lưỡng phân đầy đủ 𝑲𝟑,𝟑
3. Bậc của đỉnh
❖ Cho 𝐺 là một đồ thị vô hướng. Số cạnh tương ứng với một đỉnh 𝑢 được gọi là
bậc của đỉnh. Ký hiệu deg(𝑢) hoặc 𝑑𝐺 (𝑢).
Nếu đỉnh có bậc bằng 0 thì được gọi là đỉnh cô lập.
Nếu đỉnh có bậc bằng 1 thì được gọi là đỉnh treo.
Xét đồ thị 𝐺 như hình dưới, ta có 𝑑𝐺 (𝑣1 ) = 4, 𝑑𝐺 (𝑣2 ) = 3, 𝑑𝐺 (𝑣3 ) = 3 và
𝑑𝐺 (𝑣4 ) = 0.

3

❖ Cho 𝐺 là một đồ thị có hướng. Bậc vào của đỉnh 𝑢, ký hiệu deg − (𝑢), là số
cung của đỉnh cuối. Bậc ra của đỉnh 𝑢, ký hiệu deg + (𝑢), là số cung của đỉnh đầu.
Nếu deg − (𝑢) + deg + (𝑢) = 0 thì 𝑢 được gọi là đỉnh cô lập.
Nếu deg − (𝑢) = 0 và deg + (𝑢) = 1, hoặc deg − (𝑢) = 1 và deg + (𝑢) = 0 thì 𝑢
được gọi là đỉnh treo.
Xét đồ thị có hướng 𝐻 bên dưới, ta có deg − (𝐴) = 0; deg + (𝐴) = 2; deg − (𝐵) =
1; deg + (𝐵) = 2; deg − (𝐶) = 2; deg + (𝐶) = 2; deg − (𝐷) = 3; deg + (𝐷) =
1; deg − (𝐸) = 1; deg + (𝐸) = 0; deg − (𝐹) = deg + (𝐹) = 0;

4. Đường đi, chu trình, tính liên thông
a) Đường đi
- Đường đi có độ dài 𝑘 từ đỉnh 𝑣0 đến 𝑣𝑘 của một đồ thị là một dãy các cạnh
(cung) liên tiếp 𝑣0 𝑣1 , 𝑣1 𝑣2 , … , 𝑣𝑘−1 𝑣𝑘 , trong đó 𝑣0 được gọi là đỉnh đầu, 𝑣𝑘 là đỉnh
cuối của đường đi. Ta ký hiệu đường đi: 𝑊 = 𝑣0 𝑒1 𝑣1 𝑒2 𝑣2 … 𝑒𝑘 𝑣𝑘 . Độ dài của một
đường đi bằng với số cạnh trong đường đi đó.
Trong một đơn đồ thị, một đường đi hoàn toàn xác định khi ta biết dãy các đỉnh
của nó. Do đó, ta có thể ký hiệu 𝑊 = 𝑣0 𝑣1 𝑣2 … 𝑣𝑘 thay cho 𝑊 =
𝑣0 𝑒1 𝑣1 𝑒2 𝑣2 … 𝑒𝑘 𝑣𝑘 .
- Đường đi được gọi là đơn nếu nó không đi qua cạnh nào quá một lần.
4

- Đường đi được gọi là sơ cấp nếu nó không đi qua đỉnh nào quá một lần.
Ví dụ: Xét đồ thị 𝐺 như hình sau

Đường đi 𝑊1 = 𝑣1 𝑒1 𝑣2 𝑒3 𝑣3 𝑒3 𝑣2 không phải là đường đi đơn. Đường đi 𝑊2 =
𝑣1 𝑒1 𝑣2 𝑒2 𝑣1 𝑒6 𝑣4 là một đường đi đơn nhưng không phải là đường đi sơ cấp. Đường
đi 𝑊3 = 𝑣1 𝑒1 𝑣2 𝑒3 𝑣3 𝑒4 𝑣4 là một đường đi sơ cấp có độ dài bằng 3.
b) Chu trình
- Đường đi có đỉnh đầu và đỉnh cuối trùng nhau được gọi là một chu trình.
- Chu trình được gọi là đơn nếu nó không đi qua cạnh nào quá một lần.
- Chu trình được gọi là sơ cấp nếu nó là chu trình đơn không đi qua đỉnh nào
quá một lần.
Ví dụ: Xét đồ thị sau:

Chu trình 𝐶1 = 𝑣1 𝑒1 𝑣2 𝑒6 𝑣6 𝑒7 𝑣1 𝑒1 𝑣2 𝑒1 𝑣1 không phải là chu trình đơn. Chu trình
𝐶2 = 𝑣1 𝑒1 𝑣2 𝑒2 𝑣3 𝑒3 𝑣4 𝑒4 𝑣5 𝑒5 𝑣2 𝑒6 𝑣6 𝑒7 𝑣1 là một chu trình đơn nhưng không phải là
chu trình sơ cấp. Chu trình 𝐶3 = 𝑣1 𝑒1 𝑣2 𝑒6 𝑣6 𝑒7 𝑣1 là một chu trình sơ cấp.
c) Tính liên thông
Hai đỉnh 𝑢 và 𝑣 của đồ thị 𝐺 được gọi là liên thông nếu trong 𝐺 có một đường đi
sơ cấp từ 𝑢 đến 𝑣. Liên thông là một quan hệ tương đương tập hợp đỉnh 𝑉. Vì vậy,
𝑉 có thể được phân hoạch thành các tập con khác rỗng 𝑉1 , 𝑉2 , … , 𝑉𝜔 sao cho hai đỉnh
𝑢 và 𝑣 liên thông khi và chỉ khi cả hai đỉnh 𝑢 và 𝑣 thuộc cùng một 𝑉𝑖 . Các đồ thị con
𝐺[𝑉1 ], 𝐺[𝑉2 ], … , 𝐺[𝑉𝜔 ] được gọi là các thành phần liên thông của 𝐺. Nếu 𝐺 có đúng

5

một thành phần liên thông thì ta nói 𝐺 liên thông; ngược lại ta nói 𝐺 không liên
thông. Ta ký hiệu số thành phần liên thông của 𝐺 bằng 𝜔(𝐺).
Ví dụ: Đồ thị 𝐺 trong hình dưới có ba thành phần liên thông. Tập đỉnh của các
thành phần liên thông lần lượt là 𝑉1 = {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 }, 𝑉2 = {𝑣5 , 𝑣6 , 𝑣7 , 𝑣8 } và 𝑉3 =
{𝑣9 , 𝑣10 }.

5. Đồ thị Euler
Cho 𝐺 = (𝑉, 𝐸) là một đồ thị
- Một chu trình đơn đi qua tất cả các cạnh của đồ thị được gọi là chu trình Euler.
- Một đường đi đơn đi qua tất cả các cạnh của đồ thị được gọi là đường đi Euler.
- Đồ thị có chu trình Euler được gọi là đồ thị Euler.
Ví dụ: Cho các đồ thị 𝐺1 , 𝐺2 , 𝐺3

Đồ thị 𝐺1 là đồ thị Euler vì nó có chu trình Euler 𝐶 = 𝑎𝑒𝑐𝑑𝑒𝑏𝑎.
Đồ thị 𝐺2 không có chu trình cũng như đường đi Euler.
Đồ thị 𝐺3 không có chu trình Euler nhưng nó có đường đi Euler 𝑊 = 𝑎𝑐𝑑𝑒𝑏𝑑𝑎𝑏
6. Đồ thị Hamilton
Cho đồ thị 𝐺 = (𝑉, 𝐸)
- Một chu trình sơ cấp được gọi là chu trình Hamilton nếu như nó đi qua tất cả
các đỉnh của đồ thị.
- Một đường đi sơ cấp được gọi là đường đi Hamilton nếu như nó đi qua tất cả
các đỉnh của đồ thị.
- Đồ thị có chu trình Hamilton được gọi là đồ thị Hamilton.
6

Ví dụ: Khối mười hai mặt là đồ thị Hamilton

II. CÁC DẠNG BÀI TẬP
1. Thuật toán tìm đường đi Euler
a) Phương pháp
Bước 1: Nếu 𝐺 là đồ thị không liên thông thì 𝐺 không có chu trình Euler. Bài
toán kết thúc.
Ngược lại, sang bước 2
Bước 2: Nếu 𝐺 có số đỉnh có bậc lẻ khác 2 thì 𝐺 không có chu trình Euler. Bài
toán kết thúc.
Ngược lại, sang bước 3
Bước 3: Ta thêm cạnh nối hai đỉnh có bậc lẻ và xây dựng quy trình tìm chu trình
Euler như trên. Sau đó ta sẽ điều chỉnh chu trình vừa tìm được thành một chu trình
mới có điểm đầu và điểm cuối là một trong hai đỉnh bậc lẻ và cạnh cuối cùng trong
chu trình này là cạnh ta vừa thêm vào. Khi đó ta chỉ cần loại bỏ cạnh mới thêm vào
trong chu trình trên ta sẽ được đường đi Euler.
b) Ví dụ
Tìm đường đi Euler của đồ thị sau

Giải
Đồ thị trên là đồ thị liên thông và có số đỉnh bậc lẻ là 2 nên đồ thị có đường đi
Euler. Ta thêm vào đồ thị cạnh 𝑒8 = 𝑎𝑏
7

Ta tìm được chu trình Euler: 𝑎𝑒1 𝑒𝑒5 𝑑𝑒4 𝑐𝑒3 𝑏𝑒8 𝑎𝑒6 𝑑𝑒7 𝑏𝑒2 𝑎 (có thể có nhiều chu
trình khác).
Ta điều chỉnh chu trình Euler trên thành chu trình Euler khác là
𝑎𝑒6 𝑑𝑒7 𝑏𝑒2 𝑎𝑒1 𝑒𝑒5 𝑑𝑒4 𝑐𝑒3 𝑏𝑒8 𝑎. Sau đó ta xóa đi cạnh 𝑒8 , ta được đường đi Euler:
𝑎𝑒6 𝑑𝑒7 𝑏𝑒2 𝑎𝑒1 𝑒𝑒5 𝑑𝑒4 𝑐𝑒3 𝑏
2. Bài toán người đưa thư Trung Hoa
Trong công việc của mình, một người đưa thư nhận thư tại bưu điện, chuyển nó
và sau đó quay lại bưu điện. Tất nhiên, anh ta phải qua mỗi con đường trong khu
vực của mình ít nhất một lần. Theo điều kiện này, anh ta muốn chọn tuyến đường
sao cho anh ta đi bộ ít nhất có thể. Bài toán này được gọi là bài toán người đưa thư
Trung Hoa, vì nó lần đầu tiên được xem xét bởi một nhà toán học Trung Quốc, Guan
(1962).
Ta xét bài toán bài toán ở một dạng đơn giản như sau: Cho đồ thị liên thông 𝐺 =
(𝑉, 𝐸). Một chu trình qua mọi cạnh của 𝐺 gọi là hành trình trong 𝐺. Trong các hành
trình đó, hãy tìm hành trình ngắn nhất, tức là qua ít cạnh nhất.
a) Phương pháp
❖ Trường hợp 1: Nếu 𝐺 là đồ thị Euler (mọi đỉnh đều có bậc chẵn) thì chu trình
Euler trong 𝐺 (qua mỗi cạnh của 𝐺 đúng một lần) là hành trình ngắn nhất cần tìm.
❖ Trường hợp 2: 𝐺 có một số đỉnh bậc lẻ (số đỉnh bậc lẻ là một số chẵn). Khi
đó mọi hành trình trong 𝐺 phải đi qua ít nhất hai lần một số cạnh nào đó.
Bước 1: Gọi 𝑉0 (𝐺) là tập hợp các đỉnh bậc lẻ (2k đỉnh) của 𝐺. Ta phân 2k phần
tử của 𝐺 thành k cặp, mỗi tập hợp k cặp gọi là một phân hoạch cặp của 𝑉0 (𝐺).
Ta gọi độ dài đường đi ngắn nhất từ 𝑥 đến 𝑦 là khoảng cách 𝑑(𝑥, 𝑦). Đối với mọi
phân hoạch cặp 𝑃𝑖 , ta tính khoảng cách giữa hai đỉnh trong từng cặp, rồi tính tổng
𝑑(𝑃𝑖 ). Khi đó, số cạnh mà hành trình đi qua hai lần 𝑚(𝐺) chính là số nhỏ nhất của
các 𝑑(𝑃𝑖 ): 𝑚(𝐺) = 𝑚𝑖𝑛 𝑑(𝑃𝑖 ).
Bước 2: (Ta quy ước xem mỗi hành trình trong 𝐺 là một hành trình trong đồ thị
Euler 𝐺 ' ). Do đó 𝐺' có được từ 𝐺 bằng cách vẽ thêm 𝑚(𝐺) cạnh, mỗi cạnh song
song với những cạnh mà mỗi hành trình trong 𝐺 đi qua hai lần.
8

Bước 3: Trong các đồ thị Euler 𝐺 ' , tìm đồ thị có số cạnh ít nhất (khi đó chu trình
Euler trong đồ thị này là hành trình ngắn nhất).
b) Ví dụ
Giải bài toán người đưa thư Trung Hoa cho trong đồ thị 𝐺 sau (trọng số các cạnh
là 1)

Giải
Do 𝐺 có số đỉnh bậc lẻ là 4 nên tập hợp các đỉnh bậc lẻ 𝑉0 (𝐺) = {𝐵, 𝐸, 𝐻, 𝐼} và
tập hợp các phân hoạch cặp là 𝑃 = {𝑃1 , 𝑃2 , 𝑃3 }, trong đó:
𝑃1 = {(𝐵, 𝐸), (𝐻, 𝐼)} ⇒ 𝑑(𝑃1 ) = 𝑑(𝐵, 𝐸) + 𝑑(𝐻, 𝐼) = 2 + 2 = 4
𝑃2 = {(𝐵, 𝐻), (𝐸, 𝐼)} ⇒ 𝑑(𝑃2 ) = 𝑑(𝐵, 𝐻) + 𝑑(𝐸, 𝐼) = 4 + 3 = 7
𝑃3 = {(𝐵, 𝐼), (𝐸, 𝐻)} ⇒ 𝑑(𝑃3 ) = 𝑑(𝐵, 𝐼) + 𝑑(𝐸, 𝐻) = 2 + 3 = 5
⇒ 𝑚(𝐺) = min{𝑑(𝑃1 ), 𝑑(𝑃2 ), 𝑑(𝑃3 )} = 4.
Do đó 𝐺 ' có được từ 𝐺 bằng cách thêm vào 4 cạnh 𝐵𝐶, 𝐶𝐸, 𝐻𝐺, 𝐺𝐼

Vậy hành trình ngắn nhất cần tìm là đi theo chu trình Euler trong
𝐺 : 𝐴𝐵𝐶𝐷𝐸𝐹𝐺𝐻𝐺𝐼𝐾𝐽𝐺𝐼𝐽𝐶𝐸𝐶𝐵𝐾𝐴
3. Bài toán người bán hàng
Một nhân viên bán hàng muốn đến một số thị trấn và sau đó quay trở lại điểm
xuất phát của mình. Biết trước thời gian di chuyển giữa các thị trấn, anh ta lên kế
hoạch cho hành trình của mình như thế nào để anh ta đến mỗi thị trấn đúng một lần
'

9

và tổng thời gian di chuyển là ngắn nhất? Bài toán này được gọi là bài toán người
bán hàng. Theo ngôn ngữ của lý thuyết đồ thị, mục tiêu là tìm một chu trình
Hamilton có trọng số nhỏ nhất trong một đồ thị đầy đủ có trọng số. Ta sẽ gọi một
chu trình như vậy là một chu trình tối ưu.
a) Phương pháp: Sử dụng thuật toán láng giềng gần nhất
Bước 1: Chọn một đỉnh bắt đầu 𝑉.
Bước 2: Từ đỉnh hiện hành, chọn cạnh nối có trọng số nhỏ nhất đến các đỉnh chưa
đến. Đánh dấu đã đến đỉnh vừa chọn.
Bước 3: Nếu còn đỉnh chưa đến thì quay lại bước 2.
Bước 4: Quay lại đỉnh 𝑉
Bước 5: Bắt đầu lại với những đỉnh khác.
Bước 6: So sánh trọng số của chu trình bắt đầu từ các đỉnh khác nhau và đưa ra
kết luận.
b) Ví dụ
Giải bài toán người bán hàng cho trong đồ thị sau

Giải
Sử dụng thuật toán láng giềng gần nhất, ta bắt đầu với đỉnh 𝐿𝑜
➢ Từ 𝐿𝑜, đỉnh gần nhất là 𝑃𝑎, trọng số của 𝐿𝑜 𝑃𝑎 là 2
➢ Từ 𝑃𝑎, đỉnh chưa viếng thăm gần nhất là 𝑁𝑌, trọng số của 𝑃𝑎 𝑁𝑌 là 36
➢ Từ 𝑁𝑌, đỉnh chưa viếng thăm gần nhất là 𝑀𝐶, trọng số của 𝑁𝑌 𝑀𝐶 là 21
➢ Từ 𝑀𝐶, đỉnh chưa viếng thăm gần nhất là 𝑇𝑜, trọng số của 𝑀𝐶 𝑇𝑜 là 70
➢ Từ 𝑇𝑜, đỉnh chưa viếng thăm gần nhất là 𝑃𝑒, trọng số của 𝑇𝑜 𝑃𝑒 là 13
➢ Không còn đỉnh chưa viếng thăm, vì vậy quay về 𝐿𝑜, trọng số của 𝑃𝑒 𝐿𝑜 là
51
Khi đó chu trình 𝐿𝑜 𝑃𝑎 𝑁𝑌 𝑀𝐶 𝑇𝑜 𝑃𝑒 𝐿𝑜 có trọng số là 193.
Tương tự, ta bắt đầu lại với những đỉnh còn lại và thu được bảng sau

10

Đỉnh bắt đầu
Chu trình
Trọng số
193
𝐿𝑜
𝐿𝑜 𝑃𝑎 𝑁𝑌 𝑀𝐶 𝑇𝑜 𝑃𝑒 𝐿𝑜
192
𝑀𝐶
𝑀𝐶 𝑁𝑌 𝐿𝑜 𝑃𝑎 𝑃𝑒 𝑇𝑜 𝑀𝐶
211
𝑁𝑌
𝑁𝑌 𝑀𝐶 𝐿𝑜 𝑃𝑎 𝑃𝑒 𝑇𝑜 𝑁𝑌
192
𝑃𝑎
𝑃𝑎 𝐿𝑜 𝑁𝑌 𝑀𝐶 𝑇𝑜 𝑃𝑒 𝑃𝑎
210
𝑃𝑒
𝑃𝑒 𝑇𝑜 𝐿𝑜 𝑃𝑎 𝑁𝑌 𝑀𝐶 𝑃𝑒
192
𝑇𝑜
𝑇𝑜 𝑃𝑒 𝑃𝑎 𝐿𝑜 𝑁𝑌 𝑀𝐶 𝑇𝑜
Dựa vào bảng trên, trọng số nhỏ nhất là 192 và có 3 chu trình có trọng số 192.
Vậy chu trình tốt nhất tìm ra bởi thuật toán láng giềng là 𝐿𝑜 𝑁𝑌 𝑀𝐶 𝑇𝑜 𝑃𝑒 𝑃𝑎 𝐿𝑜
4. Bài toán tìm đường đi tối ưu (thuật toán)
❖ Thuật toán Dijkstra
Cho một đồ thị có trọng số không âm với 𝑛 đỉnh, tìm đường đi ngắn nhất từ đỉnh
𝑢0 đến tất cả các đỉnh khác. Thuật toán Dijkstra chỉ tìm khoảng cách từ 𝑢0 đến tất
cả các đỉnh khác và không phải tìm đường đi ngắn nhất. Do đó, ta áp dụng thuật toán
Dijkstra kết hợp với lưu vết.
a) Phương pháp
Bước 1: Khởi tạo 𝑖 = 0 và 𝑆0 = {𝑢𝑜 }. Dán cho 𝑢𝑜 nhãn 𝑙(𝑢0 ) = 0, mỗi đỉnh 𝑣 ≠
𝑢0 dán nhãn tạm 𝑙(𝑣) = ∞.
Nếu 𝑛 = 1, khi đó 𝑉 = {𝑢0 } và bài toán kết thúc.
Nếu 𝑛 > 1, tiếp tục bước 2.
Bước 2: Đặt 𝑖 ≔ 𝑖 + 1, ∀𝑣 ∈ 𝑆̅, ta cập nhật nhãn của tất cả các đỉnh trong 𝑆̅, như
sau: 𝑙(𝑣) ≔ min{𝑙(𝑣), 𝑙(𝑢𝑖 ) + 𝑤(𝑢, 𝑣)}
Bước 3: ∀𝑣 ∈ 𝑆̅, tìm 𝑣 sao cho 𝑙(𝑣) = min{𝑙(𝑣)}. Khi đó 𝑢𝑖+1 ≔ 𝑣
Bước 4: Gán 𝑆 ≔ 𝑆 ∪ {𝑢𝑖+1 }
Bước 5: Nếu 𝑖 = 𝑛 − 1 thì kết thúc. Ngược lại, quay lại bước 2.
Sau khi thuật toán kết thúc, ta tiến hành lưu vết thông qua bảng minh hoạ sau:
Giai đoạn Giai đoạn Giai đoạn Giai đoạn Giai đoạn Giai đoạn
Đỉnh
0
1
2
3
4
5
∗
(0, ⊥)
𝑢0
(∞, ⊥)
(6, 𝑢0 )∗
𝑣1
(6, 𝑢0 )
(9, 𝑣3 )∗
𝑣2
(∞, ⊥)
(∞, ⊥)
(9, 𝑣3 )
(9, 𝑣3 )
(1, 𝑢0 )∗
𝑣3
(∞, ⊥)
(8, 𝑣3 )∗
𝑣4
(∞, ⊥)
(∞, ⊥)
(8, 𝑣3 )
(10, 𝑣2 )∗
𝑣0
(∞, ⊥)
(∞, ⊥)
(∞, ⊥)
(∞, ⊥)
(13, 𝑣4 )

11

Trong bảng này ta dùng ký hiệu (𝑎, 𝑏) ở dòng 𝑣 cột giai đoạn 𝑗 để chỉ 𝑙(𝑣) = 𝑎
và đỉnh liền trước của 𝑣 là 𝑏, nếu 𝑣 không có đỉnh liền trước thì ta dùng ký hiệu ⊥ ở
vị trí 𝑏. Dấu ∗ ở dòng 𝑣 để chỉ đỉnh 𝑣 được thêm vào 𝑆.
Ta ký hiệu 𝑃(𝑢, 𝑣) là đường đi ngắn nhất từ 𝑢 đến 𝑣. Phần tử (10, 𝑣2 )∗ ở dòng
𝑣0 trong bảng trên cho ta biết 𝑃(𝑢0 , 𝑣0 ) có độ dài bằng 10 và 𝑃(𝑢0 , 𝑣0 ) =
𝑃(𝑢0 , 𝑣2 ) ∪ 𝑣2 𝑣0 . Phần tử (9, 𝑣3 )∗ ở dòng 𝑣2 cho ta biết 𝑃(𝑢0 , 𝑣2 ) = 𝑃(𝑢0 , 𝑣3 ) ∪
𝑣3 𝑣2 . Phần tử (1, 𝑢0 )∗ ở dòng 𝑣3 cho ta biết 𝑃(𝑢0 , 𝑣3 ) = 𝑃(𝑢0 , 𝑢0 ) ∪ 𝑢0 𝑣3 . Vậy
𝑃(𝑢0 , 𝑣0 ) = 𝑢0 𝑣3 𝑣2 𝑣0 .
b) Ví dụ
Tìm đường đi ngắn nhất từ 𝑢0 đến 𝑣0 của đồ thị sau

Giải
Áp dụng thuật toán Dijkstra:
Ban đầu nhãn của các đỉnh như sau: 𝑙(𝑢0 ) = 0, 𝑙(𝑣1 ) = ∞, 𝑙(𝑣2 ) = ∞, 𝑙(𝑣3 ) =
∞, 𝑙(𝑣4 ) = ∞ và 𝑙(𝑣0 ) = ∞, ngoài ra ta còn đặt 𝑆0 = {𝑢0 } và 𝑖 = 0.
Vì 𝑖 < 𝑛 − 1 nên ta đặt 𝑖 ≔ 𝑖 + 1 = 1.
Ta có 𝑆̅0 = {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣0 }, ta cập nhật nhãn của các đỉnh trong 𝑆̅0 như sau
𝑙(𝑣1 ) ≔ min{𝑙(𝑣1 ), 𝑙(𝑢0 ) + 𝑤(𝑢0 𝑣1 )} = min{∞, 0 + 6} = 6
𝑙(𝑣2 ) ≔ min{𝑙(𝑣2 ), 𝑙(𝑢0 ) + 𝑤(𝑢0 𝑣2 )} = min{∞, 0 + ∞} = ∞
𝑙(𝑣3 ) ≔ min{𝑙(𝑣3 ), 𝑙(𝑢0 ) + 𝑤(𝑢0 𝑣3 )} = min{∞, 0 + 1} = 1
𝑙(𝑣4 ) ≔ min{𝑙(𝑣4 ), 𝑙(𝑢0 ) + 𝑤(𝑢0 𝑣4 )} = min{∞, 0 + ∞} = ∞
𝑙(𝑣0 ) ≔ min{𝑙(𝑣0 ), 𝑙(𝑢0 ) + 𝑤(𝑢0 𝑣0 )} = min{∞, 0 + ∞} = ∞
Ta thấy trong 𝑆̅0 , đỉnh 𝑣3 là đỉnh có nhãn nhỏ nhất nên ta đặt 𝑆1 = 𝑆0 ∪ {𝑣3 } =
{𝑢0 , 𝑣3 }.
Vì 𝑖 < 𝑛 − 1 nên ta đặt 𝑖 ≔ 𝑖 + 1 = 2.
Ta có 𝑆̅1 = {𝑣1 , 𝑣2 , 𝑣4 , 𝑣0 }, ta cập nhật nhãn của các đỉnh trong 𝑆̅1 như sau
𝑙(𝑣1 ) ≔ min{𝑙(𝑣1 ), 𝑙(𝑣3 ) + 𝑤(𝑣3 𝑣1 )} = min{6, 1 + 6} = 6
𝑙(𝑣2 ) ≔ min{𝑙(𝑣2 ), 𝑙(𝑣3 ) + 𝑤(𝑣3 𝑣2 )} = min{∞, 1 + 8} = 9
𝑙(𝑣4 ) ≔ min{𝑙(𝑣4 ), 𝑙(𝑣3 ) + 𝑤(𝑣3 𝑣4 )} = min{∞, 1 + 7} = 8
12

𝑙(𝑣0 ) ≔ min{𝑙(𝑣0 ), 𝑙(𝑣3 ) + 𝑤(𝑣3 𝑣0 )} = min{∞, 1 + ∞} = ∞
Ta thấy trong 𝑆̅1 , đỉnh 𝑣1 là đỉnh có nhãn nhỏ nhất nên ta đặt 𝑆2 = 𝑆1 ∪ {𝑣1 } =
{𝑢0 , 𝑣3 , 𝑣1 }.
Vì 𝑖 < 𝑛 − 1 nên ta đặt 𝑖 ≔ 𝑖 + 1 = 3.
Ta có 𝑆̅2 = {𝑣2 , 𝑣4 , 𝑣0 }, ta cập nhật nhãn của các đỉnh trong 𝑆̅2 như sau
𝑙(𝑣2 ) ≔ min{𝑙(𝑣2 ), 𝑙(𝑣1 ) + 𝑤(𝑣1 𝑣2 )} = min{9, 6 + 6} = 9
𝑙(𝑣4 ) ≔ min{𝑙(𝑣4 ), 𝑙(𝑣1 ) + 𝑤(𝑣1 𝑣4 )} = min{8, 6 + 3} = 8
𝑙(𝑣0 ) ≔ min{𝑙(𝑣0 ), 𝑙(𝑣1 ) + 𝑤(𝑣1 𝑣0 )} = min{∞, 6 + ∞} = ∞
Ta thấy trong 𝑆̅2 , đỉnh 𝑣4 là đỉnh có nhãn nhỏ nhất nên ta đặt 𝑆3 = 𝑆2 ∪ {𝑣4 } =
{𝑢0 , 𝑣3 , 𝑣1 , 𝑣4 }.
Vì 𝑖 < 𝑛 − 1 nên ta đặt 𝑖 ≔ 𝑖 + 1 = 4.
Ta có 𝑆̅3 = {𝑣2 , 𝑣0 }, ta cập nhật nhãn của các đỉnh trong 𝑆̅3 như sau
𝑙(𝑣2 ) ≔ min{𝑙(𝑣2 ), 𝑙(𝑣4 ) + 𝑤(𝑣4 𝑣2 )} = min{9, 8 + 2} = 9
𝑙(𝑣0 ) ≔ min{𝑙(𝑣0 ), 𝑙(𝑣4 ) + 𝑤(𝑣4 𝑣0 )} = min{∞, 8 + 5} = 13
Ta thấy trong 𝑆̅3 , đỉnh 𝑣2 là đỉnh có nhãn nhỏ nhất nên ta đặt 𝑆4 = 𝑆3 ∪ {𝑣2 } =
{𝑢0 , 𝑣3 , 𝑣1 , 𝑣4 , 𝑣2 }.
Vì 𝑖 < 𝑛 − 1 nên ta đặt 𝑖 ≔ 𝑖 + 1 = 5.
Ta có 𝑆̅4 = {𝑣0 }, ta cập nhật nhãn của các đỉnh trong 𝑆̅4 như sau
𝑙(𝑣0 ) ≔ min{𝑙(𝑣0 ), 𝑙(𝑣2 ) + 𝑤(𝑣2 𝑣0 )} = min{13, 9 + 1} = 10
Ta thấy trong 𝑆̅4 , đỉnh 𝑣0 là đỉnh có nhãn nhỏ nhất nên ta đặt 𝑆5 = 𝑆4 ∪ {𝑣0 } =
{𝑢0 , 𝑣3 , 𝑣1 , 𝑣4 , 𝑣2 , 𝑣0 }.
Vì 𝑖 = 𝑛 − 1 nên thuật toán kết thúc.
Kết hợp thuật toán với lưu vết, ta có được bảng sau:
Giai đoạn Giai đoạn Giai đoạn Giai đoạn Giai đoạn Giai đoạn
Đỉnh
0
1
2
3
4
5
∗
(0, ⊥)
𝑢0
(∞, ⊥)
(6, 𝑢0 )∗
𝑣1
(6, 𝑢0 )
(9, 𝑣3 )∗
𝑣2
(∞, ⊥)
(∞, ⊥)
(9, 𝑣3 )
(9, 𝑣3 )
(1, 𝑢0 )∗
𝑣3
(∞, ⊥)
(8, 𝑣3 )∗
𝑣4
(∞, ⊥)
(∞, ⊥)
(8, 𝑣3 )
(10, 𝑣2 )∗
𝑣0
(∞, ⊥)
(∞, ⊥)
(∞, ⊥)
(∞, ⊥)
(13, 𝑣4 )
Vậy đường đi ngắn nhất từ 𝑢0 đến 𝑣0 là 𝑃(𝑢0 , 𝑣0 ) = 𝑢0 𝑣3 𝑣2 𝑣0 và đồ thị sau
minh họa cho đường đi ngắn nhất từ 𝑢0 đến các đỉnh còn lại:

13

❖ Thuật toán Floyd-Warshall
a) Phương pháp
Cho một đơn đồ thị có trọng số với 𝑛 đỉnh 𝑣1 , 𝑣2 , … , 𝑣𝑛 , để tìm đường đi ngắn
nhất giữa các cặp đỉnh bất kỳ, ta sử dụng thuật toán Floyd-Warshall như sau:
Bước 1: Nếu 𝑣𝑖 𝑣𝑗 (𝑖 ≠ 𝑗) là một cạnh thì đặt 𝑑(𝑖, 𝑗) = 𝑤(𝑣𝑖 𝑣𝑗 ), ngược lại đặt
𝑑(𝑖, 𝑗) = ∞.
Bước 2: Cho 𝑘 = 1 đến 𝑛
- Cho 𝑖, 𝑗 = 1 đến 𝑛, đặt 𝑑(𝑖, 𝑗) = min{𝑑(𝑖, 𝑗), 𝑑(𝑖, 𝑘) + 𝑑(𝑘, 𝑗)}
- Giá trị cuối cùng của 𝑑(𝑖, 𝑗) là khoảng cách ngắn nhất từ 𝑣𝑖 đến 𝑣𝑗
b) Ví dụ
Sử dụng thuật toán Floyd-Warshal để tìm đường đi ngắn nhất giữa hai đỉnh bất
kỳ của đồ thị 𝐺

Giải
Ta có bảng giá trị ban đầu của 𝑑(𝑖, 𝑗)

14

𝑣1
𝑣2
𝑣3
𝑣4

𝑣1
𝑣2
𝑣3
𝑣4

𝑣1
0
4
2
∞

𝑣1
0
4
2
∞

𝑘=1
𝑣2
𝑣3
4
2
0
6
6
0
9
2

𝑣4
∞
9
2
0

𝑣2
4
0
7
9

→

𝑣3
2
7
0
2

𝑣1
𝑣2
𝑣3
𝑣4

𝑣4
∞
9
2
0

𝑣1
0
4
2
13

𝑘=2
𝑣2
𝑣3
4
2
0
6
6
0
9
2

𝑣4
13
9
2
0

𝑘=3
𝑘=4
𝑣1
𝑣2
𝑣3
𝑣4
𝑣1
𝑣2
𝑣3
𝑣4
4
2
4
4
2
4
𝑣1 0
𝑣1 0
→
0
6
8
0
6
8
𝑣2 4
𝑣2 4
6
0
2
6
0
2
𝑣3 2
𝑣3 2
8
2
0
8
2
0
𝑣4 4
𝑣4 4
Dựa vào bảng cuối cùng ta suy ra được độ dài ngắn nhất giữa các cặp đỉnh. Từ
đó, ta tìm được đường đi ngắn nhất của hai cặp đỉnh bất kỳ là:
➢ Đường đi ngắn nhất từ 𝑣1 đến 𝑣2 : 𝑣1 𝑣2
➢ Đường đi ngắn nhất từ 𝑣1 đến 𝑣3 : 𝑣1 𝑣3
➢ Đường đi ngắn nhất từ 𝑣1 đến 𝑣4 : 𝑣1 𝑣3 𝑣4
➢ Đường đi ngắn nhất từ 𝑣2 đến 𝑣3 : 𝑣2 𝑣1 𝑣3
➢ Đường đi ngắn nhất từ 𝑣2 đến 𝑣4 : 𝑣2 𝑣1 𝑣3 𝑣4
➢ Đường đi ngắn nhất từ 𝑣3 đến 𝑣4 : 𝑣3 𝑣4

III. BÀI TẬP VẬN DỤNG
Câu 1: Giải bài toán sau: Có thể đi dạo chơi qua các cây cầu trong thành phố
(hình bên dưới), mỗi cầu vừa đúng một lần hay không?

15

Đáp án: Có thể dạo chơi qua các cây cầu trong thành phố vì ta tìm được đường
đi Euler xuất phát từ 𝐵 như sau: 𝐵𝐸𝐶𝐸𝐵𝐷𝐶𝐷𝐸𝐹𝐴𝐵
Câu 2: Tìm đường đi Euler của đồ thị có hướng sau

Đáp án: Đường đi Euler của đồ thị trên là: 𝑐𝑒𝑎𝑓𝑑𝑒𝑏𝑓𝑒𝑓𝑎𝑏𝑑𝑐𝑏
Câu 3: Giải bài toán người đưa thư Trung Hoa cho đồ thị 𝐺 sau:

16

Đáp án: Hành trình ngắn nhất cần tìm là đi theo chu trình Euler trong 𝐺 ' : 𝐶 =
𝑥𝑢𝑦𝑤𝑣𝑧𝑤𝑦𝑥𝑢𝑤𝑣𝑥𝑧𝑦𝑥

Câu 4: Giải bài toán người đưa thư Trung Hoa cho đồ thị 𝐻 sau:

Đáp án: Hành trình ngắn nhất cần tìm là đi theo chu trình Euler trong 𝐻' : 𝐶 =
𝑎𝑏𝑐𝑑𝑒𝑏𝑎𝑒𝑐𝑑𝑎

17

Câu 5: Giải bài toán người bán hàng cho đồ thị sau

Đáp án: Chu trình Hamilton tốt nhất lả 𝐶𝐷𝐸𝐺𝐹𝐴𝐵𝐶 với trọng số là 46.
Câu 6: Giải bài toán người bán hàng cho đồ thị sau

18

Đáp án: Chu trình Hamilton tốt nhất lả 𝐴𝐵𝐶𝐹𝐷𝐸𝐴 với trọng số là 10.
Câu 7: Tìm đường đi ngắn nhất từ 𝑎 đến 𝑧 trong đồ thị dưới đây bằng thuật
toán Dijkstra

Đáp án:
Đỉnh Giai đoạn Giai đoạn Giai đoạn Giai đoạn Giai đoạn Giai đoạn
0
1
2
3
4
5
∗
(0, ⊥)
𝑎
𝑏

(∞, ⊥)

(2, 𝑎)∗

𝑐

(∞, ⊥)

(3, 𝑎)

(3, 𝑎)∗

𝑑

(∞, ⊥)

(∞, ⊥)

(7, 𝑏)

(7, 𝑏)

𝑒

(∞, ⊥)

(∞, ⊥)

(4, 𝑏)

(4, 𝑏)∗

𝑧

(∞, ⊥)

(∞, ⊥)

(∞, ⊥)

(∞, ⊥)

19

(5, 𝑒)∗
(8, 𝑒)

(7, 𝑑)∗

Đường đi ngắn nhất từ 𝑎 đến 𝑧 là 𝑎𝑏𝑒𝑑𝑧

Câu 8: Tìm đường đi ngắn nhất từ 𝑣1 đến 𝑣10 trong đồ thị 𝐺 ở hình vẽ sau
bằng thuật toán Dijkstra

Đáp án:

20

Đường đi ngắn nhất từ 𝑣1 đến 𝑣10 : 𝑣1 𝑣4 𝑣6 𝑣9 𝑣10

21

Câu 9: Sử dụng thuật toán Floyd-Warshall để tìm đường đi ngắn nhất giữa
hai đỉnh bất kỳ của đồ thị sau

Đáp án: Bảng giá trị của cuối cùng
𝑣1
𝑣2
𝑣3
𝑣4
1
2
2
𝑣1 0
0
1
3
𝑣2 1
1
0
3
𝑣3 2
3
3
0
𝑣4 2
2
3
1
𝑣5 1
4
5
2
𝑣6 3
Đường đi ngắn nhất giữa hai đỉnh bất kỳ là:
➢ Đường đi ngắn nhất từ 𝑣1 đến 𝑣2 : 𝑣1 𝑣2
➢ Đường đi ngắn nhất từ 𝑣1 đến 𝑣3 : 𝑣1 𝑣2 𝑣3
➢ Đường đi ngắn nhất từ 𝑣1 đến 𝑣4 : 𝑣1 𝑣5 𝑣4
➢ Đường đi ngắn nhất từ 𝑣1 đến 𝑣5 : 𝑣1 𝑣5
➢ Đường đi ngắn nhất từ 𝑣1 đến 𝑣6 : 𝑣1 𝑣5 𝑣6
➢ Đường đi ngắn nhất từ 𝑣2 đến 𝑣3 : 𝑣2 𝑣3
➢ Đường đi ngắn nhất từ 𝑣2 đến 𝑣4 : 𝑣2 𝑣5 𝑣4
➢ Đường đi ngắn nhất từ 𝑣2 đến 𝑣5 : 𝑣2 𝑣5
➢ Đường đi ngắn nhất từ 𝑣2 đến 𝑣6 : 𝑣2 𝑣5 𝑣6
➢ Đường đi ngắn nhất từ 𝑣3 đến 𝑣4 : 𝑣3 𝑣4
➢ Đường đi ngắn nhất từ 𝑣3 đến 𝑣5 : 𝑣3 𝑣2 𝑣5
➢ Đường đi ngắn nhất từ 𝑣3 đến 𝑣6 : 𝑣3 𝑣4 𝑣6
➢ Đường đi ngắn nhất từ 𝑣4 đến 𝑣5 : 𝑣4 𝑣5
➢ Đường đi ngắn nhất từ 𝑣4 đến 𝑣6 : 𝑣4 𝑣6
➢ Đường đi ngắn nhất từ 𝑣5 đến 𝑣6 : 𝑣5 𝑣6

22

𝑣5
1
2
3
1
0
2

𝑣6
3
4
5
2
2
0

Câu 10: Một công ty có chi nhánh ở 6 thành phố 𝐶1 , 𝐶2 , … , 𝐶6 . Chi phí để bay
trực tiếp từ thành phố 𝐶𝑖 đến thành 𝐶𝑗 là phần 𝑎𝑖,𝑗 của ma trận sau (∞ dùng để chỉ
không có chuyến bay trực tiếp giữa hai thành phố tương ứng).
0 50 ∞ 40 25 10
50 0 15 20 ∞ 25
∞ 15 0 10 20 ∞
𝐴=
40 20 10 0 10 25
25 ∞ 20 10 0 55
(10 25 ∞ 25 55 0 )
Hãy lập bảng chi phí thấp nhất và lộ trình để di chuyển giữa hai thành phố bất
kỳ trong 6 thành phố này.
Đáp án: Bảng chi phí thấp nhất giữa hai thành phố bất kỳ:
𝐶1
𝐶2
𝐶3
𝐶4
𝐶5
𝐶6
35
45
35
25
10
𝐶1 0
0
15
20
30
25
𝐶2 35
15
0
10
20
35
𝐶3 45
20
10
0
10
25
𝐶4 35
30
20
10
0
35
𝐶5 25
25
35
25
35
0
𝐶6 10
Lộ trình di chuyển giữa hai thành phố bất kỳ:
➢ Lộ trình di chuyển từ 𝐶1 đến 𝐶2 : 𝐶1 𝐶6 𝐶2
➢ Lộ trình di chuyển từ 𝐶1 đến 𝐶3 : 𝐶1 𝐶5 𝐶3
➢ Lộ trình di chuyển từ 𝐶1 đến 𝐶4 : 𝐶1 𝐶5 𝐶4
➢ Lộ trình di chuyển từ 𝐶1 đến 𝐶5 : 𝐶1 𝐶5
➢ Lộ trình di chuyển từ 𝐶1 đến 𝐶6 : 𝐶1 𝐶6
➢ Lộ trình di chuyển từ 𝐶2 đến 𝐶3 : 𝐶2 𝐶3
➢ Lộ trình di chuyển từ 𝐶2 đến 𝐶4 : 𝐶2 𝐶4
➢ Lộ trình di chuyển từ 𝐶2 đến 𝐶5 : 𝐶2 𝐶4 𝐶5
➢ Lộ trình di chuyển từ 𝐶2 đến 𝐶6 : 𝐶2 𝐶6
➢ Lộ trình di chuyển từ 𝐶3 đến 𝐶4 : 𝐶3 𝐶4
➢ Lộ trình di chuyển từ 𝐶3 đến 𝐶5 : 𝐶3 𝐶5
➢ Lộ trình di chuyển từ 𝐶3 đến 𝐶6 : 𝐶3 𝐶5 𝐶1 𝐶6
➢ Lộ trình di chuyển từ 𝐶4 đến 𝐶5 : 𝐶4 𝐶5
➢ Lộ trình di chuyển từ 𝐶4 đến 𝐶6 : 𝐶4 𝐶6
➢ Lộ trình di chuyển từ 𝐶5 đến 𝐶6 : 𝐶5 𝐶1 𝐶6

23

IV. TÀI LIỆU THAM KHẢO
1. Nguyễn Trung Kiên, Nguyễn Thanh Hùng (2021), Giáo trình Lý thuyết đồ thị
và ứng dụng, Đại học Cần Thơ.
2. Đặng Huy Ruân (2004), Lý thuyết đồ thị và ứng dụng, Nhà xuất bản Khoa học
và Kỹ thuật, Hà Nội.
3. Nguyễn Hữu Khánh, Phạm Bích Như (2014), Giáo trình Toán rời rạc – Toán
ứng dụng, Nhà xuất bản Đại học Cần Thơ.
4. Đoàn Quỳnh, Hạ Vũ Anh, Phạm Khắc Ban, Văn Như Cương, Vũ Đình Hòa
(2013), Tài liệu chuyên Toán – Bài tập Hình học 12, Nhà xuất bản Giáo dục
Việt Nam.
5. Nguyễn Thị Minh Thương (2015), Lý thuyết đồ thị với các bài toán phổ thông,
Luận văn Thạc sĩ khoa học, Trường Đại học Khoa học Tự nhiên – Đại học
Quốc gia Hà Nội.

24