ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
ĐỀ TÀI
:
Giảng viên hướng dẫn: PGS.TS. ĐỖ VĂN NHƠN
Sinh viên thực hiện: LÊ KIM NGA
Mã số sinh viên: CH1301040
TPHCM, tháng 01/ 2014
2
THUẬT TOÁN & PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ GVHD: PGS.TS ĐỖ VĂN NHƠN
MỤC LỤC
MỤC LỤC
LỜI MỞ ĐẦU
PHẦN 1. GIỚI THIỆU TỔNG QUAN VỀ ĐỒ THỊ
1. 1.Nhắc lại một số định nghĩa:
1.1.1.Đồ thị: 5
1.1.2.Bậc của đỉnh: 5
1.1.3.Biểu diễn đồ thị bằng ma trận: 6
1.1.4.Tính liên thông: 6
1. 2.Giới thiệu về đẳng cấu đồ thị:
1.2.1.Khái quát chung: 6
1.2.2.Khái niệm về đẳng cấu đồ thị: 7
1.2.3. Những ứng dụng của đồ thị đẳng cấu: 8
PHẦN 2. VẤN ĐỀ SO KHỚP ĐỒ THỊ VÀ GIẢI PHÁP
2. 1.Bài toán so khớp đồ thị (đồ thị đẳng cấu):
2.1.1.Phát biểu bài toán: 9
2.1.2.Khảo sát, phân tích và giới hạn vấn đề: 9
2. 2.Xây dựng mô hình của bài toán:
2.2.1.Mô hình cho DIK: 10
2.2.2.Mô hình cho giả thiết: 10
2.2.3.Mô hình cho mục tiêu: 10

hỏi phải có nhiều phương pháp (giải pháp) để giải quyết được nhiều yêu cầu hay nhiều
vấn đề đặt ra trong đời sống hàng ngày như công tác lập lịch, tìm đường đi ngắn nhất
trên bản đồ giao thông, so khớp đồ thị để ứng dụng vào các lĩnh vực như hóa học, sinh
học, điện tử, … hay nhiều vấn đề khác đã và đang hình thành.
Những vấn đề trên đều gần giũi với đời sống hàng ngày và được nhiều nhà nghiên
cứu tìm hiểu, xây dựng nhiều giải pháp giải quyết khác nhau, tuy nhiên vẫn chưa đạt
được mong muốn vì còn một số hạn chế nhất định, ví dụ như độ phức tạp của thuật toán
quá lớn hoặc thời gian, hiệu quả chưa cao, …
Sau thời gian học tập môn Thuật toán và phương pháp giải quyết vấn đề do
PGS.TS Đỗ Văn Nhơn hướng dẫn, cùng với thời gian nghiên cứu, tìm hiểu từ các tài
liệu từ các bài báo khoa học, các luận văn trên Internet. Em chọn nghiên cứu giải pháp
cho bài toán so khớp đồ thị để làm tiểu luận môn học này.
Nội dung của tiểu luận bao gồm:
Phần 1: Giới thiệu tổng quan về lý thuyết đồ thị
Phần 2: Vấn đề so khớp đồ thị và giải pháp
Phần 3: Giới thiệu một thuật toán polynomial-time áp dụng vào bài toán so khớp
đồ thị.
Do thời gian nghiên cứu có hạn và bản thân em cũng có một số hạn chế nên tiểu
luận này chắc chắn sẽ không tránh khỏi những thiếu sót nhất định. Kính mong được sự
thông cảm và góp ý của PGS.TS Đỗ Văn Nhơn để hướng nghiên cứu sắp tới của em sẽ
hoàn thiện và đạt hiệu quả hơn. Em xin cảm ơn!
GIẢI PHÁP CHO BÀI TOÁN SO KHỚP ĐỒ THỊ HVTH: LÊ KIM NGA-CH1301040
5
THUẬT TOÁN & PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ GVHD: PGS.TS ĐỖ VĂN NHƠN
PHẦN 1. GIỚI THIỆU TỔNG QUAN VỀ ĐỒ THỊ
Lý thuyết đồ thị là một ngành khoa học được phát triển từ lâu nhưng lại có nhiều
ứng dụng hiện đại. Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ 18 bởi nhà toán
học Thụy Sĩ tên là Leonhard Euler. Ông đã dùng đồ thị để giải quyết bài toán 7 chiếc
cầu Konigsberg nổi tiếng.
Đồ thị cũng được dùng để giải các bài toán trong nhiều lĩnh vực khác nhau. Thí

