TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN

ĐÀO THỊ HOÀI PHƯƠNG

MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC

Chuyên ngành: Toán ứng dụng

Hà Nội – Năm 2019


TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN

ĐÀO THỊ HOÀI PHƯƠNG

MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC

Chuyên ngành: Toán ứng dụng

Người hướng dẫn khoa học

TS. TRẦN VĨNH ĐỨC

Hà Nội – Năm 2019

LỜI CẢM ƠN

Em xin bày tỏ sự kính trọng và lời cảm ơn tới các thầy cô khoa Toán, Trường Đại
học Sư phạm Hà Nội 2, các thầy cô trong tổ Ứng dụng cũng như các thầy cô tham gia
giảng dạy đã tận tình truyền đạt những tri thức quý báu và tạo điều kiện thuận lợi để
em hoàn thành tốt chương trình học trong suốt 4 năm Đại học và thời gian thực hiện
khóa luận.
Đặc biệt, em xin bày tỏ lòng biết ơn sâu sắc tới TS. Trần Vĩnh Đức - Giảng viên
Trường Đại học Bách Khoa Hà Nội, người đã trực tiếp hướng dẫn, chỉ bảo tận tình
giúp đỡ để em có thể hoàn thành khóa luận này.
Do thời gian, năng lực và điều kiện bản thân còn hạn chế nên bản khóa luận không
thể tránh khỏi những sai sót. Vì vậy, em rất mong nhận được những ý kiến góp ý quý
báu của các thầy cô và các bạn.
Em xin chân thành cảm ơn.

Hà Nội, tháng 05 năm 2019
Sinh viên

Đào Thị Hoài Phương


LỜI CAM ĐOAN

Em xin cam đoan khóa luận này là kết quả của việc học tập, nghiên cứu độc lập
của bản thân dưới sự hướng dẫn của thầy giáo TS. Trần Vĩnh Đức. Trong quá trình
thực hiện đề tài “Một số bài toán tối ưu trên đồ thị” em đã tham khảo một số tài
liệu được ghi trong phần "Tài liệu tham khảo". Nếu sai em xin chịu mọi trách nhiệm.

Hà Nội, tháng 05 năm 2019

Sinh Viên

Đào Thị Hoài Phương


Mục lục
LỜI NÓI ĐẦU

1

1 MỘT SỐ KHÁI NIỆM CƠ BẢN CỦA ĐỒ THỊ

2

1.1

Đồ thị có hướng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2

Đồ thị vô hướng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.3

Đồ thị có trọng số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


3

1.4

Đồ thị liên thông . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.4.1

Hành trình, đường, chu trình . . . . . . . . . . . . . . . . . . .

4

1.4.2

Liên thông . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.4.3

Cây . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.5

Biểu diễn đồ thị bằng ma trận kề . . . . . . . . . . . . . . . . . . . . .


7

1.6

Biểu diễn đồ thị bằng ma trận liên thuộc . . . . . . . . . . . . . . . . .

8

1.7

Biểu diễn đồ thị có trọng số bằng các ma trận . . . . . . . . . . . . . .

9

2 BÀI TOÁN TÌM CÂY BAO TRÙM CÓ TRỌNG LƯỢNG NHỎ
NHẤT

11

2.1

Bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.2

Thuật toán Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11


2.3

Thuật toán Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

3 BÀI TOÁN TÌM ĐƯỜNG CÓ TRỌNG LƯỢNG NHỎ NHẤT

20

3.1

Bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

3.2

Thuật toán Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

3.3

Thuật toán Ford-Bellman . . . . . . . . . . . . . . . . . . . . . . . . .

25

4 BÀI TOÁN TÌM LUỒNG LỚN NHẤT TRONG MẠNG VẬN TẢI 28

4.1

Mạng vận tải. Luồng trong mạng vận tải. . . . . . . . . . . . . . . . . .
i

28


Khóa luận tốt nghiệp Đại học

Đào Thị Hoài Phương

4.2

Bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3

Thuật toán Ford-Fulkerson tìm luồng lớn nhất trong mạng vận tải nguyên 30

5 MỘT SỐ BÀI TOÁN KHÁC VỀ LUỒNG
5.1

5.2

5.3

29

35


Bài toán tìm luồng lớn nhất trong mạng vận tải đỉnh . . . . . . . . . .

35

5.1.1

Mạng vận tải đỉnh . . . . . . . . . . . . . . . . . . . . . . . . .

35

5.1.2

Luồng trong mạng vận tải đỉnh . . . . . . . . . . . . . . . . . .

35

5.1.3

Lát cắt trong mạng vận tải đỉnh . . . . . . . . . . . . . . . . . .

36

5.1.4

Bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

Bài toán tìm luồng lớn nhất trong mạng vận tải đỉnh - cung . . . . . .


37

5.2.1

Mạng vận tải đỉnh - cung . . . . . . . . . . . . . . . . . . . . .

