BỘ GIÁO DỤC
VÀ ĐÀO TẠO

VIỆN HÀN LÂM KHOA HỌC
VÀ CÔNG NGHỆ VIỆT NAM

HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
-----------------------------

Lê Thị Phương Loan

MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ: TOÁN HỌC

Hà Nội - 2019


BỘ GIÁO DỤC
VÀ ĐÀO TẠO

VIỆN HÀN LÂM KHOA HỌC
VÀ CÔNG NGHỆ VIỆT NAM

HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
-----------------------------

Lê Thị Phương Loan

MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ VÀ ỨNG DỤNG
Chuyên ngành: Toán ứng dụng

Khoa học và Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam trong
quá trình tôi thực hiện luận văn.
Tôi xin chân thành cảm ơn Viện Toán học và các thầy cô anh chị trong phòng
Cơ sở Toán học của Tin học đã tạo điều kiện thuận lợi cho tôi trong quá trình
học tập và nghiên cứu.
Xin cảm ơn các bạn học viên chuyên ngành Toán ứng dụng khoá 2017- 2019 đã
giúp đỡ, động viên tôi trong quá trình thực hiện luận văn.
Cuối cùng, luận văn chắc chắn sẽ không tránh khỏi những khiếm khuyết. Vì vậy
tôi rất mong nhận được sự đóng góp ý kiến của các thầy cô giáo và các bạn học
viên để luận văn này được hoàn chỉnh hơn.


1

MỤC LỤC

Lời cam đoan
Lời cảm ơn
Mục lục

1

Lời nói đầu

3

Danh sách bảng

5


17

2 BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ

19

2.1 BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT . . . . . . . . . . .

20

2.2 THUẬT TOÁN DIJKSTRA . . . . . . . . . . . . . . . . . . . .

21

2.2.1 Mô tả thuật toán . . . . . . . . . . . . . . . . . . . . . . .

21

2.2.2 Chứng minh tính đúng đắn của thuật toán . . . . . . . . . .

23

2.2.3 Độ phức tạp của thuật toán . . . . . . . . . . . . . . . . .

27


2
2.2.4 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


3.1 MÔ TẢ BÀI TOÁN . . . . . . . . . . . . . . . . . . . . . . . .

35

3.2 MÔ HÌNH ĐỒ THỊ . . . . . . . . . . . . . . . . . . . . . . . .

37

3.2.1 Phương pháp thế năng . . . . . . . . . . . . . . . . . . . .

37

3.2.2 Phương pháp PERT . . . . . . . . . . . . . . . . . . . . .

42

4 KẾT LUẬN VÀ KIẾN NGHỊ

46

4.1 KẾT LUẬN . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

4.2 KIẾN NGHỊ . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

TÀI LIỆU THAM KHẢO


4
Chương 2 Bài toán tìm đường đi ngắn nhất trên đồ thị Đây là phần chính
của luận văn. Trong chương này sẽ nêu ra bài toán, phương pháp giải, giả mã và
chứng minh tính đúng đắn của các thuật toán.
Chương 3 Ứng dụng: Bài toán lập kế hoạch Nêu ra một mô hình thực tiễn,
và cách áp dụng từ bài toán tìm đường đi ngắn nhất bên trên để giải quyết mô
hình đó.
Các khái niệm, nội dung trong luận văn được tham khảo từ các tài liệu [1], [2],
[3], [4], [5], [6] và viết lại theo ý hiểu của tác giả.


5

Danh sách bảng
3.1 Ví dụ mô hình dự án . . . . . . . . . . . . . . . . . . . . . . . .

36


6

Danh sách hình vẽ
1.1 Đơn đồ thị vô hướng(a) và có hướng(b) . . . . . . . . . . . . . . . .

9

1.2 Đơn đồ thị vô hướng có trọng số(a) và có hướng có trọng số (b) . . . .

9


25

2.4 Minh họa cho chứng minh ý 2 trường hợp 3.

. . . . . . . . . . . . .

26

. . . . . . . . . . . . . . . . . . . . .

27

2.6 Minh họa cho chứng minh trường hợp 2 . . . . . . . . . . . . . . . .

31

2.7 Thực thi thuật toán Bellman-Ford . . . . . . . . . . . . . . . . . . .

32