1.1.3. Biểu diễn đồ thị bằng ma trận:
Định nghĩa:Cho đồ thị G=(V,E) (vô hướng hoặc có hướng), với V={v
1
,v
2
, ,
v
n
}. Ma trận liền kề của G ứng với thứ tự các đỉnh v
1
,v
2
, , v
n
là ma trận
ij 1 ,
( ) ( , ),
i j n
A a M n Z
≤ ≤
= ∈
trong đó a
ij
là số cạnh hoặc cung nối từ v
i
tới v
j
.
Như vậy, ma trận liền kề của một đồ thị vô hướng là ma trận đối xứng, nghĩa là
a

, e
2
, , e
n
của đồ thị sao
cho e
1
= (x
0
, x
1
), e
2
= (x
1
,x
2
), , e
n
= (x
n-1
,x
n
), với x
0
=u và x
n
=v. Khi đồ thị không có cạnh
(hoặc cung) bội, ta ký hiệu đường đi này bằng dãy các đỉnh x
0

nhãn cạnh (a1 – e1), (a2 – e2) thì ta có một ánh xạ f
1
tương ứng cho đỉnh và f
2
tương
ứng cho cạnh như sau:
Hình 2. Minh họa ánh xạ của tập đỉnh và tập cạnh đồ thị (a), (b)
Vì vậy, hai đồ thị được gọi là đẳng cấu với nhau nếu đỉnh của chúng được sắp
xếp lại để cấu trúc cạnh tương ứng là giống hệt nhau và để chứng tỏ rằng chúng đẳng
cấu thì cũng phải có sự sắp xếp lại tương tự với đỉnh (bằng cách dời đỉnh, dời cạnh )
sao cho hai đồ thị này có hình vẽ y hệt nhau trên cơ sở sự hoán vị đỉnh và hoán vị cạnh.
1.2.2. Khái niệm về đẳng cấu đồ thị:
Các đơn đồ thị G
1
= (V
1
, E
1
) và G
2
= (V
2
, E
2
) là đẳng cấu (Isomorphism) với
nhau nếu tồn tại một song ánh f như sau:
f: V
1

a

− Kiểm tra đồ thị con của chúng;
− Sử dụng ma trận liền kề;
− Việc sử dụng chu trình, đường đi đặc biệt nào đó;
− …
Vậy, nếu hai đơn đồ thị có ma trận kề (theo một thứ tự đỉnh nào đó) bằng nhau
thì chúng đẳng cấu với nhau.
Hình 3. Minh họa sự đẳng cấu dùng ma trận kề
1.2.3. Những ứng dụng của đồ thị đẳng cấu:
Đồ thị đẳng cấu được sử dụng để xác định một hợp chất hóa học trong cơ sở dữ
liệu hóa học hoặc để tìm kiếm, định danh và cung cấp thông tin trong cơ sở dữ liệu
hoặc web;
Đồ thị đẳng cấu còn được ứng dụng trong việc thiết kế mạch điện tử tự động hóa
nhằm đơn giản hóa và tối ưu mạch điện;
…
GIẢI PHÁP CHO BÀI TOÁN SO KHỚP ĐỒ THỊ HVTH: LÊ KIM NGA-CH1301040
9
THUẬT TOÁN & PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ GVHD: PGS.TS ĐỖ VĂN NHƠN
PHẦN 2. VẤN ĐỀ SO KHỚP ĐỒ THỊ VÀ GIẢI PHÁP
2. 1. Bài toán so khớp đồ thị (đồ thị đẳng cấu):
2.1.1. Phát biểu bài toán:
Cho hai đồ thị Graph A (GA) và Graph B (GB) có một số cạnh và một số đỉnh
tương ứng nào đó. Vấn đề đặt ra là xác định xem hai đồ thị đã cho có “khớp nhau”
(đẳng cấu) hay không?
Ví dụ cho hai đồ thị:
Hình 4. Ví dụ về 2 đồ thị GA và GB
2.1.2. Khảo sát, phân tích và giới hạn vấn đề:
2.1.2.1. Khảo sát và thu thập dữ liệu, thông tin và tri thức (DIK):
1. Tập đỉnh của 2 đồ thị là hữu hạn;
2. Tập cạnh của 2 đồ thị là hữu hạn;
3. Đồ thị có hướng hay vô hướng?