37

5.2.2

Luồng trong mạng vận tải đỉnh - cung . . . . . . . . . . . . . .

37

5.2.3

Bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

Bài toán tìm luồng lớn nhất trong mạng vận tải có nhiều điểm phát và
nhiều điểm thu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

TÀI LIỆU THAM KHẢO

38
39

ii



Khóa luận tốt nghiệp Đại học

Đào Thị Hoài Phương

LỜI NÓI ĐẦU
Các bài toán tối ưu trên đồ thị đã được ứng dụng rất nhiều vào các ngành khác
nhau của khoa học và kỹ thuật. Nhiều bài toán thực tế có thể được giải quyết bằng
cách quy chúng về các bài toán tối ưu trên đồ thị. Biểu diễn đồ thị cho ta cách nhìn
trực quan giữa các quan hệ, ràng buộc của bài toán và từ đó giải quyết các bài toán
bằng những công cụ tính toán. Đề tài “Một số bài toán tối ưu trên đồ thị” nhằm tìm
hiểu một số nội dung như: Bài toán tìm cây bao trùm có trọng lượng nhỏ nhất, Bài
toán tìm đường có trọng lượng nhỏ nhất, Bài toán tìm luồng lớn nhất trong mạng vận
tải.
Nội dung chính của khóa luận gồm có năm chương:
Chương 1: Chương này trình bày các khái niệm cơ bản của đồ thị và các cách
biểu diễn đồ thị bằng mà trận.
Chương 2: Chương này trình bày bài toán tìm cây bao trùm có trọng lượng nhỏ
nhất và hướng dẫn sử dụng thuật toán Kruskal và thuật toán P rim để giải bài toán.
Chương 3: Nội dung chương này là trình bày bài toán tìm đường có trọng lượng
nhỏ nhất và hướng dẫn sử dụng thuật toán Dijkstra và thuật toán F ord − Bellman
để giải bài toán.
Chương 4: Chương này trình bày bài toán tìm luồng lớn nhất trong mạng vận
tải và hướng dẫn sử dụng thuật toán F ord − F ulkerson để giải bài toán này.
Chương 5: Chương này trình bày một số bài toán khác về luồng: tìm luồng lớn
nhất trong mạng vận tải đỉnh, tìm luồng lớn nhất trong mạng vận tải đỉnh - cung, tìm
luồng lớn nhất trong mạng vận tải có nhiều điểm phát và nhiều điểm thu.

1



Chương 1

MỘT SỐ KHÁI NIỆM CƠ BẢN
CỦA ĐỒ THỊ
Tất cả những đinh nghĩa sẽ dùng trong các chương sau.

1.1

Đồ thị có hướng

Định nghĩa 1.1 (Đồ thị có hướng). Một đồ thị có hướng G là một cặp có thứ tự
G = (V, E), trong đó V là một tập và E là một tập con của tích đề các V × V . Các
phần tử trong V được gọi là các đỉnh, các phần tử trong E được gọi là các cung trong
đồ thị có hướng G. Ví dụ, nếu (a, b) ∈ E thì a, b được gọi là đỉnh còn ab được gọi là
cung trong đồ thị có hướng G có đỉnh đầu là a, đỉnh cuối là b và có hướng đi từ a tới b.
Giả sử G = (V, E) là một đồ thị có hướng. Nếu (a, b) ∈ E thì các đỉnh a, b được
gọi là liên thuộc với cung (ab). Cung có dạng (a, a) với a ∈ V được gọi là khuyên.
Đồ thị có hướng được biểu diễn trên mặt phẳng bằng cách biểu diễn các đỉnh là
những vòng tròn nhỏ còn các cung được biểu diễn bằng các đường nối đỉnh đầu với
đỉnh cuối và có mũi tên hướng từ đỉnh đầu tới đỉnh cuối.
Ví dụ 1.1. Cho G = (V, E) có V = {v1 , v2 , v3 , v4 , v5 } và E = {(v1 , v2 ), (v1 , v3 ), (v3 , v2 ),
(v2 , v3 ), (v4 , v2 ), (v3 , v4 ), (v3 , v5 ), (v4 , v5 )} có đồ thị như hình 1.1

1.2

Đồ thị vô hướng

Định nghĩa 1.2 (Đồ thị có hướng). Một đồ thị vô hướng G là một cặp có thứ tự

G = (V, E), trong đó V là một tập và E là một tập với các phần tử là các đa tập lực
2


Khóa luận tốt nghiệp Đại học

Đào Thị Hoài Phương

Hình 1.1: Ví dụ một đồ thị có hướng

