ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
ĐOÀN NGỌC LÀNH
MỘT SỐ BÀI TOÁN
TỐI ƯU TỔ HỢP TRÊN ĐỒ THỊ
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - 2012
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
ĐOÀN NGỌC LÀNH
MỘT SỐ BÀI TOÁN
TỐI ƯU TỔ HỢP TRÊN ĐỒ THỊ
Chuyên ngành: TOÁN ỨNG DỤNG
Mã số : 60.46.36
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học: TS VŨ MẠNH XUÂN
Thái Nguyên - 2012
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Mục lục
Mở đầu 3
1 Tối ưu tổ hợp 5
1.1 Thuật toán và độ phức tạp của thuật toán . . . . . . . . . 5
1.1.1 Thuật toán . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.2 Độ phức tạp của thuật toán . . . . . . . . . . . . . 7
1.1.3 Đánh giá thời gian tốt nhất, tồi nhất và trung bình
của một thuật toán . . . . . . . . . . . . . . . . . . 10
1.2 Tối ưu tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.1 Bài toán tối ưu tổ hợp . . . . . . . . . . . . . . . . 13
1.2.2 Một số bài toán cụ thể . . . . . . . . . . . . . . . . 14
1.2.3 Bài toán lớp P và lớp NP . . . . . . . . . . . . . . 16

ưu trên đồ thị ngày càng được quan tâm và đã đạt được nhiều kết quả khả
quan. Đáng chú ý, việc chứng minh giả thuyết bốn màu có thể xem như
một minh chứng rõ nét về việc chứng minh bài toán nhờ máy tính điện
tử. Mặc dù có ý nghĩa thực tiễn cao nhưng lý thuyết đồ thị cũng chỉ mới
được đưa vào chương trình giảng dạy và nói chung còn sơ sài. Đề tài này
đặt vấn đề nghiên cứu những vấn đề cơ bản về thuật toán, độ phức tạp
thuật toán, m ột số bài toán tối ưu cụ thể trên đồ thị và trình bày thuật
toán cũng như kết quả tính toán với những bài toán cụ thể.
Nội dung của bản Luận văn gồm 2 chương.
Chương 1 trình bày khái quát về thuật toán, độ phức tạp của thuật
toán, nêu một số bài toán có độ phức tạp đa thức và không đa thức.
Chương 2 trình bày một số thuật toán giải một lớp những bài toán:
duyệt đồ thị, bài toán tìm đường đi ngắn nhất, bài toán luồng cực đại
và minh họa trên những ví dụ cụ thể.
Dù đã rất cố gắng, nhưng chắc chắn nội dung được trình bày trong luận
văn không tránh khỏi thiếu sót nhất định, em rất mong nhận được sự góp
ý của các thầy cô giáo và các bạn.
Luận văn này được hoàn thành dưới sự chỉ bảo và hướng dẫn tận tình
của TS Vũ Mạnh Xuân. Thầy đã dành nhiều thời gian hướng dẫn và giải
đáp các thắc mắc của tôi trong suốt quá trình làm luận văn. Em xin được
bày tỏ lòng biết ơn sâu sắc đến Thầy.
Tôi xin cảm ơn Sở Nội vụ, Sở Giáo dục và Đào tạo Tuyên Quang, trường
THPT Xuân Vân, Tổ Toán trường THPT Xuân Vân đã giúp đỡ tạo điều
kiện cho tôi hoàn thành khóa học này.
3
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Em xin gửi tới các thầy cô khoa Toán, phòng đào tạo sau đại học Trường
Đại học Khoa Học, Đại học Thái Nguyên cũng như các Thầy cô đã tham
gia giảng dạy khóa cao học 2010 - 2012, lời cảm ơn sâu sắc nhất về công
lao dạy dỗ trong suốt quá trình giáo dục, đào tạo của Nhà trường.

