DANH MỤC TÀI LIỆU THAM KHẢO
MỤC LỤC
Nghiên cứu thuật toán so sánh hai đồ thị bằng phương pháp xây dựng 1
cây quyết định
DANH MỤC TÀI LIỆU THAM KHẢO
LỜI CẢM ƠN
Nghiên cứu thuật toán so sánh hai đồ thị bằng phương pháp xây dựng 2
cây quyết định
Đầu tiên em xin gởi lời cảm ơn chân thành đến thầy Đỗ Phúc – Giảng viên
cao học trường đại học Công nghệ thông tin tp. Hồ Chí Minh đã tận tình giảng dạy,
hướng dẫn em trong suốt môn học. Đồng thời cũng chính thầy Phúc đã gợi ý cho
em nghiên cứu đề tài này làm bài thu hoạch môn.
Do thời gian và khả năng còn hạn chế, chắc chắn bài thu hoạch sẽ còn nhiều
thiếu sót. Rất mong được ý kiến đóng góp của thầy, cô, và các bạn.
Xin chân thành cảm ơn!
DANH MỤC TÀI LIỆU THAM KHẢO
PHẦN I - TỔNG QUAN
Bài thu hoạch này tập trung nghiên cứu bài báo Subgraph Isomorphism in
Polynomial Time (SIPT) của 2 tác giả B.T.Messmer và H.Bunker, phân tích
những điểm mạnh, yếu của thuật toán đồng thời tìm cách tối ưu hóa thuật toán.
Những phân tích trong bài thu hoạch dựa theo những ý kiến của riêng em và góp
ý của cộng đồng mạng, tuy nhiên chưa được nhận xét của các chuyên gia nên có
thể còn tồn tại nhiều hạn chế sai sót.
Hiện nay, hai tác giả nêu trên đã xây dựng được một phương pháp mới để
nâng cấp thuật toán theo hướng giảm độ lớn của cây quyết định. Tuy nhiên đây
là tài liệu mới được cung cấp thu phí trên mạng nên em chưa có điều kiện
nghiên cứu thêm. Đó là một thiếu sót lớn và em sẽ cố gắng khắc phục trong thời
gian tới để mở rộng bài thu hoạch sử dụng cho các mục đích lớn hơn.
Nghiên cứu thuật toán so sánh hai đồ thị bằng phương pháp xây dựng 3
cây quyết định
DANH MỤC TÀI LIỆU THAM KHẢO

Thành phần đầu tiên sẽ là ô đầu tiên của ma trận. Các thành phần tiếp theo
sẽ là các ô kế cận bên phải và bên dưới của thành phần trước đó. Như vậy số
lượng thành phần sẽ lớn dần lên khi càng về cuối ma trận.
Lưu các thành phần này lại và tiếp tục phân tích tất cả các hoán vị của ma
trận.
Xây dựng cây quyết định của tất cả các thành phần trên theo thứ tự của
các thành phần bằng cách sau:
Ta phân nhóm các hoán vị của input graph thành các nhóm có thành phần
số 1 (đầu tiên) giống nhau. Mỗi nhóm sẽ là nút của cây quyết định, thành phần
số 1 sẽ là nhãn của nút đó.
Chọn một nhóm đã chia trong bước đầu tiên, ta lại tiếp tục phân nhóm
theo các nhóm có thành phần thứ 2 giống nhau. Tạo các nút của cây quyết định
theo như cách của bước 1.
Tiếp tục thực hiện các bước xây dựng cây quyết định với các nút còn lại
tương tự như cách trên. Cuối cùng ta sẽ có cây quyết định như sau:
Nghiên cứu thuật toán so sánh hai đồ thị bằng phương pháp xây dựng 5
cây quyết định
DANH MỤC TÀI LIỆU THAM KHẢO
2.2 Phân tích input graph thành một chuỗi tham số để đưa vào cây quyết
định
Cách phân tích input graph thành các thành phần cũng giống như trên.
Tuy nhiên ta chỉ thực hiện với đồ thị chính chứ không phải phân tích tất cả các
hoán vị của input graph như đã làm với model graph.
2.3 Đưa input graph đã được phân tích vào cây quyết định và đưa ra kết
quả
Chọn thành phần số 1 của input graph đưa vào cây quyết định đã tạo để
tìm đường đi. Nếu không có đường đi thì kết luận “Hai đồ thị không đẳng cấu
với nhau”. Nếu có thì thực hiện bước tiếp theo.
Chọn thành phần số 2 của input graph đưa vào cây quyết định để tìm
đường đi tiếp. Nếu không có đường đi thì kết luận “Hai đồ thị không đẳng cấu