lượng 2 trên V . Các phần tử trong V được gọi là các đỉnh, các phần tử trong E được
gọi là các cạnh trong đồ thị vô hướng G. Nếu e = {a, b} ∈ E thì a, b được gọi là đỉnh
đầu mút của cạnh e. Ta kí hiệu cạnh a, b là ab.
Đồ thị vô hướng được biểu diễn trên mặt phẳng tương tự như đồ thị có hướng.
Các đỉnh được biểu diễn là những vòng tròn nhỏ còn các cạnh được biểu diễn bằng các
đường nối hai đỉnh của cạnh. Đồ thị vô hướng sẽ không có mũi tên chỉ hướng trên các
đường nối như đồ thị có hướng.
Ví dụ 1.2. Cho G = (V, E) có V = {v1 , v2 , v3 , v4 , v5 } và E = {(v1 , v2 ), (v1 , v3 ), (v3 , v2 ),
(v2 , v3 ), (v4 , v2 ), (v3 , v4 ), (v3 , v5 ), (v4 , v5 )}. Khi đó, G có đồ thị như hình 1.2

Hình 1.2: Ví dụ một đồ thị vô hướng

1.3

Đồ thị có trọng số

Định nghĩa 1.3 (Đồ thị có trọng số). Một đồ thị G = (V, E) được gọi là đồ thị có
trọng số nếu ít nhất một trong hai hàm f : V −→ WV và g : E −→ WE được xác định.
Trong đó, WV , WE là các tập mà các phần tử của chúng là các dữ liệu và mang một ý
3



Khóa luận tốt nghiệp Đại học

Đào Thị Hoài Phương

nghĩa định lượng nào đấy. Giá trị của f (v) với v ∈ V được gọi là trọng lượng đỉnh của
đỉnh v. Giá trị của g(e) với e ∈ E được gọi là trọng lượng cung của cạnh e. Tùy thuộc
vào việc những hàm nào được xác định, người ta kí hiệu đồ thị có trọng lượng bằng:
G = (V, E, f ) hoặc G = (V, E, g) hoặc G = (V, E, f, g).
Ví dụ 1.3. Cho G = (V, E, g) có V = {v1 , v2 , v3 , v4 , v5 }, E = {(v1 , v2 ), (v1 , v3 ), (v2 , v3 ),
(v3 , v2 ), (v4 , v2 ), (v3 , v4 ), (v3 , v5 ), (v4 , v5 )} và hàm g : E −→ N được xác định như sau:
g(v1 , v2 ) = 2,
g(v1 , v3 ) = 1,
g(v2 , v3 ) = 6,
g(v3 , v2 ) = 4,
g(v3 , v5 ) = g(v4 , v2 ) = 5,
g(v3 , v4 ) = 7,
g(v4 , v5 ) = 8.
Khi đó, G có đồ thị như hình 1.3

Hình 1.3: Ví dụ một đồ thị có trọng số

1.4
1.4.1

Đồ thị liên thông
Hành trình, đường, chu trình

Định nghĩa 1.4 (Hành trình). Giả sử G = (V, E) là một đồ thị có hướng. Một

hành trình có hướng trong G là một dãy v0 e1 v1 e2 ..., en vn trong đó vi ∈ V với mọi
i = 0, 1, ..., n, ei ∈ E với mọi i = 1, 2, ..., n và ei = (vi−1 , vi ). Khi đó, v0 được gọi
là đỉnh đầu, vn được gọi là đỉnh cuối và n là độ dài của hành trình có hướng trên.
Tương tự, một hành trình vô hướng trong đồ thị vô hướng G = (V, E) là một dãy
v0 e1 v1 e2 ..., en vn trong đó vi ∈ V với mọi i = 0, 1, ..., n, ei ∈ E với mọi i = 1, 2, ..., n và
4


Khóa luận tốt nghiệp Đại học

Đào Thị Hoài Phương

ei = (vi−1 , vi ) hoặc ei = (vi , vi−1 ). Khi đó, v0 được gọi là đỉnh đầu, vn được gọi là đỉnh
cuối và n là độ dài của hành trình vô hướng trên.
Một hành trình có hướng (hoặc vô hướng) được gọi là khép kín nếu đỉnh đầu và
đỉnh cuối của chúng trùng nhau.
Định nghĩa 1.5 (Đường). Một hành trình có hướng (hoặc vô hướng) được gọi là một
đường có hướng (hoặc vô hướng) nếu các đỉnh của chúng đều khác nhau.
Định nghĩa 1.6 (Chu trình). Một hành trình khép kín được gọi là chu trình nếu nó
có độ dài không nhỏ hớn 3 và khi xóa đi đỉnh cuối thì trở thành đường.
Ví dụ 1.4. Cho G = (V, E) có đồ thị như hình 1.4. Khi đó:
1) v1 e1 v2 e2 , v3 e5 v4 là một hành trình có hướng với đỉnh đầu là v1 và đỉnh cuối là v4 .
2) v1 e1 v2 e4 , v4 e5 v3 là một hành trình vô hướng với đỉnh đầu là v1 và đỉnh cuối là v3 .
3) v2 e2 v3 e6 , v5 e7 v4 e4 v2 là một hành trình có hướng khép kín.
4) v4 e4 v2 e3 , v3 e6 v5 e7 v4 là một hành trình vô hướng khép kín.