5
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
• Đầu ra (Output): Từ mỗi tập có các giá trị đầu vào, thuật toán sẽ
tạo ra các giá trị đầu ra tương ứng. Các giá trị đầu ra chính là nghiệm
(lời giải) của bài toán.
• Tính chính xác (Precision): Các bước của thuật toán phải được mô
tả chính xác. Ở mỗi bước, các thao tác phải hết sức rõ ràng, không
gây nên sự nhập nhằng, lộn xộn, tùy tiện, đa định nghĩa. Nói rõ hơn,
trong cùng một điều kiện hai bộ xử lý cùng thực hiện một bước của
thuật toán phải cho những kết quả như nhau.
• Tính hữu hạn hay tính dừng (Finiteness): Sau một số hữu hạn
bước thuật toán phải cho kết quả với mọi đầu vào.
• Tính đơn trị (Uniqueness): Các kết quả trung gian của từng bước
thực hiện thuật toán được xác định một cách đơn trị, chỉ phụ thuộc
đầu vào và các kết quả của các bước trước. Với hai bộ dữ liệu giống
nhau cho trước làm input, thuật toán đơn định sẽ thi hành các mã lệnh
giống nhau và cho kết quả giống nhau, còn thuật toán ngẫu nhiên có
thể thực hiện theo những mã lệnh khác nhau và cho kết quả khác
nhau.
• Tính tổng quát (Generality): Thuật toán có thể giải bất kỳ một bài
toán nào trong lớp các bài toán đang xét. Với thuật toán có đầu vào
là các bộ dữ liệu khác nhau trong một miền xác định thì có thể vận
dụng được thuật toán.
• Tính hiệu quả (The effectiveness): Hiệu quả về thời gian: Thuật
toán phải được thực hiện trong thời gian cho phép, điều này khác với
lời giải toán (chỉ cần chứng minh là kết thúc sau hữu hạn bước). Tính
hiệu quả về bộ nhớ: Kích thước của thuật toán phải đủ nhỏ để phù
hợp với khả năng lưu trữ.
Mô tả thuật toán: Có nhiều cách trình bày thuật toán, như dùng ngôn
ngữ tự nhiên, ngôn ngữ lưu đồ (sơ đồ khối), ngôn ngữ lập trình, ngôn ngữ

n
: integer);
Begin
Max:= a
1
;
for i:= 2 to n do
(* Nếu a
i
lớn hơn Max thì gán lại Max *)
if Max < a
i
then Max := a
i
;
End;
Thuật toán này trước hết gán số hạng đầu tiên a
1
của dãy cho biến Max.
Vòng lặp for được dùng để kiểm tra lần lượt các số hạng của dãy. Nếu
một số hạng lớn hơn giá trị hiện thời của Max thì nó được gán làm giá
trị mới của Max.
1.1.2 Độ phức tạp của thuật toán
Để đánh giá khả năng ứng dụng của chương trình ta cần phân tích tính
hiệu quả của thuật toán. Phân tích thuật toán là quá trình tìm ra những
đánh giá về thời gian tính cũng như dung lượng bộ nhớ cần thiết để thực
hiện thuật toán. Để đo tính hiệu quả của một thuật toán đã cho, ta thiết
lập mối quan hệ giữa thời gian tiến hành thuật toán, được diễn tả bởi số
các phép toán cơ bản với kích thước của bài toán đang xét, hoặc được diễn
tả bởi số các dấu hiệu cần thiết để mã hóa các dữ liệu của bài toán.

phải thực hiện, hoặc trong một số trường hợp cụ thể đếm số các phép tính
số học, so sánh, gán, mà thuật toán đòi hỏi thực hiện. Đây là tiêu chuẩn
khách quan để đánh giá tính hiệu quả của thuật toán.
Ví dụ 1.1.4. Kiểm tra số nguyên dương n có phải là nguyên tố không?
8
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Phân tích. Số nguyên dương n là số nguyên tố khi và chỉ khi n > 1 và n
chỉ có hai ước là 1 và chính nó hay n>1 và n không chia hết cho k với
2 ≤ k ≤ n −1
Mô tả thuật toán tựa pascal:
Input: Nhập số nguyên n;
Output: n số nguyên tố hoặc hợp số.
Procedure Nguyento(n);
Begin
ok:=True;
For i:=2 to n-1 do
If (n mod i =0) then ok:=False;
If ok then n_nguyên_tố else n_hợp_số;
End;
Độ phức tạp của thuật toán cỡ n. Ví dụ n=10000 thì chương trình trên
phải duyệt 99998 lần.
Nhận xét: Nếu n có ước thì có một ước không lớn hơn
n
2
. Khi đó thuật
toán được mô tả như sau.
Procedure Nguyento(n);
Begin
ok:=True;
For i:=2 to (n div 2) do