3.1 Đồ thị Conjunctive . . . . . . . . . . . . . . . . . . . . . . . . . .

38

3.2 Biểu diễn đồ thị của bảng 3.1 bằng phương pháp thế năng . . . . . . .

39

3.3 Biểu diễn kết quả bằng phương pháp thế năng . . . . . . . . . . . . .


thể tham khảo các tài liệu trong mục tài liệu tham khảo.

1.1.1

Các định nghĩa và thí dụ

Định nghĩa 1.1.1. Một đồ thị vô hướng G = (V, E) được xác định bởi:
• V là một tập khác rỗng gồm các đỉnh,
• E là tập các cặp đỉnh (không thứ tự), được gọi là cạnh. Hai đỉnh thuộc một
cạnh được gọi là các đầu mút của cạnh đó.
Trong khuôn khổ luận văn, ta xét các đồ thị hữu hạn, tức là có tập hợp đỉnh
hữu hạn.


8
Nếu giữa hai đỉnh bất kỳ có không quá một cạnh thì G được gọi là một đồ thị
đơn.
Định nghĩa 1.1.2. Một đồ thị có hướng G = (V, E) được xác định bởi:
• V là một tập khác rỗng gồm các đỉnh,
• E là một tập gồm các cạnh có hướng (hay cung), mỗi cạnh đi từ một đỉnh
đầu tới một đỉnh cuối.
Nếu với hai đỉnh u, v bất kỳ, có nhiều nhất một cạnh đi từ u tới v thì G được
gọi là một đồ thị đơn có hướng.
Nếu (a, b) ∈ E thì (a, b) được gọi là cạnh (cung) của G với đỉnh đầu là a, đỉnh
cuối là b và có hướng đi từ a tới b.
Ví dụ 1.1.1. a. Đồ thị vô hướng G = (V, E) trong đó:
V = {a, b, c, d, e, f },
E = {(a, b), (a, e), (b, e), (c, d)} (Hình 1.1.a)
b. Đồ thị có hướng G = (V, E) trong đó:
V = {a, b, c, d, e, f },

Định nghĩa 1.1.3. Một đồ thị con của đồ thị G là một đồ thị H = (W, F ) sao
cho W ⊂ V, F ⊂ E.
Tiếp sau đây là một số thuật ngữ cơ bản của lý thuyết đồ thị.


10
Trước tiên, ta xét các thuật ngữ mô tả các đỉnh và các cạnh của đồ thị vô hướng.
Nếu (u, v) là một cạnh nằm trong đồ thị G = (V, E) ta nói đỉnh v kề với đỉnh
u. Trong đồ thị vô hướng, quan hệ kề là đối xứng.
Nếu e = (u, v) là cạnh của đồ thị ta nói cạnh này là liên thuộc với hai đỉnh u và
v, hoặc cũng nói là nối đỉnh u và đỉnh v, đồng thời các đỉnh u và v sẽ được gọi
là các đỉnh đầu của cạnh (u, v).
Để biết có bao nhiêu cạnh liên thuộc với một đỉnh, ta dựa vào định nghĩa sau:
Định nghĩa 1.1.4. Bậc của một đỉnh trong một đồ thị vô hướng là số lượng các
cạnh liên thuộc trên nó.
Ký hiệu: deg(v).
Đỉnh v được gọi là đỉnh cô lập nếu deg(v) = 0.
Đỉnh v được gọi là đỉnh treo nếu deg(v) = 1.
Ta xét các thuật ngữ tương tự cho đồ thị có hướng
Tương tự với đồ thị vô hướng, ta có khái niệm về quan hệ kề đối với đồ thị có
hướng. Và trong một đồ thị có hướng, quan hệ kề không nhất thiết đối xứng.
Nếu v kề với u trong một đồ thị có hướng, đôi lúc ta viết u → v.
Nếu (u, v) là một cạnh trong một đồ thị G = (V, E) , ta nói rằng (u, v) liên
thuộc từ (incident from) đỉnh u và liên thuộc đến (incident to) đỉnh v.
Định nghĩa 1.1.5. Trong một đồ thị có hướng, bậc đi ra của một đỉnh là số
lượng cạnh rời khỏi nó, bậc đi vào của một đỉnh là số lượng cạnh nhập vào nó.
Bậc của một đỉnh trong đồ thị có hướng là bậc đi ra cộng bậc đi vào của nó.
Hay ta còn có thể viết dưới dạng sau:
Giả sử G = (V, E) là một đồ thị có hướng và v ∈ V . Kí hiệu:


12
(u, v) ∈ E.
Nếu G là một đồ thị có hướng thì tổng các chiều dài của tất cả các danh sách kề
là |E|, bởi mỗi cạnh (u, v) thể hiện v xuất hiện trong Adj[u].
Nếu G là một đồ thị vô hướng thì tổng các chiều dài của tất danh sách kề là
2|E|, vì nếu (u, v) là một cạnh vô hướng thì u xuất hiện trong danh sách kề của
v và ngược lại.
Danh sách kề có thể thay đổi để biểu diễn đồ thị có trọng số. Khi đó, trọng số
w(u, v) của cạnh (u, v) được lưu trữ với đỉnh v trong danh sách kề của u.
Một nhược điểm của phép biểu diễn danh sách kề đó là để xác định xem một
cạnh đã cho (u, v) có tồn tại trong đồ thị hay không, ta không còn cách nào
nhanh hơn là tìm kiếm v trong danh sách kề Adj[u].Có thể khắc phục nhược
điểm này bằng một phép biểu diễn ma trận kề của đồ thị, để đổi lại, ta phải
dùng nhiều bộ nhớ hơn.
Ví dụ 1.1.3. Hai phép biểu diễn đồ thị vô hướng Hình 1.1a.

(a) Biểu diễn danh sách kề của G

(b) Biểu diễn ma trận kề của G

Hình 1.3: Hai phép biểu diễn đồ thị vô hướng trong hình 1.1a

Ví dụ 1.1.4. Hai phép biểu diễn của đồ thị có hướng Hình 1.1b


13

(a) Biểu diễn danh sách kề của G

(b) Biểu diễn ma trận kề của G







1, nếu (vi , vj ) ∈ E


0, nếu (vi , vj ) ∈
/E


14
Dễ thấy rằng ma trận kề A của đồ thị có hướng G hoàn toàn xác định G. Vì
vậy, ma trận kề được coi là một biểu diễn của G. Ta có một số tính chất:
Tính chất 1.1.1.

i. Ma trận kề của đồ thị vô hướng là một ma trận đối xứng.

ii. Tổng các phần tử trên dòng i (cột j) bằng bậc của đỉnh tương ứng.
Cũng tương tự phép biểu diễn danh sách kề của một đồ thị, phép biểu diễn
ma trận kề có thể được dùng cho các đồ thị có trọng số. Khi đó, nếu G là một
đồ thị có trọng số, ta có ma trận
A = (aij )n×n
trong đó:

aij =



Xét một đồ thị vô hướng
Giả sử G = (V, E) là một đồ thị vô hướng. Một đường đi trong G là một dãy
v0 e1 v1 e2 v2 . . . en vn sao cho:
+ Với mọi i = 0, 1, 2, .., n, vi ∈ V ,
+ Với mọi i = 1, 2, . . . , n, ei ∈ E và ei = (vi−1 , vi ) hoặc ei = (vi , vi−1 ).
Khi đó, n được gọi là độ dài, đỉnh v0 được gọi là đỉnh đầu, đỉnh vn được gọi là
đỉnh cuối của đường đi trên.
Một chu trình là một đường có điểm đầu và điểm cuối trùng nhau.
Một đường đi đơn (chu trình đơn) là một đường đi (chu trình) không đi qua
cạnh nào quá một lần.
Xét một đồ thị có hướng
Hoàn toàn tương tự, ta có các định nghĩa với đồ thị có hướng.
Giả sử G = (V, E) là một đồ thị có hướng. Một đường đi trong G là một dãy
v0 e1 v1 e2 v2 . . . en vn sao cho:
+ Với mọi i = 0, 1, 2, .., n, vi ∈ V ,
+ Với mọi i = 1, 2, . . . , n, ei ∈ E và ei = (vi−1 , vi ).
Khi đó n được gọi là độ dài, đỉnh v0 được gọi là đỉnh đầu, đỉnh vn được gọi là
đỉnh cuối của đường có htoán lựa chọn đường truyền tin với chi phí nhỏ nhất trong mạng
thông tin,. . . Và để giải quyết những bài toán đó, 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ả. Trong chương
này chúng ta sẽ xét một số thuật toán như vậy.