Hình 1.4: Ví dụ về hành trình trong đồ thị

1.4.2


Liên thông

Định nghĩa 1.7 (Liên thông). Giả sử G = (V, E) là một đồ thị (có hướng hoặc vô
hướng). G được gọi là liên thông nếu với hai đỉnh vi , vj khác nhau bất kì luôn tồn tại
một hành trình vô hướng trong G với đỉnh đầu là vi và đỉnh cuối là vj . Ngược lại, nếu
với hai đỉnh vi , vj khác nhau bất kì ta tìm được một cặp đỉnh (vi , vj ) mà giữa chúng
không tồn tại hành trình vô hướng trong G thì đồ thị được gọi là không liên thông.

5


Khóa luận tốt nghiệp Đại học

Đào Thị Hoài Phương

Trong trường hợp đồ thị không liên thông, nó sẽ tạo thành những đồ thị con liên
thông đôi một không có đỉnh chung. Những đồ thị con liên thông như vậy được gọi là
những thành phần liên thông.
Ví dụ 1.5. Đồ thị G = (V, E) trong Hình 1.5 là đồ thị không liên thông có 2 thành
phần liên thông là G1 = (V1 , E1 ) và G2 = (V2 , E2 ).

Hình 1.5: Đồ thị G = (V, E)

1.4.3

Cây

Định nghĩa 1.8 (Cây). Một đồ thị vô hướng liên thông không có khuyên và không có
chu trình được gọi là cây.
Ví dụ 1.6. Đồ thị G = (V, E) trong Hình 1.6 là một cây.


Hình 1.6: Đồ thị G = (V, E)

6


Khóa luận tốt nghiệp Đại học

1.5

Đào Thị Hoài Phương

Biểu diễn đồ thị bằng ma trận kề

Định nghĩa 1.9 (Ma trận kề của đồ thị). Giả sử G = (V, E) là một đồ thị vô
hướng (hoặc vô hướng) với V = {v1 , v2 , ..., vn }. Ta luôn xác định được ma trận:

A = (aij )n×n

với:




=



a11 a12 · · · a1n





a21 a22 · · · a2n 

..
..
..
.. 
.
.
.
. 

an1 an2 · · · ann


 1, nếu (v , v ) ∈ E
i j
aij =
 0, nếu (vi , vj ) ∈
/E

Khi đó, ma trận A được gọi là ma trận kề của đồ thị G.
Tính chất 1.1. Các tính chất của ma trận kề:
1. Ma trận kề của đồ thị vô hướng là ma trận đối xứng. Ma trận kề của đồ thị có
hướng không đối xứng.
2. Tổng số các phần tử trên dòng i (cột j) của ma trận kề chính bằng bậc của đỉnh
i (đỉnh j).
Ví dụ 1.7. Cho đồ thị G = (V, E) có V = {v1 , v2 , v3 , v4 , v5 } và E = {e1 , e2 , e3 , e4 , e5 , e6 , e7 }

có đồ thị như sau:

Hình 1.7: Đồ thị có hướng của ví dụ 1.7

7


Khóa luận tốt nghiệp Đại học

Đào Thị Hoài Phương

Ma trận kề của G là:


1 0 1

 1 0 0


A=
 0 1 0

 0 0 1

1 0 0

1.6

0 0





0 1 


0 0 


1 0 

1 0

Biểu diễn đồ thị bằng ma trận liên thuộc

Định nghĩa 1.10 (Ma trận liên thuộc của đồ thị). Giả sử G = (V, E) là một đồ
thị có hướng với V = {v1 , v2 , ..., vn } và E = {e1 , e2 , ..., em }. Ta luôn xác định được ma
trận:

B = (bij )n×m



b11 b12 · · · b1m







=



b21 b22 · · · b2m
..
..
..
..
.
.
.
.








bn1 bn2 · · · bnm
với:
bij =




 1,


nếu vi là đỉnh đầu của ej

−1, nếu vi là cuối nhưng không là đỉnh đầu của ej





0,

nếu vi không liên thuộc với ej

Khi đó, ma trận B được gọi là ma trận liên thuộc của đồ thị G.
Ví dụ 1.8. Cho đồ thị G = (V, E) có V = {v1 , v2 , v3 , v4 , v5 } và E = {e1 , e2 , e3 , e4 , e5 , e6 ,
e7 } có đồ thị như sau:

Hình 1.8: Đồ thị có hướng của ví dụ 1.8

8


Khóa luận tốt nghiệp Đại học

Đào Thị Hoài Phương

Ma trận liên thuộc của G là:


1


1

0

−1

0

0

0 −1

1

−1

0

0

0

0

1

−1 0

0


0

−1