− Số đỉnh là số nguyên dương >= 2 và mỗi đỉnh được gán nhãn;
− Cạnh: là một đường nối giữa đỉnh này với đỉnh khác trong đồ thị
− Bậc của đỉnh x: Là tổng số cạnh liên thuộc với với đỉnh x, ký hiệu deg(x)
GA = (V
A
, E
A
)
V
A
= {x
1
, …, x
n
}
E
A
= {e
1
, …, e
m
}; e ∈ E
A
liên kết xi và xj
(Tương tự cho GB)
2.2.2. Mô hình cho giả thiết:
Input: 2 đồ thị được biểu diễn dưới dạng ma trận kề A và ma trận kề B
Output: GA và GB là hai đồ thị đẳng cấu với biểu song ánh f tương ứng
hoặc GA và GB không phải là hai đồ thị đẳng cấu.
2.2.3. Mô hình cho mục tiêu:

,
deg( )
i i j
A A=
∑
và lưu vào D
A
;
SortAcc(D
A
); // Sắp xếp D
A
tăng dần theo bậc;
Tính
,
deg( )
i i j
B B=
∑
và lưu vào D
B
;
// D
A
và D
B
là các mảng n phần tử chứa giá trị của bậc và nhãn
đỉnh
SortAcc(D
B

Lập ma trận kề B;
// Với dòng i của B là D
B
.Nhãn đỉnh thứ i;
// Với mỗi cột j của B là D
A
.Nhãn đỉnh thứ i;
}
If Isomorphism(A,B) then
{ Kết luận “GA đẳng cấu với GB” và kết thúc;}
Else k ← n-1;
GIẢI PHÁP CHO BÀI TOÁN SO KHỚP ĐỒ THỊ HVTH: LÊ KIM NGA-CH1301040
12
THUẬT TOÁN & PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ GVHD: PGS.TS ĐỖ VĂN NHƠN
}
2. 4. Chứng minh tính đúng đắn của thuật toán:
Sử dụng hai đồ thị ở hình 4 để chứng minh tính đúng đắn của thuật toán ở mục 2.3:
Bước 1: Ta có n = 5 (mỗi đồ thị có 5 đỉnh) và ma trận kề tương ứng cho GA, GB
như sau:
Hình 5. Ma trận kề tương ứng của GA và GB
Bước 2: Tính bậc của đỉnh là lưu và D
A
, D
B
+ Với GA: deg(A) = 3; deg(B) = 4; deg(C) = 2; deg(D) = 4; deg(E) = 3
 Ta có D
A
3.A 4.B 2.C 4.D 3.E
 D
A

+ Lập ma trận kề B:
C A E B D
1 0 0 0 1 1
4 0 0 1 1 1
5 0 1 0 1 1
2 1 1 1 0 1
3 1 1 1 1 0
 Ta thấy: A = B nên GA và GB là đẳng cấu.