20

2.1

BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT

Cho một đồ thị có hướng có trọng số G = (V, E, w). Độ dài một đường đi

độ khó là tương đương.
Bài toán thứ nhất là trường hợp con của bài toán thứ hai, và bài toán thứ hai là
trường hợp con của bài toán thứ tư.
Tuy nhiên, ta sẽ thấy rằng thực chất việc giải bài toán thứ nhất không đơn giản


21
hơn giải bài toán thứ hai, vì muốn tìm đường ngắn nhất giữa hai đỉnh, ta vẫn
phải khảo sát cả đồ thị.
Ngược lại, việc giải bài toán thứ hai lại thực sự đơn giản hơn bài toán thứ tư, và
một trong những thuật toán có độ phức tạp thấp để giải bài toán thứ tư là gọi n
lần bài toán thứ hai, mỗi lần chọn đỉnh nguồn là một đỉnh của đồ thị.

2.2

THUẬT TOÁN DIJKSTRA

Thuật toán Dijkstra được mang tên nhà khoa học máy tính người Hà Lan
Edsger Dijkstra vào năm 1956 và công bố năm 1959, là một thuật toán giải
quyết bài toán đường đi ngắn nhất nguồn đơn trong một đồ thị có hướng liên
thông không có cạnh mang trọng số âm.
Dữ kiện của bài toán quy về việc xét bài toán thứ nhất.
Trong phần này, ta sẽ tập trung vào mô tả thuật toán và chứng minh tính đúng
đắn của thuật toán. Độ phức tạp sẽ thừa nhận, không chứng minh.

2.2.1

Mô tả thuật toán

Thuật toán áp dụng cho các đồ thị liên thông có trọng số không âm.

d[u] := d[v] + d[v, u];
p[u] := v;
if {u ∈
/ Q} then
Q := Q ∪ {u};
end
end
end
S := S ∪ {v};
Q := Q \ {v};
end
end
Algorithm 1: Thuật toán Dijkstra


23

2.2.2

Chứng minh tính đúng đắn của thuật toán

Ta có nhận xét sau:
Nếu tại thời điểm t, d[u] < ∞ thì tồn tại một đường đi từ s đến u mà chỉ đi qua
những đỉnh thuộc S.
Trong quá trình chứng minh, ta kí kiệu thêm biến chỉ số thời gian, St , Qt , dt [v]
là S, Q, d[v] tại thời điểm t.
Gọi δ(v) là độ dài đường đi ngắn nhất từ s đến v trên đồ thị G.
Để chứng minh thuật toán trên đúng đắn, ta sẽ chứng minh các điều sau:
1. Nếu v ∈ St thì dt [v] = δ(v).
2. Nếu u ∈ Qt thì dt (u) là độ dài đường đi ngắn nhất từ s đến u mà chỉ đi qua

giả thiết quy nạp, ta có:
w(p) ≥ dt−1 [u] ≥ dt [u].

Hình 2.2: Minh họa cho chứng minh ý 2 trường hợp 1.


25
Trường hợp 2: Nếu p đi qua v nhưng v không phải đỉnh kề trước của u trong
p.
Gọi z là đỉnh liền trước u trong p (z = v).

Hình 2.3: Minh họa cho chứng minh ý 2 trường hợp 2.
Vì z thêm vào tại thời điểm t ≤ t − 1 nên theo giả thiết quy nạp, tồn tại một
đường đi ngắn nhất p từ s đến z sao cho p nằm trọn trong St−1 .
Suy ra δ(z) = dt−1 [z] = w(p ).
Ta gọi p1 là một đường đi từ s đến z qua v.
Khi đó, w(p1 ) ≥ dt−1 [z].
Đường p + (z, u) là một đường từ s đến u mà chỉ đi qua các đỉnh thuộc St−1
nên:
w(p + (z, u)) ≥ dt−1 [u].
Khi đó ta có:
w(p) = w(p1 ) + d[z, u]
≥ w(p ) + d[z, u]
≥ dt−1 [u]
≥ dt [u].
Vậy w(p) ≥ dt [u].