1

0

0

0

0

0

0

1


 0 0
1


B=
 0 −1 0

 0 0
0


0 0 −1

1.7

0




0 


0 


−1 

1

Biểu diễn đồ thị có trọng số bằng các ma trận

Định nghĩa 1.11 (Ma trận trọng lượng cung). Giả sử G = (V, E, g) là một đồ
thị có hướng với V = {v1 , v2 , ..., vn } và g : E −→ WE là hàm trọng lượng cung của G.
Khi đó, ma trận:

C = (cij )n×n

với:
cij =





=






 g(vi , vj ),




c11 c12 · · · c1n




c21 c22 · · · c2n 

..
..
..
.. 
.
.
.

. 

cn1 cn2 · · · cnn
nếu (vi , vj ) ∈ E

0,

nếu i = j và (vi , vj ) ∈
/E

∞

nếu i = j và (vi , vj ) ∈
/E

được gọi là ma trận trọng lượng cung của đồ thị G.
Ví dụ 1.9. Cho đồ thị G = (V, E) có V = {v1 , v2 , v3 , v4 , v5 } và E = {e1 , e2 , e3 , e4 , e5 , e6 , e7 }
có đồ thị như sau:
Ma trận trọng lượng cung của G là:







C=







0

1

8

5

∞ ∞





∞ 

∞ ∞ 0 6 ∞ 4 


∞ ∞ ∞ 0 2 ∞ 


∞ ∞ ∞ ∞ 0 9 


∞


0

∞

7

3

∞ ∞ ∞ 10 ∞

0

Định nghĩa 1.12 (Ma trận trọng lượng đỉnh). Giả sử G = (V, E, f ) là một đồ thị
có hướng với V = {v1 , v2 , ..., vn } và f : V −→ WV là hàm trọng lượng đỉnh của G. Khi
9


Khóa luận tốt nghiệp Đại học

Đào Thị Hoài Phương

Hình 1.9: Đồ thị có hướng của ví dụ 1.9

đó, ma trận:


d1







D=



d2
..
.








dn
với
di = f (vi )
được gọi là ma trận trọng lượng đỉnh của đồ thị G.

10


Chương 2

BÀI TOÁN TÌM CÂY BAO TRÙM
CÓ TRỌNG LƯỢNG NHỎ NHẤT

Định nghĩa 2.1 (Cây bao trùm). Cho đồ thị G = (V, E) là đồ thị vô hướng liên
thông. Đồ thị T = (V , E ) ⊆ G được gọi là cây bao trùm của G nếu T là cây và
V =V.
Định nghĩa 2.2 (Trọng lượng của cây). Đồ thị G = (V, E, w) là đồ thị vô hướng
liên thông và w : E → R là hàm trọng lượng cạnh, T = (V , E ) là một cây bao trùm
của G. Khi đó, w(T ) =

w(e) được gọi là trọng lượng của cây T .
e∈E

2.1

Bài toán
Cho đồ thị có trọng số G = (V, E, w) với w là hàm trọng lượng cạnh. Tìm một cây

bao trùm T = (V, E ) của G để trọng lượng w(T ) của cây T là nhỏ nhất trong số các
trọng lượng của các cây bao trùm trong G.
Ví dụ 2.1. Khi xây dựng hệ thống đường bộ qua 63 tỉnh, thành phố trong nước. Người
ta tính toán được chi phí cho mỗi cung đường từ 2 thành phố bất kỳ. Bài toán đặt ra
là tìm tuyến đường đi qua tất cả các tỉnh, thành phố mà chi phí xây dựng là nhỏ nhất.

2.2

Thuật toán Kruskal

Thuật toán: Giả sử G = (V, E, w) là đồ thị có trọng số vô hướng liên thông có hàm
trọng lượng cạnh w : E → R, đồ thị con T = (V , E ) .
Bước 1: Khởi tạo: V := V, E := ∅. Mỗi thành phần liên thông của đồ thị T khi
11



Khóa luận tốt nghiệp Đại học

Đào Thị Hoài Phương

