MỤC LỤC

MỤC LỤC_____________________________________________________________1
LỜI NÓI ĐẦU__________________________________________________________2
TỔNG QUAN__________________________________________________________3
Đẳng cấu đồ thị con với thời gian đa thức._____________________________________4
TỔNG KẾT VÀ HƯỚNG DẪN SỬ DỤNG CHƯƠNG TRÌNH__________________46
Tác giả bài báo trên đã chỉ ra cho chúng ta thấy một hướng tiếp cận rất hay về vấn đề
đẳng cấu đồ thị, đặc biệt là làm giảm thời gian tính toán bằng cách tính trước cây quyết
định ở bước tiền xử lý. Trong quá trình tính toán, tác giả nêu lên những phương pháp để
có thể giảm thiểu độ phức tạp của chương trình một cách cần thiết. Vì thế nếu đi sâu tìm
hiểu ta có thể áp dụng cách tiếp cận này cho một số bài toán thực tế. Bên cạnh đó, tác
giả cũng chỉ cho chúng ta thấy một số hạn chế nhất định của phương pháp này.______46
Do hạn chế về thời gian và ngôn ngữ nên bài dịch này sẽ không tránh khỏi sai sót, em
mong được sự góp ý của thầy. Ngoài bài dịch này ra, em có minh họa cho bài báo này
bằng một chương trình đơn giản để nhận dạng đồ thị. Chương trình được viết bằng ngôn
ngữ C++ (Visual Studio 2010). Thực hiện chương trình bằng cách nhập vào 2 tập tin
văn bản (theo dạng ma trận).______________________________________________46
TÀI LIỆU THAM KHẢO (CỦA BÀI BÁO)__________________________________47
Trang 1
LỜI NÓI ĐẦU
Môn Cơ sở dữ liệu (Nâng cao) là một môn rất hay, khó và cần thiết cho
sinh viên ngành tin học. Và càng hay hơn nữa khi em được thầy Đỗ Phúc phụ
trách môn học này. Khi học với thầy em nhận thấy rằng: thầy có kiến thức rất sâu
rộng ở nhiều lĩnh vực nên luôn tạo cho bài giảng của mình một cách rất sinh
động, tự nhiên. Thầy dẫn dắt chúng em đi sâu vào bài học bằng những kiến thức,
những mẩu chuyện, những ví dụ rất quen thuộc và cách thầy đan xen chúng vào
nhau thật là khéo léo.
Qua môn học này ở chương trình cao học, em nhận ra rằng trên cơ sở dữ
liệu truyền thống ta có rất nhiều cách thức để tạo, biến đổi, . . . nó có hiệu quả
hơn với nhu cầu thực tế sử dụng mà trước đây em chưa biết được.

thị con đẳng cấu. Phương pháp mới được thiết kế dựa trên 2 đồ thị. Một đồ thị
mẫu sẵn có (model graphs) và một đồ thị đầu vào (input graphs). Ta sẽ tìm một
đồ thị con trong đồ thị ban đầu mà đẳng cấu với đồ thị đưa vào. Ý tưởng của
phương pháp này là trước tiên ta sẽ tạo ra một cây quyết định (decision tree) trên
đồ thị mẫu. Khi thực thi, đồ thị đầu vào sẽ được phân loại bởi cây quyết định và
cho biết có tồn tại một đồ thị con đẳng cấu với đồ thị đầu vào hay không.
Nếu chúng ta bỏ qua thời gian cần thiết cho quá trình tiền xử lý (tạo ra cây
quyết định ban đầu), thì bài toán sẽ có độ phức tạp là bậc 2 của số đỉnh đồ thị
đầu vào. Hơn nữa, thuật toán cũng độc lập với đồ thị mẫu và số cạnh của nó.
Tuy nhiên, cây quyết định được xây dựng trong bước tiền xử lý có thể phát
triển theo cấp số nhân với số đỉnh của đồ thị mẫu. Vì vậy, chúng tôi xin trình
bày một thuật toán nhằm mục đích giảm độ phức tạp của cây quyết định. Việc
ứng dụng thuật toán trong việc nhận dạng đồ thị được trình bày tóm tắt như sau:
Trang 4
1. Giới thiệu
Đẳng cấu đồ thị và đồ thị con là những khái niệm đã được dùng trong nhiều
ứng dụng khác nhau. Giải pháp so sánh sự khác nhau giữa các đồ thị là động lực
thúc đẩy nhiều nhà nghiên cứu trong suốt hai mươi năm qua. Một số thuật
toán trước đây đề xuất độ phức tạp xấu nhất theo cấp số nhân và được biết
dưới dạng các bài toán NP-complete. Trong phần sau đây, chúng tôi sẽ cung
cấp một cách tổng quan thuật toán về đẳng cấu đồ thị và đồ thị con. Trong
quá khứ có hai cách tiếp cận cơ bản về vấn đề đẳng cấu đồ thị. Cách thứ nhất
được dựa trên khái niệm về lý thuyết nhóm và nghiên cứu của nhóm hoán vị.
Cách này đã được chỉ ra rằng tồn tại một giới hạn vừa phải của một cấp số
nhân đối với các vấn đề đẳng cấu đồ thị nói chung. Hơn nữa, bằng cách áp
đặt hạn chế nhất định trên các thuộc tính của đồ thị, ta có thể thấy được các
thuật toán có độ phức tạp đa thức.
Ví dụ: Luks và Hoffman mô tả một phương pháp giới hạn đa thức cho
việc tìm đẳng cấu đồ thị bằng các liên kết hóa trị. Đối với trường hợp đặc
biệt, đẳng cấu đồ thị hóa trị ba, thuật toán có độ phức tạp là O(n

và độ phức tạp tính toán của nó là O(n
4
), với n là số đỉnh của đồ thị. Một cách
tiếp cận khác được trình bày trong [Par93], bằng cách tính toán cấu trúc chỉ
mục mà nó được tổ chức như một một mạng phân cấp tương tự như việc so
khớp đồ thị mạng căn bản được mô tả trong [MB95b]. Vấn đề được quan tâm
nhất hiện này là phương pháp lập chỉ mục được đề xuất trong [Ike87, GB89,
Spi93]. Thay vì sử dụng một cơ chế lập chỉ mục như là một bước tiền xử lý
để phát hiện ra đẳng cấu đồ thị hoặc đồ thị con, cơ sở dữ liệu của đồ thị được
chuyển đổi thành một cây quyết định. Cây quyết định sau đó được sử dụng
trực tiếp dùng để chỉ mục và so khớp đồ thị mẫu với đồ thị đầu vào. Tuy nhiên,
tất cả các phương pháp tiếp cận bằng cây quyết định đã được trình bày cho
đến nay được ứng dụng mạnh trong việc nhận dạng các đối tượng 3D chứ chưa
được sử dụng trong vấn đề đẳng cấu đồ thị nói chung.
Trong bài báo này, chúng tôi đề xuất một phương pháp mới phát hiện
đẳng cấu đồ thị và đồ thị con. Nó có hai tính năng quan trọng. Đầu tiên, thời
gian thực thi của phương pháp này chỉ là bậc hai số đỉnh của đồ thị mẫu nếu
chúng ta bỏ qua thời gian cần thiết cho bước tiền xử lý. Thứ hai, thời gian là độc
Trang 6
lập với số lượng đồ thị trong cơ sở dữ liệu. Phương pháp mới dựa trên ý tưởng
sau đây. Chúng tôi tạo ra một tập của tất cả các hoán vị của ma trận kề của đồ thị
mẫu và tổ chức này tập hợp trong cây quyết định. Các đồ thị mẫu có thể kết hợp
với nhau trong cùng một cây quyết định. Cây quyết định được xây dựng trước từ
đồ thị mẫu. Khi thực thi, nó được sử dụng để xác định nếu có một đẳng cấu đồ
thị con từ một đồ thị đầu vào với một trong những đồ thị mẫu. Ưu điểm chính
của phương pháp này là nó đảm bảo độ phức tạp chỉ ở bậc hai thời gian. Tuy
nhiên, thời gian cho bước tiền xử lý là tạo ra cây quyết định, trong trường hợp
xấu nhất, sẽ là một cấp số nhân của các đỉnh. Tuy nhiên, chúng tôi tin rằng
phương pháp này là một đóng góp mới trong lĩnh vực phát hiện đẳng cấu đồ thị
con. Đây là một lĩnh vực ứng dụng được quan tâm đặc biệt với các đồ thị mẫu là

e
là một hàm gán nhãn các cạnh,
Thông thường, ta giả định rằng L
ν
và L
e
là tập giới hạn của nhãn tượng trưng.
Lưu ý rằng những định nghĩa trên tương ứng với trường hợp của đồ thị có hướng.
Đồ thị vô hướng sẽ có cùng một nhãn cho cạnh có hướng từ (v1, v2) và ngược
lại.
Định nghĩa: 2.2: Cho một đồ thị G = (V, E, µ,
ν
, L
ν
, L
e
), một đồ thị con của G là
có dạng: S = (V
s
, E
s
, µ
s
,
ν
s
, L
ν
, L
e

1
, v
2
, . . . , v
n
}. G cũng có thể đại diện
bởi ma trận kề M= (m
ij
), i, j = 1, . . ., n với m
ij
= µ(v
i
) và m
ij
=
ν
((v
i
,v
j
)) với i ≠ j.
Rõ ràng, các ma trận kề đại diện cho đồ thị không bị đếm lặp tại đỉnh. Tuy nhiên,
đây không phải là hạn chế thực sự khi lặp ta có thể được biểu diễn bằng cách mở
rộng tập nhãn đỉnh.
Rõ ràng, ma trận M không phải là duy nhất cho đồ thị G. Nếu M đại diện cho G,
sau đó bất kỳ hoán vị của M cũng là một đại diện hợp lệ của G.
Định nghĩa 2.3: Một ma trận cấp n × n P = (p
ij
) được gọi là một ma trận hoán vị
nếu:

với i = 1, . . ., n
Nếu đồ thị G được biểu diễn bởi ma trận kề (cấp n×n) M và P là một ma trận
hoán vị (cấp n×n), khi đó ma trận M’ (cấp n×n):
M’ = PMP
T
(1)
Với P
T
là hoán vị của P, và cũng là ma trận kề của G. Nếu p
ij
= 1 khi đỉnh thứ j
trong M trở thành đình thứ i trong M’.
Định nghĩa 2.4: Cho G
1
, G
2
là hai đồ thị và M
1
, M
2
là hai ma trận kề tương ứng.
G1 và G2 là đẳng cấu nếu tồn tại một ma trận hoán vị P sao cho
M
2
= PM
1
P
T
(2)
Chú ý rằng ma trận P có thể được hiểu như là một hàm song ánh f mà nó ánh xạ

1
= S
m,m
(PM
2
P
T
) (3)
Trang 9
Như vậy, vấn đề tìm một đồ thị con G2 đẳng cấu với G1 là tương đương với việc
tìm ma trận hoán vị P thỏa biểu thức (3). Lưu ý rằng S
m,m
(PM
2
P
T
) =
S
m,n
(P)M
2
(S
m,n
(P))
T
.
3. Tóm tắt thuật toán Ullman.
Để so sánh, chúng ta xem phương pháp của Ullman trong [Ull76]. Phương
pháp này có thể được áp dụng cho cả hai: tìm đẳng cấu đồ thị và đồ thị con.
Phương pháp này được dựa trên kỹ thuật quay lui và một số thủ tục cải tiến.

1
= S
m,m
(PM
1
P
T
). Lưu ý rằng S
i,n
(P) là một ma trận hoán vị (i×n) đại
diện cho một mảnh dò tìm từ đỉnh đầu tiên thứ i của G vào một số đỉnh trên
G
1
. Nếu S
i,i
(M
I
) = S
i,n
(P)M(S
i,n
(P))
T
thì rõ ràng S
i,n
(P) đại diện cho một đẳng cấu
đồ thị từ đồ thị con G
1
với một số đồ thị trong G gồm n đỉnh.
Thuật toán của Ullman được dựa trên ý tưởng tìm tất cả các đồ thị con

= (V
I
, E
I
, µ
I
,
ν
I
, L
v
, L
e
))
1. Cho P = (p
ij
) là một ma trận hoán vị (n×n), n = |V|, m = |V
I
| và M, M
I
là
các ma trận kề của G và G
I
.
2. Gọi Backtrack (M, M
I
,P,1)
3. Procedure Backtrack (M ma trận kề, ma trận kề M
I
, ma trận hoán vị P,

I
= S
m,n
(P)M(S
m,n
(P))
T
(hoặc M
I
= S
m,m
(PMP
T
)). Hơn nữa, nếu G
I
và G có kích thước bằng nhau,
nghĩa là m = n,
thuật toán tìm tất cả đồ thị đẳng cấu giữa G
I
và G thì kết của các ma trận hoán
vị P thỏa M
I
= PMP
T
. Trong các thí nghiệm thực tế trình bày ở phần 8, chúng
ta thực hiện các tiến trình quay lui cùng với các bước cải tiến lại được trình
bày trong [Ull76]. Thủ tục cải tiến được dựa trên ý tưởng là kiểm tra trước
các giá trị P
ki
= 1 ở bước (3.bi) là phù hợp cục bộ với ít nhất một p

, L
v
, L
e
) là một đồ thị mẫu và ma trận kề tương ứng M
(n×n). Gọi A(G) là tập của tất cả các hoán vị ma trận kề của G,
A(G) = |M
P
| M
P
= PMP
T
trong đó P là ma trận hoán vị (n×n) (4)
Tổng số hoán vị của ma trận kề là |A(G)| = n! như vậy sẽ có n! ma trận hoán vị
cấp n. Một đồ thị mẫu G với ma trận kề M (n×n) và đồ thị đầu vào G
I
có ma trận
kề M
I
(m×m) với m ≤ n, kiểm tra xem có tồn tại một ma trận M
P
∈ A(G) như vậy
M
I
= S
m,m
(M
P
). Nếu ma trận M
P

trên mỗi mức của cây quyết định là độc lập với kích thước của ma trận kề được
bố trí trên cây quyết định. Với mục đích này, ta chọn ký hiệu mới cho một ma
trận kề (n×n). M = (m
ij
). Chúng ta nói rằng ma trận gồm một mảng các phần tử a
i
,
mỗi a
i
là một vector có dạng:
a
i
= (m
1i
, m
2i
, , m
ii
, m
i(i-1)
, …, m
i1
).
Ma trận M có thể được biểu diễn như sau:
M = (a
1
, a
2
, …, a
n

P
đã được phân loại đến
đỉnh thứ k, P mô tả một đẳng cấu đồ thị con cho các đồ thị con với ma trận kề
S
k,k
(M
P
) vào G. Khi thực thi, P sẽ mô tả một đẳng cấu đồ thị con cho bất kỳ đồ thị
đầu vào được phân loại tới nút thứ N. Cuối cùng, ở mức dưới cùng của cây quyết
định có các nút lá. Mỗi nút lá đại diện cho một ma trận M
P
∈ A(G). Số lượng của
những ma trận hoán vị trong mỗi nút lá là bằng số tự đẳng cấu của G. (tự đẳng
Trang 14
cấu là một đẳng cấu của một đồ thị cho chính nó). Trong Hình 3 là đồ thị g1 và
cây quyết định của g1. Các nút của cây quyết định được biểu thị bằng các vòng
tròn tô mờ. Mỗi nhánh liên kết giữa các nút thông qua giá trị của hàng và cột
tương ứng. Ở phía trên của hình 3, liệt kê các hoán vị ma trận kề (A(g
1
)) của g
1
.
Dễ dàng để thấy rằng số lượng các tự đẳng cấu của g
1
là một. Vì vậy, mỗi nút lá
trong cây quyết định đại diện chính xác cho một ma trận kề. Một yêu cầu quan
trọng cho cây quyết định là các phân loại trên từng cấp độ phải được tính toán
một cách dễ dàng. Do đó, nếu một ma trận M
P
được phân loại dựa theo dòng và

2
, …, GL, với ma trận kề tương ứng là A(G
1
), A(G
2
), …, A(G
L
) có
thể được phân loại và biểu thị bởi cùng một quyết định cây. Trong Hình 5 cây
quyết định biểu diễn cho đồ thị g
1
ở hình 3 và đồ thị g
2
. Để phân loại các ma trận
kề A(g2) (được đưa ra ở trên cùng của Hình 5) chỉ có hai nút được thêm vào cây
quyết định của đồ thị g
1
. G
2
có ba phần cùng đẳng cấu tại nút 13 và nút 15 được
biểu thị trong Hình 5.
Trang 15
Khi thực thi, cây quyết định sử dụng trực tiếp các ma trận kề M
I
(đã được phân
loại) của một đồ thị đầu vào G
I
. Ma trận M
I
được phân loại ở cấp thứ 1 dựa vào

Cây quyết định được mô tả vừa rồi không cần thiết phải lớn. Sau đây chúng tôi
giới thiệu một cách làm cho nó nhỏ gọn hơn bằng cách quan sát rằng ở mức k
trong cây quyết định biểu diễn tất cả các đồ thị con có k đỉnh, k = 1, …, n. Chú ý
rằng mỗi đồ thị con S được biểu diễn bởi k!/α lần, với α là số không tự đẳng cấu
của S. Rõ ràng, tất cả các đại diện tương đương với nhau, và thông tin mà ta chứa
phần lớn là dư thừa. Bây giờ chúng ta biết được cách làm thế nào để loại bỏ sự
dư thừa này. Kết quả là ta xây dựng một cây nhỏ gọn hơn cây quyết định ban
đầu.
Cho N
1
và N
2
là các nút của cây quyết định và cả hai biểu diễn cho đồ thị
con S giống với đồ thị mẫu G, và S có ma trận kề M
S
. Cho M
1
và M
2
là các ma
trận kề biểu diễn bởi N
1
và N
2
, và P
1
, P
2
là ma trận hoán vị tương ứng, như vậy
P

T
(6)
Thế R = P
1
P
2
T
vào phương trình (5) và cũng thay thế M
2
bằng P
2
M
S
P
2
T
kết quả là
M
1
= P
1
P
2
T
(P
2
M
S
P
2

2
đến
N
1
. Với mục đích này, chúng tôi giới thiệu nhánh kết hợp (redirecting branch)
trong cây quyết định từ nhánh nút N
2
qua N
1
. Liên kết với nhánh kết hợp là các
ma trận hoán vị R. Nói chung, với một đồ thị con S ⊂ G, chúng ta chọn tập từ nút
Trang 17
của cây quyết định mà nó đại diện cho S là một nút T tùy ý và được chèn các
nhánh kết hợp từ tất cả các nút khác đến T.
MERGE_TREE(NODE Root, Graph S)
1. Cho S được biểu diễn bởi ma trận kề M(k×k) của nó.
Tạo ra tất cả các ma trận hoán vị P có kích thước là k và tập A(S) là tập mà
trận kề hoán vị của S.
2. Với mỗi M
P
= (a
1
, …,a
k
) ∈ A(S) thì:
(a) N = Root.
(b) Với i = 1 đến k thì:
i. Nếu có một nút Ns kế nút N mà a
k
= a

hoán vị tương ứng P’, như thế:
M’ = P’MP’
T
. Khi đó, kết hợp các ma trận hoán vị P
1
P’
T
đến các nhánh kết
hợp từ N đến T (xem phương trình 6).
Hình 7: Thuật toán Merge_tree.
Do đó, chỉ có một trong những nút của S sẽ được dùng cho các ma trận đã
được phân loại của đồ thị G. Bây giờ chúng ta mô tả một thủ tục để biên dịch
một cây quyết định từ một đồ thị mẫu. Ý tưởng cơ bản của chương trình biên
dịch là tạo ra một cây quyết định gồm tất cả các đồ thị con của đồ thị mẫu.
Trong thủ tục, chúng ta dần dần tăng kích thước của đồ thị con mà được
tích hợp trong cây quyết định. Như được thảo luận ở trên, với mỗi đồ thị con
chỉ cần có một nút trong cây quyết định được sử dụng để phân loại. Khi biên
dịch thủ tục compile_tree, chúng ta bắt đầu tạo ra một nút gốc cho cây quyết
Trang 18
định, với điều kiện là cây quyết định đang rỗng. Tiếp theo, ta tạo đồ thị con
của G bắt đầu với đồ thị con có kích thước là một và kết thúc là chính nó.
Với mỗi đồ thị con S
k
với k biểu thị số đỉnh, thủ tục merge_tree được gọi thực
hiện.
Trong bước đầu tiên thủ tục merge_tree, tập A(S) của tất cả các hoán vị ma
trận kề được tạo ra. Các ma trận này sau đó được phân loại theo cây quyết
định đã có càng nhiều càng tốt. Lưu ý rằng cây quyết định có thể vào thời
điểm này đã kết hợp các đồ thị mẫu hoặc các đồ thị con của đồ thị mẫu khác
nhau.

01
10
.
Khi áp dụng cho ma trận con 2×2 S
2,2
(A), S
2,2
(B) và S
2,2
(D) của g
1
, các ma trận
kết quả là S
2,2
(C), S
2,2
(E) và S
2,2
(F). Đối với đồ thị g
2
, nhánh kết hợp biến đổi ma
trận S
2,2
(A’), S
2,2
(D’) và S
2,2
(E’) thành các ma trận S
2,2
(C’), S

(M) bằng cách phân loại M
I
theo phần tử của dòng và cột. Thuật toán bắt đầu tại nút gốc của cây quyết định
và trước tiên phân loại M
I
theo phần tử đầu tiên của nó (a
1
). Nếu bước này thành
Trang 20
công, phân loại được tiếp tục vào cấp độ tiếp theo. Nói chung, nếu tiến trình
đang ở mức độ k và N là nút hiện tại của cây quyết định, khi đó a
k
sẽ đại diện cho
N. Ta làm được điều này bằng cách tìm phần tử a
k
trong từ điển. Nếu có một
phần tử a
kN
trong từ điển hoàn toàn phù hợp với a
k
, tiến trình sẽ thông qua nhánh
N này để đến nhánh kề sau với nó và có nút là Ns, nút này được thể biện bởi
phần tử a
kN
. Nếu không có phần tử nào như vậy được tìm thấy trong từ điển thì
M
I
không có thể được phân loại bởi cây quyết định, như vậy thì G
I
không là đẳng

- Không có đẳng cấu đồ thị con từ đồ thị đầu vào với bất kỳ đồ
thị mẫu nào.
Hoặc
- Trong bước (3) khi phần tử cuối cùng của M
I
đã được xử lý và
một số nút N đã được duyệt.
Trong trường hợp sau, ma trận M
I
chính là tất cả các ma trận M
i
của G
i
biểu diễn
tại nút N. Nếu N không phải là một nút lá thì tập các ma trận hoán vị được lưu
trữ tại N đại diện cho tất cả các đẳng cấu đồ thị con từ G
I
vào G
i
. Mặt khác, N là
một nút lá, G
I
và G
i
có kích thước bằng nhau, và tập các ma trận hoán vị tại nút N
biểu thị cho tất cả các đồ thị đẳng cấu giữa G
I
và G
i
.

k
.
(b) Nếu không có phần tử nào được tìm thấy trong từ điển, đồ thị G
không đẳng cấu với bất kỳ đồ thị con nào của đồ thị mẫu. Thoát
bởi tìm không thấy đẳng cấu đồ thị.
(c) Nếu một phần tử a
kN
= a
k
được tìm thấy trong từ điển, khi đó ta
theo nhánh được đại diện bởi phần tử a
kN
để đến được nút N
s
.
(d) Nếu có một nhánh kết hợp của N
s
một số nút N’ khi gán M
I
=
R’M
I
R’
T
, với R’ là ma trận hoán vị cấp m được mở rộng. Đặt N =
N’.
Ngược lại N = Ns.
3. Đối với mỗi ma trận M
P
của G

i
P
T
.
Hình 9: Thuật toán decision_tree.
7. Phân tích độ phức tạp.
Phân tích độ phức tạp tính toán được dựa vào các yếu tố sau:
N = số đồ thị mẫu trong cơ sở dữ liệu,
M = số lượng tối đa của các đỉnh trong một đồ thị mẫu,
I = Số đỉnh của đồ thị đầu vào,
l
v
= số lượng nhãn đỉnh,
l
e
= số lượng nhãn cạnh.
7.1 Tính toán phức tạp của thuật toán thông thường
Để so sánh, đầu tiên chúng ta phân tích độ phức tạp không gian và thời gian
theo cách cũ, phương pháp đẳng cấu đồ thị con trên cơ sở quay lui. Trường
hợp tốt nhất của thuật toán này:
(Độ phức tạp về thời gian trong trường hợp tốt nhất)
O(NIM) (7)
(Độ phức tạp về không gian trong trường hợp tốt nhất)
O(M
2
I) (8)
Trường hợp xấu nhất nhất của thuật toán này:
(Độ phức tạp về thời gian trong trường hợp tốt nhất)
O(I
M













k
M
O
. Mỗi nút này có thể là nút cha của rất nhiều nút kế thừa. Bất kỳ
phần tử a
k +1
mà là liên quan đến một chi nhánh bắt nguồn từ một nút ở mức
k + 1 bao gồm các mục nhãn 2k cạnh và một trong những mục nhãn đỉnh.
Do đó, có ít nhất O(l
e
2k
l
v
) phần tử khác nhau, mỗi phần tử được đại diện bởi
một nút khác nhau trong cây quyết định. Tổng số nút ở mức k + 2 (sau mức k
+ 1) là



M
k
v
llOl
k
M
lO
22
1
0
1)( +=
















∑
−
=

N
là một trong các nút kế thừa của nút hiện tại, phải phù hợp hoàn toàn
với a
k+1
.
Vì vậy, theo lý thuyết sự phức tạp thuật toán đẳng cấu đồ thị con mới được
giới hạn bởi:
(Độ phức tạp thời gian trong trường hợp tốt nhất và xấu nhất của cây quyết
định theo chiều rộng)
O(M(2Ml
e
+ l
v
) + M
2
) = O (M
2
l
e
+ Ml
v
) (14)
Chú ý rằng độ phức tạp của thuật toán mới đối với phát hiện đẳng cấu đồ thị
con cũng áp dụng để phát hiện đẳng cấu đồ thị. Một lần nữa, trường hợp đặc
biệt cho đồ thị không nhãn, vô hướng, thời gian chạy được giới hạn bởi:
O(M
2
) (15)
Điều quan trọng là cần lưu ý rằng cả hai trường hợp đặc biệt và tổng quát
của đồ thị không có nhãn, độ phức tạp tính toán của các thuật toán mới