2. 5. Đánh giá độ phức tạp của thuật toán:
− Trường hợp tốt nhất: Mỗi đồ thị có 2 đỉnh và 1 cạnh nối giữa 2 đỉnh đó. Trong
trường hợp này, độ phức tạp O là một hằng số;
− Trường hợp xấu nhất: Số đỉnh của các đồ thì lớn và bậc của các đỉnh bằng nhau
nhưng không tương ứng đôi một để có thể xây dựng được một hàm f tìm song ánh.
Trường hợp này, độ phức tạp O(n!)
2. 6. Đánh giá thực nghiệm:
Với thuận toán trên, nếu cho hai đồ thị cỡ càng nhỏ thì thuật toán mang lại hiệu
quả cao hơn. Tuy nhiên, trên thực tế, vấn đề so khớp đồ thị không chỉ dừng lại ở đồ thị
cỡ nhỏ và vô hướng có quan tâm đến trọng số (độ dài cạnh), …
Vì vậy, cần có thuật toán tối ưu hơn có thể giải quyết được vấn đề này.
Qua tìm hiểu và sưu tầm tài liệu, em xin giới thiệu một thuật toán có thể áp dụng
hiệu quả hơn để giải quyết vấn đề so khớp đồ thị phù hợp với thực tiễn. Nội dung giải
pháp và các thuật toán kèm theo được tóm tắt ở phần 3 của tiểu luận này!
GIẢI PHÁP CHO BÀI TOÁN SO KHỚP ĐỒ THỊ HVTH: LÊ KIM NGA-CH1301040
14
THUẬT TOÁN & PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ GVHD: PGS.TS ĐỖ VĂN NHƠN
PHẦN 3. GIỚI THIỆU MỘT THUẬT TOÁN POLYNOMIAL-TIME
ÁP DỤNG CHO BÀI TOÁN SO KHỚP ĐỒ THỊ
3. 1. Mở rộng bài toán so khớp đồ thị phù hợp với thực tế:
Trên thực tế, việc so khớp đồ thị có thể được thực hiện ở những đồ thị cỡ lớn và
thỏa một số yêu cầu khác như: có hướng, có trọng số, …

15
THUẬT TOÁN & PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ GVHD: PGS.TS ĐỖ VĂN NHƠN
Ngược lại, chúng ta sẽ thấy rằng các ma trận dấu hiệu S
A
*
và S
B
*
không thể được
thể hiện giống hệt nhau khi và chỉ khi các đồ thị và GA GB là không đẳng cấu. Do đó,
ta có một thuật toán polynomial-time để giải quyết các vấn đề đồ thị đẳng cấu, cho thấy
vấn đề đồ thị đẳng cấu là P.
3. 3. Các thủ tục sử dụng trong polynomial-time algorithm:
Ý tưởng rút ra từ thuật toán em nghiên cứu được có thể tóm tắt lại như sau:
Bước 1: Tìm độ dài đường đi ngắn nhất từ một đỉnh u đến đỉnh v thuộc đồ thị G (dùng
thuật toán Dijkstra (Procedure 3.3.1);
Bước 2: Dùng thuật toán 3.2.1 để tính toán độ dài đường đi ngắn nhất từ u đến v trong
đồ thị G’ với G’ = G \ uv (Procedure 3.3.2)
Bước 3: Xây dựng ma trận ký hiệu S và ma trận hình thức S
*
(Procedure 3.3.3)
− Với S là một ma trận gồm u hàng, v cột và S
uv
= ± d
uv
. n
uv
. m
uv
Trong đó:

Thủ tục này là thuật toán Dijkstra. Cho một đồ thị G và một đỉnh u, ta tính toán
khoảng cách ngắn nhất (u, v) đến tất cả các đỉnh v của G.
a(u, v) = 1 nếu uv ∈ E và a( u, v) = ∞ nếu uv ∉ E.
Tập Vknown lưu trữ các đỉnh mà khoảng cách ngắn nhất (u, v) đã tìm được và một
khoảng cách d’(u, w) cho mỗi đỉnh w ngoài V
known
.
 Khởi tạo: Thiết lập V
known
= {u} , d (u, u ) = 0 và d’ (u, w) = a (u, w) cho mỗi
đỉnh w bên ngoài V
known
.
 Lặp: Chọn đỉnh w
min
bên ngoài V
known
sao cho d’(u, w
min
) là ngắn nhất. Thêm w
min
vào V
known
và cập nhật các khoảng cách d’(u, w) = min { d’(u, w), d (u, w) + a (u,
w) } cho mỗi đỉnh w bên ngoài V
known
.
 Kết thúc: Lặp cho đến khi Vknown chứa tất cả các đỉnh của G hoặc cho đến khi
d ' (u, w) = ∞ ứng với mỗi đỉnh w bên ngoài Vknown . Trong trường hợp cuối,
GIẢI PHÁP CHO BÀI TOÁN SO KHỚP ĐỒ THỊ HVTH: LÊ KIM NGA-CH1301040

uv
. Mỗi đỉnh w của cặp đồ
thị g
uv
thu được theo cách này, bởi vì bất kỳ đường đi ngắn nhất (u, v) có chứa w
thu được bằng cách kết nối một đường ngắn nhất (u, w) với một đường (w, v)
trong G \ uv. Như vậy, ít nhất là một cặp đường đi ngắn nhất tìm thấy như trên
phải thỏa mãn u
r
= v
s
= w, với mỗi đỉnh w của đồ thị guv.
3.3.3. Proceduce 3.3.3:
 Sử dụng 3.3.2, cho mỗi cặp đỉnh u và v, ta tính toán khoảng cách d(u, v) trong
G\ uv và đồ thị g
uv
.
 Các phần tử tương ứng của hàng u và v cột của ma trận ký hiệu S được tính như
sau: S
UV
= ± d
uv
.n
uv
.m
uv
Trong đó:
 ± là ký hiệu cho biết có đường đi từ u đến v hay không. Nếu uv ∈ E thì
ký hiệu “+”, ngược lại, ký hiệu “–“
 d

i
(k)
là số lần ký hiệu s
k
xuất hiện ở hàng
i. Với S là một ma trận đối xứng , vector tần số ký hiệu cho cột i cũng giống như
các vector tần số ký hiệu cho dòng i (i = 1, 2, , n).
 Viết các vector tần số ký hiệu f
1
, f
2
, , f
n
trong bảng tham chiếu
1 2
, , ,
n
i i i
f f f
.
 Sắp xếp lại các hàng và cột của ma trận ký hiệu theo hoán vị i
1
, i
2
, ,i
n
từ các
đỉnh 1, 2, , n của G để có được ma trận hình thức S* .
GIẢI PHÁP CHO BÀI TOÁN SO KHỚP ĐỒ THỊ HVTH: LÊ KIM NGA-CH1301040
17

B
i'
n
), ta sắp xếp lại i''
1
,
i''
2
, , i''
n
của các đỉnh của GB nếu một trong hai phần từ đầu tiên của S
B
*
mà không phù
hợp với các phần tử tương ứng của S
A
*
ở chỉ số xuất hiện lớn nhất có thể trong hàng thứ
tự đầu tiên hoặc S
A
*
= S
B
*
.
 Gán A = S