Thông thường trong các ứng dụng thực tế, thời gian chính xác mà thuật
toán đòi hỏi để thực hiện nó ít được quan tâm hơn so với việc xác định
mức độ tăng lên của thời gian thực hiện thuật toán khi kích thước của dữ
liệu đầu vào tăng lên. Chẳng hạn, một thuật toán đang được xem xét nào
đó có thời gian tính trong trường hợp tồi nhất là
t(n) = 60n
2
+ 6n + 6 với đầu vào kích thước n.
Bảng 1.1
n t(n) = 60n
2
+ 6n + 6 60n
2
10 6066 6000
100 600606 600000
1000 60006006 60000000
10000 6000060006 6000000000
Trên bảng 1.1, khi n càng lớn thì ta có thể xấp xỉ t(n) với số hạng 60n
2
.
Trong trường hợp này t(n) có tốc độ tăng giống như 60n
2
.
Nếu t(n) được tính bằng giây, thì t(n) = n
2
+ 0, 1n + 0, 1 sẽ cho ta thời
gian đo bằng phút của thuật toán. Như vậy khi mô tả tốc độ tăng thời
gian tính của thuật toán với kích thước đầu vào tăng, ta chỉ quan tâm đến
số hạng trội (60n
2

và N
2
∈ Z
∗
+
sao cho f(n) ≥ C
2
.g(n), với ∀n ≥ N
2
. Kí hiệu f(n) = Ω(g(n)).
10
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
• f(n) có bậc là g(n), nếu f(n) = O(g(n)) và f(n) = Ω(g(n)). Kí hiệu
f(n) = θ(g(n)).
Định nghĩa 1.1.6. Thời gian tính của thuật toán.
• Nếu thuật toán đòi hỏi thời gian tính tốt nhất là t(n) với đầu vào kích
thước n và t(n) = O(g(n)) thì thời gian tính tốt nhất của thuật toán có
bậc không quá g(n) hay thời gian tính tốt nhất của thuật toán là O(g(n)).
• Nếu thuật toán đòi hỏi thời gian tính tồi nhất là t(n) với đầu vào kích
thước n và t(n) = O(g(n)) thì thời gian tính tồi nhất của thuật toán có
bậc không quá g(n) hay thời gian tính tồi nhất của thuật toán là O(g(n)).
• Nếu thuật toán đòi hỏi thời gian tính trung bình là t(n) với kích thước
đầu vào là n và t(n) = O(g(n)) thì thời gian tính trung bình của thuật
toán có bậc không quá g(n) hay thời gian tính trung bình của thuật toán
là O(g(n)).
Trong định nghĩa trên nếu thay O bởi Ω và không quá bởi ít nhất, ta có
bậc ít nhất của thời gian tính tốt nhất, tồi nhất và trung bình của thuật
toán. Nếu thời gian tính tốt nhất của thuật toán vừa là O(g(n)) vừa là
Ω(g(n)) thì thời gian tính tốt nhất của thuật toán là θ(g(n)). Tương tự
như vậy, ta định nghĩa thời gian tính tồi nhất và trung bình của thuật

Begin
11
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ok := T rue; break;
end;
If i ≤ n then linear_seach := i else linear_seach := 0;
end;
Độ phức tạp của thuật toán: Thời gian tính của thuật toán có thể
đánh giá bởi số lần thực hiện câu lệnh trong vòng For
Nếu a
1
= x thì câu lệnh trong thân vòng lặp For thực hiện một lần. Do
đó thời gian tính tốt nhất của thuật toán là θ(1).
Nếu x không có mặt trong dãy đã cho, thì câu lệnh trong thân vòng lặp
For thực hiện n lần. Do đó thời gian tính tồi nhất của thuật toán là θ(n).
Thời gian tính trung bình của thuật toán. Nếu x tìm thấy ở vị trí thứ i
của dãy (x = a
i
) thì câu lệnh For phải thực hiện i lần (i = 1, 2, 3, , n),
còn nếu x không có mặt trong dãy đã cho thì câu lệnh For phải thực hiện
n lần. Từ đó suy ra số lần trung bình phải thực hiện câu lệnh lặp For là:
[(1 + 2 + + n) + n]
n + 1

n
2
+ n
n + 1
= n
Vậy thời gian trung bình của thuật toán là O(n).

Dạng đánh giá Tên gọi
θ(1) Hằng số
θ(log
2
n) Logarithm
θ(n) Tuyến tính
θ(nlog
2
n) nlog
2
n
θ(n
2
) Bậc hai
θ(n
3
) Bậc ba
θ(n
m
) Đa thức
θ(m
n
), m ≥ 2 Hàm mũ
θ(n!) Giai thừa
Trong bảng 1.2 các đánh giá được sắp xếp theo thứ tự tăng dần của tốc
độ tăng (ngoại trừ trường hợp θ(n
m
)).
Bảng 1.3 Đánh giá thời gian của thuật toán.
Đánh giá T/gian tính nếu n=

Định nghĩa 1.2.1. Bài toán tối ưu hóa tổ hợp được xác định bởi một tập
hữu hạn S và một ánh xạ f : S → R. Vấn đề đặt ra là xác định s
∗
∈ S sao
cho:
f(s
∗
) = min
s∈S
{f(s)}
13
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Bài toán tìm phần tử cực đại có thể chuyển về bài toán tìm phần tử cực
tiểu vì:
max
s∈S
{f(s
∗
)} = −min
s∈S
{−f(s)}
Hàm f(s) là hàm mục tiêu của bài toán, mỗi phần tử s ∈ S đươc gọi là
một phương án. Còn tập S gọi là tập các phương án của bài toán. Thông
thường tập S được mô tả như là tập các cấu hình tổ hợp được thỏa mãn
một số tính chất nào đó.
Phương án s
∗
∈ S đem lại giá trị nhỏ nhất cho hàm mục tiêu được gọi là
phương án tối ưu, khi đó giá trị f
∗

1
, T
2
, , T
n
. Rõ ràng ta có thể thiết lập
tương ứng 1 −1 giữa các hành trình
T
π(1)
→ T
π(2)
→ → T
π(n)
→ T
π(1)
,
kí hiệu Π tập tất cả các hoán vị π = (π(1), π(2), , π(n)) của n số tự
nhiên 1, 2, , n. Khi đó bài toán có thể phát biểu dưới dạng bài toán tối
ưu tổ hợp sau.
min{f(π) : π ∈ Π}.
Phương pháp giải đơn giản nhất là xét tất cả các cách đi để tìm chu trình
bé nhất, tức là phải duyệt n! phép toán thì suy ra hành trình tối ưu.
Vậy đây là bài toán tối ưu tổ hợp có độ phức tạp cỡ n!
14
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Bài toán 1.2.3. Bài toán cái túi. Một nhà thám hiểm cần đem theo
một cái túi có trọng lượng không quá b. Có n đồ vật có thể đem theo. Đồ
vật thứ j có trọng lượng a
j
và giá trị sử dụng c

j
.c
j
đạt giá trị cực đại.
Cách giải bài toán là duyệt tất cả dãy nhị phân có độ dài n tương đương
với bài toán tìm số tập con của X có n phần tử. Số các phép toán cần thực
hiện là 2
n
.
Đây là bài toán tối ưu tổ hợp có độ phức tạp của tính toán là 2
n
.
Bài toán 1.2.4. Nhân hai ma trận.
Cho hai ma trận A, B vuông cấp n. Tính tích A.B
Phân tích độ phức tạp của bài toán.
Ý tưởng giải bài toán: - Gọi ma trận vuông C là ma trận tích của hai ma
trận vuông A, B cùng cấp.
- Mỗi phần tử của C được tính theo công thức: C
i,j
=

A
i,k
∗ B
k,j
với
k = 1, , n.
Thuật toán tựa pascal.
(* Tính ma trận tích *)
For i:= 1 to n do

}; các biến Booles và một biểu thức Boole
đối với các số hạng của các biến này: E = C
1
∧ C
2
∧ ∧ C
n
trong đó
C
i
(i = 1, n) là một biểu thức: C
i
= u
j1
∧ u
j2
∧ ∧ u
jk(i)
với mỗi u
jq
là
một trong các biến của X. Bài toán đặt ra là tìm xem có một phân bố các
biến x
k
(k = 1, 2, , n) bằng 0 hay 1 sao cho E = 1.
Bài giải: Ta biết: 1 ∧ 1 = 1 và 1 ∧ 0 = 0 ∧ 1 = 0 ∧ 0 = 0; 1 = 0.
1 ∨0 = 0 ∨ 1 = 1 ∨ 1 = 1 và 0 ∨0 = 0; 1 = 0.
Như vậy đối với E = (x
1
∨ x

2
∨ x
3
) .
Câu trả lời là sai với x
1
= 0 hay 1, x
2
= 1, x
3
= 1.
Nghiệm của bài toán nhận biết chỉ là đúng hoặc sai và không đòi hỏi gì
hơn. Điều này phân biệt một cách cơ bản của bài toán nhận biết với các
bài toán tồn tại cũng như với các bài toán về sự phân bố phù hợp.
Định nghĩa 1.2.9. Cho bài toán tối ưu tổ hợp min
s∈S
{f(s)} (tương ứng với
max
s∈S
{f(s)}) và một số a. Định nghĩa "bài toán nhận biết liên hợp" là bài
toán: Liệu có tồn tại s ∈ S sao cho f(s)  a (tương ứng f(s)  a).
Ví dụ 1.2.10. Cho một tập gồm n thành phố, các khoảng cách giữa các
thành phố và một số a. Bài toán với nội dung là xác định xem có tồn tại
một vòng đi với giá nhỏ hơn hoặc bằng a là bài toán liên hợp của bài toán
người du lịch 1.2.2.
16
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Định lý 1.2.11. Nếu bài toán nhận biết liên hợp của bài toán tối ưu tổ
hợp đã cho là "khó" thì bài toán tối ưu hóa tổ hợp cũng là "khó".
Ký hiệu NP đặc trưng cho lớp các bài toán mà ta nghiên cứu bây giờ