Từ những phân tích nêu trên, ta có thể phân tích được những ưu khuyết
điểm của thuật toán như sau:
- Ưu điểm:
+ Áp dụng được cho tất cả những đồ thị có thể biểu diễn dưới dạng ma
trận (vô hướng, có hướng, có trọng số, có nhãn…).
+ Thời gian để so sánh 2 đồ thị rất ít.
+ Sử dụng một đồ thị để so sánh được nhiều lần với tốc độ rất nhanh
không đổi.
+ Giải quyết được bài toán đẳng cấu đồ thị, đẳng cấu đồ thị con, có thể sử
dụng để tính thêm độ sai khác giữa 2 đồ thị.
- Nhược điểm:
+ Thời gian lập cây quyết định ban đầu khá lớn.
+ Không thể áp dụng cho trường hợp so sánh từng cặp đồ thị khác nhau
từng đôi một.
+ Tốn khá nhiều bộ nhớ để chứa cây quyết định.
Nghiên cứu thuật toán so sánh hai đồ thị bằng phương pháp xây dựng 8
cây quyết định
DANH MỤC TÀI LIỆU THAM KHẢO
+ Để tìm được tất cả những nút giống nhau để tỉa bớt cây quyết định rất
khó khăn, để công việc tìm đơn giản hơn thì ta chỉ có thể tìm được một số rất ít
những nhánh giống nhau để tỉa bớt cây quyết định.
Nghiên cứu thuật toán so sánh hai đồ thị bằng phương pháp xây dựng 9
cây quyết định
DANH MỤC TÀI LIỆU THAM KHẢO
PHẦN III - Nâng cấp thuật toán
1 Phân tích thuật toán
Thuật toán dựa trên việc gộp tất cả các hoán vị của đồ thị vào một cây
quyết định. Việc tìm những nhánh có chu trình giống nhau rất hao tốn chi phí về
thời gian và bộ nhớ nên sẽ rất khó để thực hiện.
Bước yếu nhất trong thuật toán theo phân tích là bước xây dựng cây quyết

hoán vị một chuỗi cho trước theo các yêu cầu của mục trước. Yêu cầu mỗi lần
gọi sẽ đưa ra một hoán vị không trùng nhau của thuật toán sẽ được giải quyết
sau. Bước này ta chỉ tìm hiểu cách để tạo ra những hoán vị có độ sai khác nhau
nhỏ nhất trong mức có thể.
2.2.1 Hàm hoán vị
Sau khi xem xét các thuật toán hoán vị thông thường, ta rút ra kết luận
chung là các thuật toán hoán vị đều dựa trên việc đưa một đối tượng mới vào
xen kẽ một mảng đã hoán vị rồi bằng thuật toán đệ quy điển hình như sau:
Hàm đệ quy (mảng) trả về tất cả các mảng
{
Lấy ra phần tử đầu tiên của mảng.
For (i = độ lớn của mảng - 1)
{
Đưa phần tử đầu tiên vào vị trí thứ i của hàm đệ quy(mảng
con trừ đi phần tử đầu tiên)
Trả về mảng đưa vào.
}
}
Từ những phân tích trên, ta xây dựng thuật toán đệ quy như sau:
Nghiên cứu thuật toán so sánh hai đồ thị bằng phương pháp xây dựng 11
cây quyết định
DANH MỤC TÀI LIỆU THAM KHẢO
- Dịch phần tử đầu tiên tới 1 bước bằng cách hoán vị nó với phần tử sau
nó (ta tạm gọi là bước dịch phần tử).
- Tiếp tục dịch phần tử đó đến khi nó đến cuối mảng. Khi đến cuối mảng,
ta đưa nó trở về đầu mảng và dịch phần tử nhỏ hơn nó một đơn vị.
- Khi một phần tử được dịch thì phần tử sẽ được dịch tiếp theo được dịch
sẽ là phần tử trước nó một đơn vị (nếu có).
- Mỗi bước dịch sẽ trả về kết quả là mảng vừa mới dịch xong.
Ta sẽ được kết quả như sau (ví dụ trên mảng 4 phần tử):