khởi tạo chỉ bao gồm một đỉnh, ta kí hiệu tập các thành phần liên thông của T là C.
Khi đó, C := {{x}|x ∈ V }
Bước 2: Sắp xếp các cạnh của G theo thứ tự trọng lượng không giảm.
Bước 3: Lấy cạnh đầu tiên ra khỏi dãy, kí hiệu là cạnh e = xy và xét:
Nếu hai đỉnh đầu mút x và y của e thuộc hai thành phần liên thông C1 , C2 khác
nhau của T thì S := S\{e}, E := E ∪ {e}, w(T ) := w(T ) + w(e) và ta nhập C1 và C2
thành một thành phần liên thông của T. Ngược lại, nếu hai đỉnh đầu mút x và y của
e không thuộc hai thành phần liên thông khác nhau của T thì S := S\{e}, E := E
và các thành phần liên thông của T không đổi.
Nếu E ∪ {e} chứa chu trình thì bỏ qua.
Bước 4: Nếu T còn là đồ thị không liên thông (|E | < |V | − 1) thì ta quay lại
bước 3. Ngược lại, nếu T là đồ thị liên thông (|E | = |V | − 1) thì dừng thuật toán và
đồ thị T khi đó chính là cây bao trùm có trọng lượng nhỏ nhất của đồ thị G.
Định lý 2.1. Với mọi đồ thị có trọng số vô hướng liên thông G = (V, E, w) có hàm
trọng lượng cạnh w : E → R, thuật toán Kruskal luôn tìm được một cây bao trùm có
trọng lượng nhỏ nhất của G.
Ví dụ 2.2. Cho đồ thị có trọng lượng G = (V, E, w) được biểu diễn như Hình 2.1.
Hãy tìm cây bao trùm có trọng lượng nhỏ nhất của G.

Hình 2.1: Trọng đồ của ví dụ 2.2

Giải
Bước 1: Khởi tạo:
V := V = {s, a, b, c, d, e, f, g, h, k, t},
E := ∅,

w(t) := 0,
12


Khóa luận tốt nghiệp Đại học

Đào Thị Hoài Phương

T := (V , E ),
C := {{s}, {a}, {b}, {c}, {d}, {e}, {f }, {g}, {h}, {k}, {t}}.
Bước 2: Sắp xếp các cạnh của đồ thị G theo thứ tự trọng lượng không giảm.
S := {ab, bc, ef, kt, hk, ed, sb, sa, sc, be, bd, ad, bf, f h, dh, gt, eh, cf, gh, dg, f k}.
Lần lặp 1
Bước 3: Lấy cạnh đầu tiên ab ra khỏi dãy và xét. Vì ab có các đỉnh đầu mút a và
b thuộc các thành phần liên thông khác nhau của T nên:
S := S\{ab} = {bc, ef, kt, hk, ed, sb, sa, sc, be, bd, ad, bf, f h, dh, gt, eh, cf, gh, dg, f k},
E := E ∪ {ab} = {ab},
C := {{s}, {a, b}, {c}, {d}, {e}, {f }, {g}, {h}, {k}, {t}}.
Bước 4: T là đồ thị không liên thông, quay lại bước 3.
Lần lặp 2
Bước 3: Lấy cạnh đầu tiên bc ra khỏi dãy và xét. Vì bc có các đỉnh đầu mút b và
c thuộc các thành phần liên thông khác nhau của T nên:
S := S\{bc} = {ef, kt, hk, ed, sb, sa, sc, be, bd, ad, bf, f h, dh, gt, eh, cf, gh, dg, f k},
E := E ∪ {bc} = {bc},
C := {{s}, {a, b, c}, {d}, {e}, {f }, {g}, {h}, {k}, {t}}.
Bước 4: T là đồ thị không liên thông, ta quay lại bước 3.
Lần lặp 3
Bước 3: Lấy cạnh đầu tiên ef ra khỏi dãy và xét. Vì ef có các đỉnh đầu mút e
và f thuộc các thành phần liên thông khác nhau của T nên:
S := S\{ef } = {kt, hk, ed, sb, sa, sc, be, bd, ad, bf, f h, dh, gt, eh, cf, gh, dg, f k},

E := E ∪ {ef } = {ef },
C := {{s}, {a, b, c}, {d}, {e, f }, {g}, {h}, {k}, {t}}.
Bước 4: T là đồ thị không liên thông, ta quay lại bước 3.
..
.
Tiếp tục thực hiện thuật toán tới lần lặp cuối cùng:
Lần lặp 16
Bước 3: Lấy cạnh đầu tiên eh ra khỏi dãy và xét. Vì eh có các đỉnh đầu mút e và
h thuộc các thành phần liên thông khác nhau của T nên:
13


Khóa luận tốt nghiệp Đại học

Đào Thị Hoài Phương