Một số bài toán tối ưu tổ hợp trên
đồ thị
Đồ thị và mạng là mô hình khái quát của nhiều hệ thống thực tế như mô
hình tinh thể, cấu trúc phân tử, mạng điện, bản đồ giao thông, mạng máy
tính, Bên cạnh các bài toán tối ưu hóa tổ hợp cơ sở đã nêu thì trình
bày ứng dụng cụ thể về lớp bài toán tối ưu tổ hợp trên đồ thị là nhiệm vụ
của luận văn. Chương này trình bày một số khái niệm cơ bản và một số
thuật toán trên đồ thị.
2.1 Một số khái niệm
2.1.1 Đồ thị vô hướng
Định nghĩa 2.1.1. Đồ thị vô hướng G = (V, E) bao gồm V là tập các
đỉnh, và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của
V gọi là các cạnh.
Định nghĩa 2.1.2. Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề
nhau nếu (u, v) là cạnh của đồ thị G. 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).
Để có thể biết có bao nhiêu cạnh liên thuộc với một đỉnh, ta đưa vào định
nghĩa.
Định nghĩa 2.1.3. Ta gọi bậc của đỉnh v trên đồ thị vô hướng là số cạnh
liên thuộc với nó và sẽ ký hiệu là deg(v).
18
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 được gọi là đỉnh treo. Bậc của
đỉnh có tính chất sau.
Định lý 2.1.4. Giả sử G = (V, E) là đồ thị vô hướng với m cạnh. Khi đó
tổng bậc của tất cả các đỉnh bằng hai lần số cung.