A
*
và B = S
B

 Ngược lại, các vectơ tần số ký hiệu theo thứ tự trong bảng tham chiếu của S
A
*
và
S
B
*
là như nhau: (f
A
i
1
, f
A
i
2
, , f
A
i
n
) = (f
B
i'
1
, f
B
i'
2
, , f
B
i'

) = i''
2
, , φ (i
n
) = i''
n
.
3. 4. Ví dụ áp dụng:
Cho hai đồ thị GA, GB, mỗi đồ thị 10 đỉnh như hình 8:
GIẢI PHÁP CHO BÀI TOÁN SO KHỚP ĐỒ THỊ HVTH: LÊ KIM NGA-CH1301040
18
THUẬT TOÁN & PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ GVHD: PGS.TS ĐỖ VĂN NHƠN
Hình 8. Hình minh họa cho ví dụ
 Các ma trận kề tương ứng như sau:
Graph A:
Graph B:
 Ma trận hình thức và bảng tham chiếu của từng đồ thị:
GIẢI PHÁP CHO BÀI TOÁN SO KHỚP ĐỒ THỊ HVTH: LÊ KIM NGA-CH1301040
19
THUẬT TOÁN & PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ GVHD: PGS.TS ĐỖ VĂN NHƠN
 Ma trận sau khi sắp xếp lại dòng/ cột:
GIẢI PHÁP CHO BÀI TOÁN SO KHỚP ĐỒ THỊ HVTH: LÊ KIM NGA-CH1301040
20
THUẬT TOÁN & PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ GVHD: PGS.TS ĐỖ VĂN NHƠN
Tìm thấy dòng 3, cột 4 của ma trận B (gạch dưới) không phù hợp với ma trận A nên
thực hiện hoán đổi cột 4 và cột 5 (và hàng 4 với hàng 5). Ta được:
Tiếp tục tìm thấy sự không phù hợp đầu tiên ở hàng 3, cột 5. Ta so sánh giá trị và
đổi cột 5 với cột 8 (và hàng 5 với hàng 8). Ta thu được ma trận B như sau:
GIẢI PHÁP CHO BÀI TOÁN SO KHỚP ĐỒ THỊ HVTH: LÊ KIM NGA-CH1301040
21