S := S\{eh} = {cf, gh, dg, f k},
E := E ∪ {eh} = {eh},
C := {{s, a, b, c, d, e, f, g, h, k, t}.
Bước 4: T là đồ thị liên thông, dừng thuật toán và đồ thị T := (T , E ) lúc này
chính là cây bao trùm có trọng lượng nhỏ nhất của đồ thị G.
Các bước của thuật toán được tóm tắt trong bảng sau:

14


Khóa luận tốt nghiệp Đại học

Lần
lặp


S

Đào Thị Hoài Phương

E’

C

{ab, bc, ef, kt, hk, ed, sb,
0

sa, sc, be, bd, ad, bf, f h,

{{s}, {a}, {b}, {c}, {d},
∅

{e}, {f }, {g}, {h}, {k}, {t}}

dh, gt, eh, cf, gh, dg, f k}

{{s}, {a, b}, {c}, {d}, {e},

1

{bc, ef, kt, ...}

{ab}

2


{ef, kt, hk, ...}

{ab, bc}

3

{kt, hk, ed...}

{ab, bc, ef }

4

{hk, ed, sb...}

{ab, bc, ef, kt}

5

{ed, sb, sa...}

6

{sb, sa, sc...}

7

{sa, sc, be...}

8


{f }, {g}, {h}, {k}, {t}}
{{s}, {a, b, c}, {d}, {e},
{f }, {g}, {h}, {k}, {t}}
{{s}, {a, b, c}, {d}, {e, f },
{g}, {h}, {k}, {t}}
{{s}, {a, b, c}, {d}, {e, f },
{g}, {h}, {k, t}}

{ab, bc, ef, kt,

{{s}, {a, b, c}, {d},

hk}

{e, f }, {g}, {h, k, t}}

{ab, bc, ef, kt,

{{s}, {a, b, c, d, e, f }, {g},

hk, ed}

{h, k, t}}

{ab, bc, ef, kt,

{{s, a, b, c, d, e, f }, {g},

hk, ed, sb}


{h, k, t}}

{sc, be, bd...}

—

—

9

{be, bd, ad...}

—

—

10

{bd, ad, bf...}

—

—

11

{ad, bf, f h...}

—


—

12

{bf, f h, dh...}

—

—

13

{f h, dh, gt...}

—

—

14

{dh, gt, eh...}

15

{gt, eh, cf...}

16

{eh, cf, gh...}


{ab, bc, ef, kt,
hk, ed, sb, f h}
—

{{s, a, b, c, d, e, f, h, k, t}, {g}}
—

{ab, bc, ef, kt,
hk, ed, sb, f h}

15

{{s, a, b, c, d, e, f, h, k, g, t}}


Khóa luận tốt nghiệp Đại học

2.3

Đào Thị Hoài Phương

Thuật toán Prim

Thuật toán: Giả sử G = (V, E, w) là đồ thị có trọng số vô hướng liên thông có hàm
trọng lượng cạnh w : E → R. Ta định nghĩa nhãn của đỉnh v là bộ [v, α(v)] với v ∈ V ,
a(v) ∈ R .
Bước 1: Khởi tạo:
V := V ,
E := ∅,

x := s(s − đỉnh bất kỳ trong V),
U := V \{s},
y := [s, ∞] với mọi y ∈ U .
Bước 2: Đổi nhãn

y :=




y,

nếu xy ∈
/ E hoặc xy ∈ E nhưng w(xy) ≥ α(y)

 [x, w(x)]

nếu xy ∈ E và w(xy) < α(y)

Bước 3: Tìm đỉnh vi sao cho α(vi ) đạt giá trị nhỏ nhất.
Bước 4: Gán x := vi (nếu tìm được nhiều đỉnh vi thỏa mãn ở bước 3 thì có thể
lấy một đỉnh tùy ý trong số những đỉnh vừa tìm được).
Bước 5: Gán E := E ∪ {xv}; U := \{x}.
Bước 6: Nếu U = ∅ thì quay lại Bước 2. Ngược lại, nếu U = ∅ thì dừng thuật
toán và đồ thị T khi đó chính là cây bao trùm có trọng lượng nhỏ nhất của đồ thị
G.
Định lý 2.2. Với mọi đồ thị có trọng lượng vô hướng liên thông G = (V, E, w) có
w : E → R là hàm trọng lượng cạnh, thuật toán Prim luôn tìm được một cây bao trùm
có trọng lượng nhỏ nhất của G.
Ví dụ 2.3. Hãy tìm cây bao trùm có trọng lượng nhỏ nhất bằng thuật toán Prim với

dữ kiện ở Ví dụ 2.2.
Giải
Bước 1: Khởi tạo:
V := V = {s, a, b, c, d, e, f, g, h, k, t},
E := ∅,
x := s,
y := [s, ∞] với mọi y ∈ U .
16


Khóa luận tốt nghiệp Đại học

Đào Thị Hoài Phương

Lần lặp 1
Bước 2: Gán:
a := [s, 3], b := [s, 4], c := [s, 4], d := [s, ∞], e := [s, ∞], f := [s, ∞], g :=
[s, ∞], h := [s, ∞], k := [s, ∞], t := [s, ∞].
Bước 3: Với mọi y ∈ U . Ta có: minα(y) = min(a) = 3.
Bước 4: Gán: x := a.
Bước 5: Gán: E := E ∪ {as} = {as}; U := \{a} = {b, c, d, e, f, g, h, k, t}.
Bước 6: U = ∅, ta quay lại Bước 2.
Lần lặp 2
Bước 2: Gán:
b := [a, 2], c := [s, 4], d := [b, 6], e := [b, ∞], f := [b, ∞], g := [s, ∞], h :=
[s, ∞], k := [s, ∞], t := [s, ∞].
Bước 3: Với mọi y ∈ U . Ta có: minα(y) = min(b) = 2.
Bước 4: Gán: x := b.
Bước 5: Gán: E := E ∪ {ab} = {bs, ab}; U := \{b} = {c, d, e, f, g, h, k, t}.
Bước 6: U = ∅, ta quay lại Bước 2.

Lần lặp 3
Bước 2: Gán:
c := [b, 2], d := [b, 5], e := [b, 4], f := [b, 6], g := [s, ∞], h := [s, ∞], k := [s, ∞],
t := [s, ∞].
Bước 3: Với mọi y ∈ U . Ta có: minα(y) = min(c) = 2.
Bước 4: Gán: x := c.
Bước 5: Gán: E := E ∪ {bc} = {bs, ab, bc}; U := \{c} = {d, e, f, g, h, k, t}.
Bước 6: U = ∅, ta quay lại Bước 2.
Lần lặp 4
Bước 2: Gán:
d := [b, 5], e := [d, 3], f := [c, 8], g := [s, ∞], h := [s, ∞], k := [s, ∞],
t := [s, ∞].
Bước 3: Với mọi y ∈ U . Ta có: minα(y) = min(f ) = 3.
Bước 4: Gán: x := f .
Bước 5: Gán: E := E ∪ {ab} = {sa, ab, bc, cf, }; U := \{f } = {d, e, g, h, k, t}.
17


Khóa luận tốt nghiệp Đại học

Đào Thị Hoài Phương

Bước 6: U = ∅, ta quay lại Bước 2.
..
.
Tiếp tục thực hiện thuật toán tới lần lặp cuối cùng:
Lần lặp 10
Bước 2: Gán: g := [t, 6].
Bước 3: Với mọi y ∈ U . Ta có: minα(y) = min(t) = 6.
Bước 4: Gán: x := t.

Bước 5: E := E ∪ {ab} = {sa, ab, bc, cf, f e, ed, dh, hk, kt, tg}; U := \{g} = ∅.
Bước 6: U = ∅, ta dừng thuật toán.
Đồ thị T := (T , E ) lúc này chính là cây bao trùm có trọng lượng nhỏ nhất của
đồ thị G.
Các bước của thuật toán được trình bày tóm tắt trong bảng sau:
Lần
a
b
c
d
e
f
g
h
lặp

k

t

0

[s,∞]

[s,∞]

[s,∞]

[s,∞]


[s,∞]

[s,∞]

[s,∞]

[s,∞]

[s,∞]

[s,∞]

1

[s,3]*

[s,4]

[s,4]

[s,∞]

[s,∞]

[s,∞]

[s,∞]

[s,∞]


[s,∞]

[s,∞]

2

—

[a,2]*

[s,4]

[a,6]

[s,∞]

[s,∞]

[s,∞]

[s,∞]

[s,∞]

[s,∞]

3

—


—

[b,2]*

[b,5]

[b,4]

[b,6]

[s,∞]

[s,∞]

[s,∞]

[s,∞]

4

—

—

—

[b,5]

[b,4]


[f,8]*

[s,∞]

[s,∞]

[s,∞]

[s,∞]

5

—

—

—

[b,5]

[f,2]*

—

[s,∞]

[f,6]

[f,12]


[s,∞]

6

—

—

—

[e,3]*

—

—

[s,∞]

[e,7]

[f,12]

[s,∞]

7

—

—


—

—

—

—

[d,10]

[d,6]*

[f,12]

[s,∞]

8

—

—

—

—

—

—


[h,9]

—

[h,3]*

[s,∞]

9

—

—

—

—

—

—

[h,9]

—

—

[k,2]*


10

—

—

—

—

—

—

[t,6]*

—

—

—

Các lần lặp của thuật toán Prim được thực hiện trong bảng trên với các hàng
là các lần lặp và các cột là tên các biến chứa nhãn của các đỉnh thuộc V \{s}. Nhãn
của đỉnh y ở lần lặp i sẽ được ghi tại giao của hàng i và cột y. Từ lần lặp 1, mỗi hàng
sẽ có một ô được có giá trị w(y) nhỏ nhất sẽ được đánh dấu *. Các lần lặp sau đó
nhãn của y sẽ không thể thay đổi được và ta ký hiệu là dấu gạch ngang. Khi ta thực
hiện tới lần lặp mà chỉ còn một nhãn được đánh dấu và các nhãn khác được đánh dấu
bằng dấu gạch ngang thì ta dừng thuật toán. Cây bao trùm có trọng lượng nhỏ nhất
18



Khóa luận tốt nghiệp Đại học

Đào Thị Hoài Phương

T = (V , E ) được xác định như sau: V = V và E là tập hợp tất cả các cạnh có dạng
xy với x là đỉnh được gán nhãn và y là đỉnh mà tại đó nhãn của x được đánh dấu *.

19