Lý thuyết đồ thị và ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
MỤC LỤC
MỤC LỤC 1
MỞ ĐẦU 1
MỞ ĐẦU
Lý thuyết đồ thị là ngành khoa học phát triển từ lâu đời nhưng lại có nhiều ứng
dụng hiện đại. Những ý tưởng cơ bản của nó đã được nhà Toán học Thụy sĩ vĩ đại
Leonhard Euler đưa ra từ thế kỷ 18. Ngày nay, lý thuyết đồ thị đã phát triển thành
Toán học có vị trí đăc biệt quan trọng về mặt lý thuyết cũng như ứng dụng, đặc biệt
là ứng dụng vào giải các bài toán tối ưu.
Bài toán Người du lịch (Travelling Salesman Problem) là một trong những bài
toán kinh điển và khó trong tin học. Có rất nhiều cách tiếp cận giải bài toán này
ngay từ khi nó mới ra đời, như sử dụng quy hoạch tuyến tính, nhánh và cận, nhưng
mới chỉ dừng lại ở các bộ dữ liệu nhỏ, không tìm được cách giải tối ưu và vẫn đang
được tiếp tục nghiên cứu và phát triển.
Với mong muốn bước đầu nghiên cứu về những bài toán tối ưu và cách giải
một số bài toán tối ưu cũng như tìm kiếm những phương pháp có thể giải tốt những
bài toán tối ưu, nhóm 5 chúng tôi đã chọn: “Bài toán người du lịch” (Traveling
salesman problem) cho đề tài nghiên cứu của môn học “Lý thuyết đồ thị và ứng
dụng”.
Đề tài gồm 2 chương xoay quanh nguyên lý bù trừ. Chương 1 nêu đại cương về
cơ sở lý thuyết của lý thuyết đồ thị, chương 2 nghiên cứu sâu về bài toán người du
lịch .

STT Họ tên Công việc
(theo mục lục)
Chữ ký Nhận xét của
giáo viên
1
2
3

Đồ thị hữu hạn là đồ thị có số cạnh (cung) hữu hạn.
 Định nghĩa 1.1.4.
Đồ thị đơn là đồ thị không có khuyên và không có cạnh song song.
 Định nghĩa 1.1.5.
Đồ thị vô hướng đủ là đồ thị mà mọi cặp đỉnh đều kề nhau.
 Định nghĩa 1.1.6.
Bậc của đỉnh v
∈
V là tổng số cạnh liên thuộc với nó và ký hiệu là deg(v). Nếu
đỉnh có khuyên thì mỗi khuyên được tính là 2 khi tính bậc, như vậy:
deg(v):= Số cạnh + 2*Số khuyên
Từ định nghĩa suy ra đỉnh cô lập là đỉnh có bậc bằng 0.
 Định nghĩa 1.1.7.
Đỉnh treo là đỉnh có bậc bằng 1.
 Định nghĩa 1.1.8.
Cho G = (V, E) là đồ thị có hướng nửa bậc ra của đỉnh v
∈
V, ký hiệu là deg
o
(v),
là số cung đi ra từ đỉnh v (v là đỉnh đầu) và nửa bậc vào của đỉnh v
∈
V, ký hiệu là
deg
1
(v), là số cung đi tới đỉnh v (v là đỉnh cuối).
 Hệ quả 1.1.9.
Cho đồ thị G = (V, E). Khi đó số đỉnh bậc lẻ của đồ thị vô hướng là số chẵn.
Đề tài: Bài toán người du lịch 2 Nhóm thực hiện: Nhóm 5
Lý thuyết đồ thị và ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến

có m đỉnh và tập V
2
có
n đỉnh và mỗi đỉnh của V
1
được nối với mỗi đỉnh của V
2
bằng một cạnh duy nhất.
1.1.2. Đường đi, chu trình, tính liên thông
 Định nghĩa 1.1.12. Cho đồ thị G = (V, E)
Dây
µ
từ đỉnh v đến w là tập hợp các đỉnh và cạnh nối tiếp nhau bắt đầu từ
đỉnh v và kết thúc tại đỉnh w. Số cạnh trên dây
µ
gọi là độ dài của dây
µ
.
Đường đi từ đỉnh v đến đỉnh w độ dài n đựợc biễu diễn như sau