v∈V

Định nghĩa 2.1.8. Nếu e = (u, v) là cung của đồ thị có hướng G thì ta
nói đỉnh v là kề của u, và nói cung (u, v) nối đỉnh u với đỉnh v hoặc cũng
nói cung này là đi ra khỏi đỉnh u và vào đỉnh v. Đỉnh u (v) sẽ được gọi là
đỉnh đầu (cuối) của cung (u, v).
19
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Định nghĩa 2.1.9. Ta gọi bán bậc ra (bán bậc vào) của đỉnh v trên đồ
thị có hướng là số cung của đồ thị đi ra khỏi nó (đi vào nó) và ký hiệu là
deg
+
(v) (deg
−
(v)).
Định lý 2.1.10. Giả sử G = (V, E) là đồ thị có hướng. Khi đó

v∈V
deg
+
(v) =

v∈V
deg
−
(v) = |E|.
Rất nhiều tính chất của đồ thị có hướng không phụ thuộc vào hướng trên
các cung của nó. Vì vậy, trong nhiều trường hợp sẽ thuận tiện hơn nếu ta
bỏ qua hướng trên các cung của đồ thị. Đồ thị vô hướng thu được bằng
cách bỏ qua hướng trên các cung được gọi là đồ thị vô hướng tương ứng
với đồ thị có hướng đã cho.
2.1.3 Đường đi, chu trình. Đồ thị liên thông

n−1
, x
n
).
Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường
đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình.
Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị
lặp lại.
Ví dụ 2.1.12. Xét đồ thị vô hướng cho trong hình 2.1.
Ta có: a, d, c, f, e là đường đi đơn độ dài 4. Còn d, e, c, a không là đường
đi, do (c, e) không phải là cạnh của đồ thị. Dãy b, c, f, e, b là chu trình
độ dài 4. Đường đi a, b, e, d, a, b có độ dài là 5 không phải là đường đi
đơn, do cạnh (a, b) có mặt trong nó hai lần.
Khái niệm đường đi và chu trình trên đồ thị có hướng được định nghĩa
hoàn toàn tương tự như trong trường hợp đồ thị vô hướng, chỉ khác là ta
có chú ý đến hướng trên các cung.
20
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình 2.1: Đường đi trên đồ thị.
Định nghĩa 2.1.13. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong
đó n là số nguyên dương, trên đồ thị có hướng G = (V, A) là dãy
x
0
, x
1
, , x
n−1
, x
n
,