10 2 3
12 0 3
12 3 0
1
02 1 3
20 1 3
21 0 3
21 3 0
2
02 3 1
20 3 1
23 0 1
23 1 0
Nghiên cứu thuật toán so sánh hai đồ thị bằng phương pháp xây dựng 13
cây quyết định
DANH MỤC TÀI LIỆU THAM KHẢO
3
01 3 2
10 3 2
13 0 2
13 2 0
4
03 1 2
30 1 2
31 0 2
32 1 0
5
03 2 1
30 2 1
32 0 1

03 2 1
4
03 1 2
30 1 2
31 0 2
32 1 0
!
3
13 2 0
13 0 2
10 3 2
01 3 2
Thoạt nhìn thuật toán có vẻ như xáo trộn ngẫu nhiên nhưng khi quan sát
kỹ. Ta có thể xây dựng thuật toán như sau:
- Dịch phần tử số 0 tới.
- Khi một phần tử tới cuối mảng, đảo chiều của nó và dịch phần tử lớn
hơn nó một đơn vị (theo chiều đã quy định trước)
- Trạng thái cuối mảng nêu trên được định nghĩa bằng trạng thái ở bên trái
(hoặc phải tùy theo chiều dịch chuyển) của đối tượng không có đối tượng nào
lớn hơn nó.
- Ta sẽ sử dụng một mảng để lưu chiều dịch chuyển của mảng.
Nghiên cứu thuật toán so sánh hai đồ thị bằng phương pháp xây dựng 15
cây quyết định
DANH MỤC TÀI LIỆU THAM KHẢO
- Hàm dừng khi số hoán vị đủ số n! (n là số phần tử).
Cách giải thích khá nhiều bước nhưng khi cài đặt ta sẽ sử dụng một đoạn
mã java như sau:
public ArrayList<String> next() {
// lan chay dau, khong chay ma tra ve ket qua ban dau
if (firstUse) {

(trong thuật toán dùng mảng integer) có số phần tử bằng với số đỉnh
của đồ thị.
- Một số int chỉ vị trí vừa dịch chuyển.
- Mảng hoán vị trước đó để so sánh.
- Số hoán vị đã thực hiện để làm điều kiện dừng.
Nghiên cứu thuật toán so sánh hai đồ thị bằng phương pháp xây dựng 16
cây quyết định
DANH MỤC TÀI LIỆU THAM KHẢO
Hàm hoán vị này thật sự có thể được xây dựng để thực hiện hoán vị mà
không cần lưu bất kỳ tham số nào. Tuy nhiên khi thực hiện theo phương
pháp đó ta sẽ phải tốn kém rất nhiều chi phí tính toán. Do đó theo đánh
giá hàm hoán vị như trên tạm thời đang là lựa chọn tốt nhất cho thuật toán
xây dựng cây quyết định cho đồ thị hiện nay.
2.2.2 Ứng dụng hàm hoán vị vào thuật toán
Khi sử dụng hàm hoán vị trên vào thuật toán, bài toán của chúng ta trở
nên hết sức đơn giản:
- Lập 1 cây quyết định đơn giản có n nút theo một hoán vị bất kỳ.
- Lấy hoán vị tiếp theo.
- Thêm 1 nút tại điểm vừa hoán vị và gắn kết với cây cũ bằng 2 đường đi
khác nhau.
Để cho dễ hiểu, ta có thể xem thêm ví dụ sau:
Nghiên cứu thuật toán so sánh hai đồ thị bằng phương pháp xây dựng 17
cây quyết định
DANH MỤC TÀI LIỆU THAM KHẢO
Nghiên cứu thuật toán so sánh hai đồ thị bằng phương pháp xây dựng 18
cây quyết định
DANH MỤC TÀI LIỆU THAM KHẢO
Mỗi hoán vị mới được tạo ra ta chỉ thêm vào cây quyết định cũ 1 nút và 2
đường đi do hoán vị mới chỉ có 2 đối tượng bị đảo vị trí so với hoán vị cũ.
Tổng kết thuật toán phân tích

Subgraph Isomorphism in Polynomial Time, B.T.Messmer và H.Bunker
Nghiên cứu thuật toán so sánh hai đồ thị bằng phương pháp xây dựng 21
cây quyết định