µ
= (v,e
1
,v
1
,e
2
,v
2
, ,v

một lần.
Vòng có hướng là dãy có hướng có đỉnh đầu và đỉnh cuối trùng nhau.
Chu trình có hướng là đường đi có hướng có đỉnh đầu và đỉnh cuối trùng nhau.
Chu trình có hướng sơ cấp là chu trình có hướng không đi qua một đỉnh quá
một lần .
Đồ thị có hướng gọi là liên thông, nếu mọi cặp đỉnh của nó đều có đường đi nối
chúng với nhau.
Đồ thị có hướng gọi là liên thông mạnh, nếu mọi cặp đỉnh của nó đều có đường
đi có hướng nối chúng với nhau.
Đồ thị có hướng gọi là liên thông yếu, nếu đồ thị lót (vô hướng) của nó liên
thông.
Đồ thị có hướng gọi là bán liên thông, nếu với mọi cặp đỉnh (u,v) bao giờ cũng
tồn tại đường đi có hướng từ u đến v hoặc từ v đến u.
Đề tài: Bài toán người du lịch 3 Nhóm thực hiện: Nhóm 5
Lý thuyết đồ thị và ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
 Định lý 1.1.13.
• Trong đồ thị vô hướng mỗi dãy từ đỉnh v đến w chứa đường đi sơ cấp từ v đến
w
• Trong đồ thị có hướng mỗi dãy có hướng từ đỉnh v đến w chứa đường đi có
hướng sơ cấp từ v đến w.
 Định lý 1.1.14.
Đồ thị G lưỡng phân khi và chỉ khi G không chứa chu trình độ dài lẻ.
 Định nghĩa 1.1.15.
Trọng đồ (có hướng) là đồ thị (có hướng) mà mỗi cạnh (cung) của nó được gán
một số.
Trọng đồ được biễu diễn bởi G = (V, E, w), trong đó V là tập các đỉnh, E là tập
các cạnh (cung) và w: E
→
R là hàm số trên E, w(e) là trọng số của cạnh (cung) e với
mọi e

Tập hợp tách cạnh của đồ thị liên thông G là tập hợp các cạnh của nó mà khi
loại bỏ chúng thì G trở thành không liên thông.
 Định nghĩa 1.1.21.
Lát cắt là tập hợp tách cách cực tiểu.
 Định nghĩa 1.1.22.
Cầu là lát cắt có duy nhất một cạnh.
1.2. BIỂU DIỄN ĐỒ THỊ
1.2.1. Ma trận kề
1.2.1.1. Đồ thị vô hướng
 Định nghĩa 1.2.1.
Đề tài: Bài toán người du lịch 4 Nhóm thực hiện: Nhóm 5
Lý thuyết đồ thị và ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
Cho đồ thị vô hướng G = (V, E) có n đỉnh theo thứ tự v
1
,v
2
,v
3
, ,v
n
. Ma trận kề
của đồ thị G là ma trận vuông A=
nnij
a
×
)(
, trong đó
ij
a
là số cạnh nối

)(
. Khi đó
jic
ij
≠ ,
là số các đường đi chiều
dài k từ đỉnh V
i
đến đỉnh
j
V
.
 Hệ quả 1.2.3.
Cho đồ thị G = (V, E) có n đỉnh, V={v
1
,v
2
,v
3
,…,v
n
} và ma trận kề của đồ thị G
là ma trận
nnij
aA
×
= )(
. Ký hiệu
T = A+A
2

aA
×
= )(
, trong đó
ij
a
là số cung đi từ
i
v
tới
j
v
.
 Định lý 1.2.5.
Cho đồ thị có hướng G = (V, E) có n đỉnh,V={v
1
,v
2
,v
3
, ,v
n
} và ma trận kề của
đồ thị G là ma trận
nnij
aA
×
= )(
. Giả sử A
k

×
= )(
. Ký hiệu
T = A+A
2
+…+A
n-1
Khi đó
(i) Đồ thị G liên thông mạnh khi và chỉ khi các phần tử ngoài đường chéo chính
của ma trận T đều lớn hơn 0.
Đề tài: Bài toán người du lịch 5 Nhóm thực hiện: Nhóm 5
Lý thuyết đồ thị và ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
(ii) Đồ thị G có chu trình có hướng khi và chỉ khi tồn tại phần tử lớn hơn 0 trên
đường chéo chính của ma trận T.
1.2.2. Ma trận liên thuộc
1.2.2.1. Đồ thị vô hướng
 Định nghĩa 1.2.7.
Cho đồ thị G=(V,E) có n đỉnh,V= {v
1
,v
2
,v
3
, ,v
n
} và m cạnh E={e
1
,e
2
,e

1
∈∀=
∑
=
i
n
j
iji
vavd
.
Chú ý: Nếu đồ thị có 2 thành phần liên thông thì ta có thể đánh lại các đỉnh và
các cạnh kề có ma trận dạng
A
1
0
0 A
2

1.2.2.2.Đồ thị có hướng
 Định nghĩa 1.2.9.
Cho đồ thị có hướng G = (V, E) có n đỉnh.V={v
1
,v
2
,v
3
,…,v
n
} và m cung E={e
1

1.2.1. Định nghĩa 1.2.9
Cho đồ thị (có hướng) G = (V, E).
Chu trình (có hướng) Hamilton là chu trình sơ cấp qua mọi đỉnh của đồ thị.
Đường đi (có hướng) Hamilton là đường đi sơ cấp qua mọi đỉnh đồ thị.
Như vậy, mọi chu trình Hamilton có độ dài bằng số đỉnh và mọi đường đi
Hamilton có độ dài bằng số đỉnh trừ 1.
Đồ thị chứa chu trình (có hướng) Hamilton gọi là đồ thị Hamilton.
1.2.2. Điều kiện cần
Giả sử đồ thị G có chu trình Hamilton C. Khi đó:
• Đồ thị G liên thông.
• Mọi đỉnh của G có bậc lớn hơn hoặc bằng 2 và có đúng hai cạnh kề thuộc
chu trình C.
Đề tài: Bài toán người du lịch 6 Nhóm thực hiện: Nhóm 5
Lý thuyết đồ thị và ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
• Nếu xóa đi k đỉnh bất kỳ cùng các cạnh liên thuộc chúng thì đồ thị còn lại
sẽ có tối đa k thành phần liên thông.
1.2.3. Điều kiện đủ
 Định lý 1.2.10.
Đồ thị K
n
với n lẻ n
≥
3 có (n-1)/2 chu trình Hamilton từng đôi một không giao
nhau.
 Định lý 1.2.11. (Dirac)
Cho G là đồ thị đơn n đỉnh (n
)3≥
. Nếu bậc deg(v)
2
n

không còn cặp đỉnh nào như vậy nữa.
 Định lý 1.2.16.
Đồ thị G có chu trình Hamilton khi và chỉ khi bao đóng của G có chu trình
Hamilton.
 Định lý 1.2.17.
Nếu bao đóng C (G) = K
n
(n
3
≥
) thì đồ thị G có chu trình Hamilton.
 Định lý 1.2.18. (Định lý Ore)
Cho G là đơn đồ thị n đỉnh (n
≥
3). Nếu deg(u)+deg(v)
≥
n với mọi cặp đỉnh
không kề nhau thì đồ thị G có chu trình Hamilton.
 Định lý 1.2.1.9.
Cho G là đơn đồ thị n đỉnh (n
≥
3) và m cạnh. Nếu m
≥
C(n-1,2)+2 thì đồ thị G
có chu trình Hamilton.
 Định lý 1.2.20.
Cho đồ thị G là đồ thị lưỡng phân với hai tập đỉnh V
1
và V
2

 Định lý 1.2.22. (Konig)
Mọi đồ thị có hướng đầy đủ đều có đường đi Hamilton.
CHƯƠNG 2 : BÀI TOÁN NGƯỜI DU LỊCH
2.1. PHÁT BIỂU BÀI TOÁN
Một người du lịch muốn đi tham quan n thành phố 1,2,…,n. Xuất phát từ một
thành phố nào đó người du lịch đi qua tất cả các thành phố, mỗi thành phố chỉ qua
đúng một lần, rồi quay về thành phố ban đầu. Hỏi nên đi theo trình tự nào để độ dài
tổng cộng các đoạn đường đi qua là ngắn nhất (khoảng cách giữa hai thành phố có
thể hiểu là cự ly thông thường hoặc thời gian cần đi hoặc chi phí của hành trình và
xem như cho trước). Trò chơi này được Hamilton nghĩ ra năm 1859. Ông biểu diễn
các thành phố và các đường đibằng đa diện đều 20 đỉnh
Xét đồ thị đủ G = (V, E), với V={1, 2, , n}, có trọng số với trọng số c
ij
= c(i,j)
có thể khác c
ji
= c(j,i). Như vậy, ta có thể xem G như là một đồ thị có hướng đầy đủ
“mạnh” theo nghĩa với mọi i, j=1, 2, , n, i≠j, luôn có (i,j), (j,i)∈E. Bài toán trở
thành tìm chu trình Hamilton có độ dài ngắn nhất trong G.
2.2. GIẢI QUYẾT BÀI TOÁN
Hiện nay, phương pháp duy nhất được biết đến đảm bảo giải quyết tối ưu TSP
trong mọi trường hợp là xét tất cả các hành trình có thể và tìm ra hành trình nào có
chi phí nhỏ nhất. Mỗi hành trình như thế là một hoán vị của 1, 2, 3, , n với n là số
thành phố, do đó số hành trình là n!. Khi n lớn, số hành trình bùng nổ quá lớn ta
không thể tìm ra lời giải cho bài toán. Nhiều phương pháp tối ưu khác nhau được
dùng để giải quyết TSP và ta sẽ tìm hiểu chúng trong các mục sau:
2.2.1. Một số phương pháp giải
Xét bài toán người du lịch. Gọi C = {c
ij
: i,j = 1,2, ,n} là ma trận chi phí.

Với mỗi tập con này, ta sẽ tính cận dưới (chặn dưới đủ tốt) của các giá trị hàm
mục tiêu ứng với các phương án trong đó. Mang so sánh hai cận dưới vừa tính được,
việc tìm kiếm sẽ tìm trên tập con có cận dưới nhỏ hơn, tiếp tục phân chia tập con đó
thành hai tập con khác không giao nhau, lại tính các cận dưới tương ứng Lặp lại
quá trình này thì sau một số hữu hạn bước, cuối cùng sẽ được một phương án tốt,
nói chung là tối ưu, tức là phương án của bài toán người du lịch. Sau đó ta chỉ cần
xét những tập con có cận dưới nhỏ hơn giá trị hàm mục tiêu tìm được. Việc tính cận
dưới dựa vào thủ tục rút gọn.
2.2.2.2. Cơ sở lý luận của phép toán
Đề tài: Bài toán người du lịch 9 Nhóm thực hiện: Nhóm 5
Tập tất cả hành
trình
Các hành
trình qua (i,j)
Các hành
trình không
qua (i,j)
Lý thuyết đồ thị và ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
Nếu không xác định thành phố xuất phát thì có n! hành trình, mỗi hành trình
ứng với một hoán vị nào đó của tập {1,2,3, , n}. Còn nếu cho trước thành phố xuất
phát thì có tất cả là (n-1)! hành trình.
Giả sử v = (v(1),v(2), ,v(n),v(1)) (v là một hoán vị) là một hành trình qua các
thành phố v(1),v(2), ,v(n) theo thứ tự đó rồi quay về v(1) thì hàm mục tiêu
f(v) = C
v(1)v(2)
+ C
v(n-1)v(n)
+ C
v(n)v(1)
=

rj
=
α
nhỏ nhất trên dòng.
- Trừ tất cả các phần tử trên dòng đi một lượng
α
.
- Cộng dồn: Sum:=Sum+
α
(iii) Rút gọn cột:
Với mỗi cột c từ 1 đến n của ma trận C thực hiện:
- Tìm phần tử c
ie
=
α
nhỏ nhất trên cột.
- Trừ tất cả các phần tử trên cột đi một lượng
α
.
- Cộng dồn: Sum:= Sum+
α
.
Ví dụ: Cho ma trận chi phí của bài toán người du lịch với n = 6 như sau
1 2 3 4 5 6
α

1 3
2 4
3 16
4 7

1
2
3
4
5
6

α
0 0 15 8 0 0
Cộng dồn các hằng số rút gọn ta được:
Sum:=Sum+3+4+16+7+25+3=58.
- Rút gọn cột:
Các phần tử nhỏ nhất trên các cột theo thứ tự 1, 2, 3, 4, 5, 6 là 0, 0, 15, 8, 0, 0.
Trừ bớt các phần tử nhỏ nhất trên các cột theo thứ tự 1, 2, 3, 4, 5, 6 đi các hằng
số rút gọn tương ứng trên hàng ta được ma trận rút gọn.
1 2 3 4 5 6
1
2
3
4
5
6

Cộng dồn các hằng số rút gọn ta được:
Sum := Sum+0+0+15+8+0+0=58+15+8=81.
Vậy cận dưới cho tất cả hành trình là:
β
:=0+sum=81.
(nghĩa là không có hành trình có tổng chi phí nhỏ hơn 81).
2.2.2.4. Mệnh đề

49 0
3 21 48 0
∞
0
0 85 0 35 89
∞
Lý thuyết đồ thị và ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
2.2.2.5. Thủ tục phân nhánh
Giả sử ta chọn cạnh phân nhánh (r,s). Như vậy các hành trình sẽ được chia làm
hai tập: p
1
chứa các hành trình qua (r,s) và p
2
chứa các hành trình không qua (r,s).
+ Nhánh tập P
1
: Cận dưới
β
với giá trị xuất phát có từ thủ tục rút gọn.
- Giảm cấp ma trận chi phí C bằng cách loại dòng r và cột s.
- Ngăn cấm tạo hành trình con:
Cấm cạnh (s, r) bằng cách đặt c
sr
=
∞
.
Nếu (r,s) là cạnh phân nhánh thứ hai trở đi thì phải xét các cạnh đã chọn nối
trước và sau cạnh (r,s) thành dãy nối tiếp các cạnh như hình sau:
→ … → … →
(i,j) (r,s) (k,h)

hành trình sẽ được phân thành hai nhánh:
P
1
chứa các hành trình qua cạnh (6,3) và P
2
chứa các hành trình không qua
cạnh (6,3).
 Xét nhánh tập P
1
:
- Giảm cấp ma trận chi phí C bằng cách loại dòng 6 và cột 3.
- Ngăn cấm tạo hành trình con:
Cấm cạnh (6,3) bằng cách đặt c
36
=
∞
.
Ta nhận được ma trận chi phí tương ứng cùng cận dưới xuất phát
β
=81
1 2 4 5 6
1
2
3
4
5

Vì ma trận đã ở dạng rút gọn nên cận dưới vẫn giữ nguyên
β
= 81.

+(tổng hằng số rút gọn) cho nhánh.
1 2 3 4 5 6
1
2
3
4
5
6 α
= 48
Cột thứ 3 có giảm đi tất cả phần tử đi phần tử nhỏ nhất c
53
=48 và ta nhận được
ma trận rút gọc sau:
1 2 3 4 5 6
1
2
3
4
5
6
và cận dưới
β
=
β
+
α
= 81+48 = 129

5
∞
0 75 2 30 6
0
∞
58 30 17 12
29 1
∞
12 0 12
32 83 58
∞
49 0
3 21 48 0
∞
0
0 85
∞
35 89
∞
∞
0 75 2 30 6
0
∞
58 30 17 12
29 1
∞
12 0 12
32 83 58
∞
49 0

∞
.
- Xét các cặp (i,j) có c
ij
=0.
Cặp (1,2):minr=2; mins=1;

α
:= -
∞
<minr + mins =3 →
α
:=3; r:=1; s:=2;
Cặp (2,1): minr=12; mins:=3;

α
:= 3<minr + mins =15→
α
:=15; r:=2; s:=1;
Cặp (3,5) : minr=1; mins=17;

α
:= 15<minr + mins =18 →
α
:=18; r:=3; s:=5;
Cặp (4,6) : minr=32; mins=0;

α
:= 18<minr + mins =32 →
α

2
3
4
Đề tài: Bài toán người du lịch 14 Nhóm thực hiện: Nhóm
5
∞
0 2 30 6
0
∞
30 17 12
29 1 12 0
∞
32 83
∞
49 0
3 21 0
∞
0
∞
0 2 30 6
0
∞
30 17 12
29 1 12 0
∞
32 83
∞
49
∞
3 21 0

:
- Loại hàng 4 và cột 6 ta sẽ có ma trận chi phí cấp 4 tương ứng:
1 2 4 5
1
2
3

5

- Cấm tạo chu trình con:
Cạnh (6,3) chọn trước kế tiếp sau cạnh (4,6)
→ →
(4,6) (6,3)
Trong bước này ta cấm cạnh (3,4), bằng cách đặt c
34
=
∞
. Ta nhận được ma trận
1 2 4 5
1
2
3

5

Ma trận chi phí đã ở dạng rút gọn nên cận dưới
β
giữ nguyên
β
=81.

∞
30 17
29 1 12 0

3 21 0
∞

∞
0 2 30
0
∞
30 17
29 1
∞
0

3 21 0
∞

0 2 30

1
∞
0

21 0
∞

Lý thuyết đồ thị và ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
2 4 5

111
không qua (1,4) sẽ có cận dưới là
β
=
β
+28 = 84 + 28 = 112.
Tập P
1111
gồm các hành trình trong P
111
qua (1, 4) sẽ có ma trận chi phí cấp 2
tương ứng:
2 5

3

5
20
α
Cạnh (1,4) nối tiếp cùng các cạnh chọn trước là (6,3), (4,6) và (2,1) thành dãy
(2,1), (1,4), (4,6), (6,3)
nên ta phải cấm cạnh (3,2), bằng cách đặt c
32
=
∞
.
Rút gọn ma trận này ta được ma trận rút gọn.
2 5

3


20 0
∞
∞
0

20
∞
∞
0

0
∞

Lý thuyết đồ thị và ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
Mỗi hành trình có n cạnh. Sau khi đã chọn n-2 cạnh, ta phải chọn nốt 2 cạnh
còn lại. Lúc này ma trận rút gọn có bậc 2 và là một trong hai dạng sau:
(i) (ii)
u v u v
p p
q q
cùng cận dưới
β


81 P
2
129 P
1

81 P
12
113
P
11
81 P
112
101
P
111
Đề tài: Bài toán người du lịch 17 Nhóm thực hiện: Nhóm
5
0
∞

∞
0

∞
0
0
∞


P
1111
104
Chọn tiếp hai cạnh còn lại ta có hành trình:
P = (1,4),(4,6),(6,3),(3,5),(5,2),(2,1) và chi phí c
p
=104
Qua sơ đồ trên ta thấy các nhánh P
2
, P
12
, P
1112
có cận dưới lớn hơn c
p
=104, vì
thế các hành trình của các nhánh đó có tổng chi phí lớn hơn c
p
. Chỉ có nhánh P
112
có
cận dưới là 101 nhỏ hơn c
p
. Tiếp theo ta tìm hành trình mới theo nhánh này.
 Nhánh P
112
sẽ có ma trận chi phí cấp 4 tương ứng:
1 2 4 5
1

1122
gồm các hành trình không qua
cạnh (5,1) có cận dưới bằng 101+26 = 127 > 104 = c
p
. Ta loại không xét nhánh này
nữa.
 Nhánh P
1121
gồm các hành trình qua cạnh (5,1) có ma trận chi phí
2 4 5
1
2
3

Đề tài: Bài toán người du lịch 18 Nhóm thực hiện: Nhóm
5
Hành trình
chứa (1,4)
Hành trình
chứa (2,1)
Hành trình
không chứa
(1,4)
∞
0 2 30
∞

∞
30 17
29 1

α
(c
15
=
∞
để cấm cạnh (1,5)).
Rút gọn ma trận chi phí ta có ma trận rút gọn
2 4 5
1
2
3
với cận dưới
β
=
β
+
α
= 101+2 = 103.
Chọn (1,4) làm cạnh phân nhánh. Nhánh P
11212
gồm các hành trình không
qua cạnh (1,4) có cận dưới bằng 103+11 = 114 > 104 = c
p
. Ta loại không xét
nhánh này nữa.
 Nhánh P
11211
gồm các hành trình qua cạnh (1,4) có ma trận chi phí

2 5

b) Nếu trái lại thì phải xuất phát từ đỉnh treo nào có cận dưới nhỏ hơn để
phân nhánh tiếp tục và kiểm tra xem điều kiện a) có thỏa mãn không.
2.3.CÀI ĐẶT CHƯƠNG TRÌNH
Đề tài: Bài toán người du lịch 19 Nhóm thực hiện: Nhóm
5
0 0 30

∞
11 0
1
∞

∞∞
0
1
∞∞
0
0
∞

Lý thuyết đồ thị và ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
2.3.1. Đầu vào
Đầu vào là ma trận chi phí kích thước n.
Ví dụ: Đầu vào là ma trận chi phí với số đỉnh là n = 6 như sau.

F,G : Text;
Gd,Gm :Integer;
B: Array[1 Maxvar] Of Diem;
{***********************************}
Procedure Input (Var N : Integer;
Var Inf : Integer;
Var C : Arrnn);
Var I,J,L,K :Integer; S:String[6];
Đề tài: Bài toán người du lịch 20 Nhóm thực hiện: Nhóm
5
Lý thuyết đồ thị và ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
Begin
Assign(F,'Travel.Inp'); Reset(F);
Readln(F,N);
Str(N,S);
Settextstyle(3,0,1);
Outtextxy(5,20,S);
Inf := 9999;
L:=-40;
K:=50;
For I := 1 To N Do
Begin
For J := 1 To N Do
Begin
Read(F,C[I,J]);
Str(C[I,J],S);
L:=L+45;
K:=K;
Outtextxy(L,K,S);
If J=N Then Begin

Begin
If I <= J Then Min:=I Else Min :=J
End; { Min }
{Thu Tuc Rut Gon }
Function Reduce(Var Row,Col,Rowred,Colred:Arrn):Integer;
Var I,J,Sum,Temp:Integer;
Begin
Sum:=0;
For I:=1 To Size Do
Begin { Reduce Rows }
Temp:=Oo;
For J:=1 To Size Do Temp:=Min(Temp,C[Row[I],Col[J]]);
If Temp > 0 Then
Begin
For J:=1 To Size Do
If C[Row[I],Col[J]] < Inf Then
C[Row[I],Col[J]]:=C[Row[I],Col[J]]-Temp;
Sum:=Sum+Temp
End;
Rowred[I]:=Temp
End; { For I }
For J:=1 To Size Do
Begin { Reduce Columns }
Temp:=Inf;
For I:=1 To Size Do Temp:=Min(Temp,C[Row[I],Col[J]]);
If Temp > 0 Then
Begin
For I:=1 To Size Do
If C[Row[I],Col[J]] < Inf Then
C[Row[I],Col[J]]:=C[Row[I],Col[J]]-Temp;

If (Minrowelt+Mincolelt) > Most Then
Begin
Most:=Minrowelt+Mincolelt;
R:=I;{Chi So Dong Cua Canh Tot Nhat}
S:=J;{Chi So Cot Cua Canh Tot Nhat}
End;
End; { If W[Row[I],Col[J]] = 0, For J, I }
End; { Bestedge }
{******************************************************}
Begin { Body Of Explore }
Size:=N-Edges;
Cost:=Cost+Reduce(Row,Col,Rowred,Colred);
If Cost < Mincost Then
If Edges = (N-2) Then
Begin { Bo Sung Not Hai Canh Con Lai}
For I:=1 To N Do Best[I]:=Fwdptr[I];
If C[Row[1],Col[1]] = Inf Then Avoid:=1
Đề tài: Bài toán người du lịch 23 Nhóm thực hiện: Nhóm
5
Lý thuyết đồ thị và ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
Else Avoid:=2;
Best[Row[1]]:=Col[3-Avoid];
Best[Row[2]]:=Col[Avoid];
Mincost:=Cost
{Ghi Nhan Hanh Trinh Tot Nhat}
End { If Edges = (N-2) }
Else
Begin
Bestedge(R,S,Most);
Lowerbound:=Cost+Most;

Đề tài: Bài toán người du lịch 24 Nhóm thực hiện: Nhóm
5
Lý thuyết đồ thị và ứng dụng GVHD: PGS.TSKH Trần Quốc Chiến
Row[I]:=I; Col[I]:=I;
Fwdptr[I]:=0; Backptr[I]:=0
End;
Mincost:=Inf;
Explore(0,0,Row,Col);
Index:=1;
For I:=1 To N Do
Begin
Route[I]:=Index;
Index:=Best[Index];
End;
End; { Babtsp }
{********************************************}
Procedure Initgraphh;
Begin
Gd:=Detect;
Initgraph(Gd,Gm,'Bgi');
If Graphresult<>Grok Then
Begin
Writeln('Kiem Tra Loi Duong Dan');
Readln;
Halt(1);
End;
End;
{*************************************************}
Procedure Begingraph( X,Y:Integer);
Var