b, e, d, a, b có độ dài là 5 không phải là đường đi đơn, do cạnh (a, b) có
mặt trong nó hai lần.
Nếu sử dụng đồ thị để biểu diễn mạng máy tính (trong đó các đỉnh của đồ
thị tương ứng với các máy tính, còn các cạnh tương ứng với các kênh nối)
câu hỏi đặt ra là hai máy tính bất kì có thể trao đổi thông tin với nhau
hoặc trực tiếp qua kênh nối chúng hoặc thông qua một vài máy tính trong
mạng trung gian không? Câu hỏi đó được phát biểu trong ngôn ngữ đồ thị
như sau: Tồn tại hay không đường đi giữa mọi cặp đỉnh của đồ thị? Để
trả lời câu hỏi đó ta xét định nghĩa.
Định nghĩa 2.1.15. Đồ thị vô hướng G = (V, E) được gọi là liên thông
nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.
21
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hai máy tính bất kì trong mạng có thể trao đổi thông tin được với nhau
khi và chỉ khi đồ thị tương ứng với mạng này là đồ thị liên thông.
Định nghĩa 2.1.16. Đồ thị có hướng G = (V, E) được gọi là liên thông
mạnh nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.
Định nghĩa 2.1.17. Đồ thị có hướng G = (V, E) được gọi là liên thông
yếu nếu đồ thị vô hướng tương ứng với nó là vô hướng liên thông.
2.2 Thuật toán tìm kiếm trên đồ thị
Sử dụng đồ thị coi như là một mô hình, ta cần kiểm tra các đỉnh: có thể
thực hiện việc kiểm tra này như một cuộc "dạo chơi" dọc theo các cạnh
(cung) mà theo đó ta đến thăm các đỉnh của đồ thị.
Định nghĩa 2.2.1. Một thủ tục cho phép chọn từ các đỉnh đã viếng thăm
một đỉnh tiếp theo trong cuộc dạo chơi là việc tìm kiếm trên đồ thị.
Đây chính là sự xác định một thứ tự trong việc kiểm tra các đỉnh. Cụ thể
hơn sự tìm kiếm đó như sau:
* Đánh số các đỉnh đã viếng thăm, ta nói số của một đỉnh biểu thị giờ
viếng thăm;
* Chọn một cạnh (cung) để đạt được đỉnh mới từ những đỉnh đã viếng

xét kề với v.
Như vậy, trong quá trình thăm đỉnh bằng thuật toán tìm kiếm theo chiều
sâu, đỉnh được thăm càng muộn càng sớm được duyệt xong (Last In First
Out_Vào sau ra trước). Mô tả quá trình này bằng một thủ tục đệ quy
DFS (Depth first search) như sau:
Procedure DFS(v);
(*Tìm kiếm theo chiều sâu bắt đầu từ đỉnh v;
Các biến Chuaxet, Ke, là toàn cục*)
Begin
Tham_dinh(v);
Chuaxet[v] := false;
for u ∈ Ke(v) do
if Chuaxet[u] then DFS(u);
end; (*đỉnh v là đã duyệt xong*)
Khi đó, tìm kiếm theo chiều sâu trên đồ thị được thực hiện bằng:
Thuật toán mô tả tựa pascal.
Input: Đồ thị G = (V, E); đỉnh xuất phát S;
Output: Danh sách các đỉnh sau khi duyệt.
Begin
(*Khởi tạo*)
for v ∈ V do Chuaxet[u]:= true;
for v ∈ V do
if Chuaxet[v] then DFS(v);
end.
Nhận xét: Rõ ràng lệnh gọi DF S(v) sẽ cho phép đến thăm tất cả các
đỉnh thuộc cùng thành phần liên thông với đỉnh v, bởi vì sau khi thăm
đỉnh là lệnh gọi đến thủ tục DFS đối với tất cả các đỉnh kề với nó. Mặt
khác, do mỗi khi thăm đỉnh v xong, biến Chuaxet[v] được đặt lại giá trị
23
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên