CHƯƠNG 1: TỔNG QUAN VỀ CLIQUE

3

1.1.

3

Lịch sử và ứng dụng của bài toán clique

1.2. Giới thiệu về CLIQUE của đồ thị

3

CHƯƠNG 2: BÀI TỐN MAXIMAL CLIQUE

6

2.1. Phát biểu bài tốn

6

2.2. Phân tích vấn đề

6

2.3. Xây dựng giải pháp cho bài tốn

6

2.4. Chứng minh tính đúng đắn của thuật tốn

8

2.5. Đánh giá độ phức tạp của thuật toán

10

2.6. Đánh giá thực nghiệm

10

CHƯƠNG 3: GIỚI THIỆU MỘT THUẬT TOÁN POLYNOMIAL – TIME ÁP DỤNG
CHO BÀI TỐN TÌM CLIQUE CỰC ĐẠI
11
3.1. Mở rộng bài toán Maximal Clique phù hợp với thực tế

11

3.2. Giới thiệu hướng tiếp cận thuật giải

11

3.3. Các thủ tục sử dụng trong polynomial-time algorithm

12

3.3.1. Các thủ tục

12


3.3.2. Thuật toán

12

3.3.3.Chứng minh tính đúng đắn của thuật tốn

12

3.4. Phân tích độ phức tạp

14

TÀI LIỆU THAM KHẢO

16

2


CHƯƠNG 1: TỔNG QUAN VỀ CLIQUE
1.1.

Lịch sử và ứng dụng của bài toán clique
Nghiên cứu về đồ thị con đầy đủ trong tốn học có trước thuật ngữ “clique”. Ví dụ,
các đồ thị con đầy đủ xuất hiện sớm trong các tài liệu toán học trong lý thuyết đồ thị của lý
thuyết Ramsey bởi Erdoc & Szekeres (1935). Nhưng thuật ngữ "clique" và vấn đề về danh
sách các thuật toán clique đều đến từ khoa học xã hội, nơi các đồ thị con đầy đủ được sử
dụng để mơ hình các nhóm xã hội, những nhóm người biết nhau. Luce và Perry (1949) đã sử
dụng các đồ thị để mơ hình hóa các mạng xã hội và điều chỉnh thuật ngữ khoa học xã hội

theo lý thuyết đồ thị. Họ là những người đầu tiên gọi các đồ thị con đầy đủ "cliques". Thuật
toán đầu tiên để giải quyết vấn đề clique là của Harary và Ross (1957) ,được thúc đẩy bởi
ứng dụng xã hội học. Các nhà nghiên cứu khoa học xã hội cũng đã xác định các loại khác
nhau của cliques và cliques tối đa trong mạng xã hội. Có thể tìm thấy nhiều khái niệm tổng
quát của các cliques bằng cách xây dựng một đồ thị vơ hướng có các cạnh đại diện cho các
cặp đối tượng có liên quan từ mạng xã hội và sau đó áp dụng thuật tốn cho bài tốn clique
vào đồ thị này.
Kể từ khi cơng trình của Harary và Ross, nhiều người khác đã nghĩ ra các thuật toán
cho các phiên bản khác nhau của vấn đề clique. Vào những năm 1970, các nhà nghiên cứu
bắt đầu nghiên cứu các thuật tốn này từ quan điểm phân tích trường hợp xấu nhất . Ví
dụ, Tarjan & Trojanowski (1977) , một cơng trình ban đầu về độ phức tạp trong thời gian xấu
nhất của vấn đề clique tối đa. Cũng trong thập niên 1970, bắt đầu với công việc của Cook
(1971) và Karp (1972) , các nhà nghiên cứu bắt đầu sử dụng lý huyết NP-completeness và
các kết quả liên quan để cung cấp một giải thích tốn học cho vấn đề clique. Trong những
năm 1990, một loạt các bài báo mang tính đột phá bắt đầu với Feige et al. (1991) và được
xuất bản trên tờ New York Times đã chỉ ra rằng (giả sử P ≠ NP ) nó thậm chí khơng thể đưa ra
vấn đề chính xác và hiệu quả.
1.2. Giới thiệu về CLIQUE của đồ thị
Trong lý thuyết đồ thị, một Clique trong đồ thị vô hướng G là tập các đỉnh V (V là tập
con của tập các đỉnh của G) thỏa mãn điều kiện: với mỗi cặp đỉnh thuộc V luôn tồn tại một
cạnh của G nối chúng. Do vậy một đồ thị con được tạo ra từ V sẽ là một đồ thị đầy đủ. Kích
thước của một clique là số đỉnh của nó.
Định nghĩa 1: Đồ thị đầy đủ n đỉnh, kí hiệu là Kn, là là đồ thị đơn vơ hướng mà giữa
hai đỉnh bất kỳ nó ln có cạnh nối.
Đồ thị Kn có tất cả n(n-1)/2 cạnh. Nó là đồ thị đơn có nhiều cạnh nhất, đồng thời là đồ
thị chính quy bậc n-1.
Ví dụ 1: Một đồ thị đầy đủ K7 (7 đỉnh). Nếu đây là một đồ thị con thì tập đỉnh của nó
sẽ tạo nên một clique kích thước 7002E

3



Hình 1.1: Đồ thị đầy đủ K7
Bài tốn xác định có tồn tại hay khơng một clique với một kích thước cho trước trong
một đồ thị (Bài toán clique) là một bài toán NP-Complete.
Đối với một clique là một tập độc lập, với nghĩa rằng mỗi clique tương ứng với một
tập độc lập của đồ thị nghịch đảo.
Thuật ngữ này xuất phát từ ý tưởng rằng giả sử mỗi đỉnh biểu diễn một người và mỗi
cạnh biểu diễn mối quan hệ quen biết, thì hai người bất kì đều quen lẫn nhau, do vậy tạo nên
một clique.
Định nghĩa 2: Clique cực đại (maximal clique) của G là clique không thuộc bất cứ
một clique nào khác rộng hơn nó, nói cách khác là không thể thêm bất cứ đỉnh nào vào một
clique cực đại để tạo ra clique có số đỉnh lớn hơn.
Định nghĩa 3: Clique lớn nhất (maximum clique) của G là clique có số đỉnh lớn nhất
của G. Một clique lớn nhất đồng thời là một clique cực đại, nhưng điều ngược lại chưa chắc
đã đúng.
Định nghĩa 4: Chỉ số clique (clique number) của đồ thị G là số đỉnh của clique lớn
nhất trong G. Chỉ số clique của đồ thị G được ký hiệu là ω(G).
Định nghĩa 5: Phần bù của đồ thị G (kí hiệu là 𝐺) có tập đỉnh giống với tập đỉnh của
G và tập cạnh không nằm trong tập cạnh của G.
Định nghĩa 6: Đồ thị đầy đủ (Complete Graph): với mỗi cặp đỉnh được nối với nhau
bằng một cạnh.

4


Hình 1.2: Đồ thị G, phần bù đồ thị 𝐺, đồ thị đầy đủ, Clique

5



CHƯƠNG 2: BÀI TỐN MAXIMAL CLIQUE
2.1. Phát biểu bài tốn
Cho đồ thị G = (V, E) và số k∈N* thỏa mãn |k|≤|V|. Tồn tại hay không một tập con
V’ của V sao cho |V’|≥k mà mọi cặp đỉnh trong V’ đều được nối bởi một cạnh trong E.
Ví dụ 2.1:Cho đồ thị Octahedron với n = 6 đỉnh. Tìm Clique cực đại với kích thước k
= 3.

Hình 2.1: Đồ thị Octahedron với clique cực đại ( n=6, k=3)
2.2. Phân tích vấn đề
❖ Mô tả giả thiết của vấn đề
- Đầu vào: Đồ thị G là đơn đồ thị vô hướng, liên thông
- Đầu ra: Clique cực đại của đồ thị G;
❖ Mục tiêu của vấn đề: Tìm ra Clique cực đại của đồ thị;
❖ Các điều kiện hay ràng buộc liên quan:
- Phải là đơn đồ thị vô hướng, liên thông;
- Số đỉnh (>=2) và số cạnh (>=1) của đồ thị là hữu hạn;
2.3. Xây dựng giải pháp cho bài tốn
Bài tốn này có một số giải pháp như:
- Sử dụng các thuật toán Non polynomial-time algorithm.
- Sử dụng các thuật toán polynomial-time algorithm.
- Hai thuật toán hiệu quả với việc thực hiện các bài toán NP-Complete: quay lui và
nhánh – cận.
Ở đây, em sẽ trình bày giải thuật Bron Kerbosch cho bài tốn tìm Clique cực đại.
Thuật tốn này được thiết kế và công bố vào năm 1973 bởi hai nhà khoa hoc người Hà Lan là
Joep Kerbosch và Coenradd Bron. Nó được biết như là một thuật tốn hiệu quả nhất cho việc
sử dụng đệ qui quay lui để tìm các Clique. Thuật tốn như sau:
● Khơng có Pivoting Strategy
6



➢
Dạng cơ bản của thuật toán Bron – Kerbosch là một thuật tốn đệ quy lùi để tìm
kiếm tất cả các clique tối đa trong một đồ thị G. Nói chung, với ba bộ R , P và X , nó tìm thấy
các clique tối đa bao gồm tất cả các đỉnh trong R , một số đỉnh trong P , và khơng có đỉnh
nào trong X. Trong mỗi lời gọi đến thuật toán, P và X là các tập hợp rời nhau mà hợp của nó
bao gồm các đỉnh tạo thành các clique khi thêm vào R. Nói cách khác, P ∪ X là tập các đỉnh
được nối với mọi phần tử của R. Khi P và X đều trống rỗng, khơng có thêm phần tử nào có
thể được thêm vào R , vì vậy R là một clique tối đa và kết quả của thuật toán là R.
➢
Phép đệ quy được khởi tạo bằng cách thiết lập R và X là tập rỗng và P là tập
đỉnh của đồ thị. Trong mỗi lời gọi đệ quy, thuật toán xem xét lần lượt các đỉnh trong P; nếu
khơng có đỉnh nào thì nó báo cáo R là một clique tối đa (nếu X trống) hoặc ngược lại. Đối với
mỗi đỉnh v được chọn từ P , nó thực hiện một lời gọi đệ quy trong đó v được thêm vào R và
trong đó P và X bị giới hạn đối với tập lân cận N (v) của v , tìm và xuất ra tất cả các phần mở
rộng clique của R chứa v . Sau đó, nó di chuyển v từ P sang X để loại trừ nó khỏi việc xem
xét trong các cliques trong tương lai và tiếp tục với đỉnh tiếp theo trong P.
Trong mã giả, thuật toán thực hiện các bước sau:
BronKerbosch1(R, P, X):
if P and X are both empty:
report R as a maximal clique
for each vertex v in P:
BronKerbosch1(R ⋃ {v}, P ⋂N(v), X ⋂ N(v))
P := P \ {v}
X := X ⋃ {v}
●
Có Pivoting Strategy:
Dạng cơ bản của thuật tốn, được mơ tả ở trên, không hiệu quả trong trường hợp các
đồ thị có nhiều clique khơng cực đại: nó tạo ra một lời gọi đệ quy cho mọi clique, cực đại hay
khơng. Để tiết kiệm thời gian và cho phép thuật tốn quay lại nhanh hơn trong các nhánh tìm

kiếm khơng chứa các clique cực đại, Bron và Kerbosch đã giới thiệu một biến thể của thuật
toán liên quan đến "pivot vertex" u , được chọn từ P (hoặc đơn giản hơn, như các nhà nghiên
cứu sau này nhận ra, từ P ⋃ X ). Bất kỳ clique cực đại phải bao gồm một trong hai: hoặc u
hoặc một trong những đỉnh khơng phải lân cận của nó, nếu khơng thì clique có thể được tăng
cường bằng cách thêm u vào nó. Do đó, chỉ có u và những đỉnh khơng phải lân cận của nó
cần phải được kiểm tra như là sự lựa chọn cho v đỉnh được thêm vào R trong mỗi lần gọi đệ
quy đến thuật toán. 
Trong mã giả thuật toán thực hiện như sau:
BronKerbosch2(R,P,X):
if P and X are both empty:
report R as a maximal clique
choose a pivot vertex u in P ⋃ X
for each vertex v in P \ N(u):
BronKerbosch2(R ⋃ {v}, P ⋂N(v), X ⋂ N(v))
7


P := P \ {v}
X := X ⋃ {v}
2.4. Chứng minh tính đúng đắn của thuật tốn
Cho đồ thị như hình 2.2, hãy tìm các maximal clique của đồ thị?

Hình 2.2. Đồ thị 7 đỉnh

Trường hợp 1: Khơng có Pivoting Strategy
Thuật tốn thực hiện như sau (có pivot):
● R = X = ∅, P = (1,2,3,4,5,6)
● Mỗi v trong P = (1,2,3,4,5,6,7)
● Tìm các giá trị Rnew, Pnew và Xnew
● Pnew = P ∩ N(v); Rnew = R ∪ v; Xnew = X ∩ N(v)

● Rnew = 1; Pnew = (2,3,4); Xnew = ∅
Tiếp tục thực hiện gọi đệ qui nhiều lần, cụ thể như sau:
BronKerbosch(∅,(1,2,3,4,5,6,7),∅)
BronKerbosch((1),(2,3,4),∅)
BronKerbosch((1,2),(3,4),∅)
BronKerbosch((1,2,3),(4),∅)
BronKerbosch((1,2,3,4), ∅ ,∅) Maximal Clique: 1 2 3 4
BronKerbosch((1,2,4), ∅ ,(3))
BronKerbosch((1,3),(4),(2))
BronKerbosch((1,3,4),∅,(2))
BronKerbosch((1,4),(4),(2,3)
BronKerbosch((2),(3,4,5),(1))
8


BronKerbosch((2,3),(4),(1))
BronKerbosch((2,3,4),∅,(1))
BronKerbosch((2,4),(5),(1,3))
BronKerbosch((2,4,5), ∅ , ∅ ) Maximal Clique: 2 4 5
BronKerbosch((2,5), ∅ ,(4))
BronKerbosch((3),(4),(1,2))
BronKerbosch((3,4),∅,(1,2))
BronKerbosch((4),(5,6),(1,2,3))
BronKerbosch((4,5),∅,(2))
BronKerbosch((4,6),∅, ∅ ) Maximal Clique: 4 6
BronKerbosch((5),(7),(2,4))
BronKerbosch((5,7), ∅, ∅ ) Maximal Clique: 5 7
BronKerbosch((6),∅,(4))
BronKerbosch((7),∅,(7))
Trường hợp 2: Có Pivoting Strategy:

Trong đồ thị trên hình 2.2, thuật tốn ban đầu được gọi là R  = Ø, P  = {1,2,3,4,5,6,7} và X  =
Ø. Đỉnh u được chọn là một đỉnh bậc cao nhất (bậc 5), để giảm các lời gọi đệ quy; giả sử
rằng u được chọn là đỉnh 4. Sau đó, có hai đỉnh cịn lại trong P  \ N ( u ): đỉnh 4 và 7.
Thuật tốn thực hiện như sau (có pivot):
● R = X = ∅, P = (1,2,3,4,5,6,7)
● Chọn phần tử pivot u là 4.
● Mọi v trong P\N(u) = (1,2,3,4,5,6,7)\(1,2,3,5,6) = (4,7)
● Tìm các giá trị Rnew, Pnew và Xnew
● Pnew = P ∩ N(v); Rnew = R ∪ v; Xnew = X ∩ N(v)
● Rnew = 4; Pnew = (1,2,3,5,6); Xnew = ∅
Tiếp tục thực hiện gọi đệ qui nhiều lần, cụ thể như sau:
BronKerbosch(∅,(1,2,3,4,5,6,7), ∅):
BronKerbosch((4),(1,2,3,5,6), ∅)
BronKerbosch((4,2),(1,3,5), ∅)
BronKerbosch((4,2,1),(3), ∅)
BronKerbosh((4,2,1,3), ∅,∅)
BronKerbosch((4,2,3), ∅,(1))
BronKerbosch((4,2,5), ∅,∅)
BronKerbosch((4,6), ∅,∅)
BronKerbosch((7),(5), ∅):
BronKerbosch((7,5), ∅,∅)

9

→Clique: (4,2,1,3)
→Clique (4,2,5)
→ Clique (4,6)
→ Clique (7,5)



2.5. Đánh giá độ phức tạp của thuật tốn
Bất kì đồ thị nào có n đỉnh thì có nhiều nhất 3n/3 các Clique cực đại và thời gian chạy
trong trường hợp xấu nhất (với một chiến lược pivot giảm thiểu số lượng các lần gọi đệ quy
được thực hiện ở mỗi bước) của thuật toán Bron–Kerbosch là O(3n/3).
2.6. Đánh giá thực nghiệm
Với thuật toán trên, nếu cho đồ thị cỡ nhỏ thì thuật tốn mang lại hiệu quả cao hơn.
Tuy nhiên, trong thực tế, vấn đề tìm Clique cực đại khơng chỉ dừng lại ở các đồ thị có kích
thước nhỏ, … Vì vậy, cần tối ưu hơn trong việc giải quyết vấn đề này.
Qua sự tìm hiểu và sưu tầm các tài liệu, em xin giới thiệu một thuật tốn có thể áp
dụng hiệu quả hơn để giải quyết vấn đề tìm Clique cực đại phù hợp với thực tiễn. Nội dung
giải pháp và thuật toán kèm theo được trình bày chi tiết ở Chương 3.

10


CHƯƠNG 3:
GIỚI THIỆU MỘT THUẬT TOÁN POLYNOMIAL – TIME ÁP DỤNG CHO
BÀI TỐN TÌM CLIQUE CỰC ĐẠI
3.1. Mở rộng bài toán Maximal Clique phù hợp với thực tế
Trong thực tế, các ứng dụng Clique của đồ thị thường với số đỉnh lớn và phức
tạp.Trong nghiên cứu này, bài toán xử lý trên các đơn đồ thị vơ hướng.Hình ảnh về đồ thị cỡ
lớn như Hình 3.1.

Hình 3.1: Đồ thị 12 đỉnh và Clique cực đại với k = 5
3.2. Giới thiệu hướng tiếp cận thuật giải
Năm 1972, Karp [9], đã giới thiệu danh sách 21 bài toán NP-complete, một trong số
đó là bài tốn tìm clique cực đại trên đồ thị. Như đã giới thiệu trong chương 2, thuật toán
Bron Kerbosch giải quyết bài tốn tìm Clique cực đại với độ phức tạp O(3n/3). Thực tế, các
bài toán ứng dụng Clique thường với số đỉnh rất lớn, khi đó bài tốn sẽ có thời gian chạy rất
lớn. Để giải quyết vấn đề này, chúng ta phải xây dựng một giải thuật mới tìm clique cực đại

với thời gian đa thức.d
Một thuật toán là một phương pháp giải quyết vấn đề phù hợp để thực thi được trên
máy tính.Việc thiết kế thuật toán thường phải đối mặt với một số phương pháp khác
nhau.Tuy nhiên, có nhiều vấn đề mà các thuật toán chỉ giải quyết được phải mất nhiều thời
gian để tính tốn các giải pháp, nhưng thực tế thì khơng cho phép điều này. Một thuật tốn có
thời gian đa thức là một thuật tốn có số lượng bước tính tốn ln được xác định bởi một
hàm đa thức theo kích thước đầu vào. Do đó, một thuật tốn có thời gian đa thức là một trong
những thuật toán hữu ích trong thực tế. Các lớp bài tốn có thời gian đa thức được kí hiệu là
P. Ý tưởng là chúng ta tìm cách đưa các bài tốn NP-complete về các bài tốn P. Thuật tốn
được thiết kế và trình bày chi tiết trong mục 3.3.

11


3.3. Các thủ tục sử dụng trong polynomial-time algorithm
3.3.1. Các thủ tục
❖ Procedure 1: Cho một đơn đồ thị G với n đỉnh và một clique Q của G.
- Nếu Q khơng có các đỉnh có khả năng kề với đỉnh khác thì xuất ra Q.
- Ngược lại, với mỗi đỉnh có khả năng kề v của Q,
+ Tìm số đỉnh có thể kề là ρ(Q∪{v}) của clique Q∪{v}.
+ vmax kí hiệu đỉnh có thể kề sao cho ρ(Q∪{vmax}) là lớn nhất và thu một clique Q∪{vmax}.
+ Lặp lại cho đến khi clique khơng cịn đỉnh nào có khả năng kề.
❖ Procedure 2: Cho một đồ thị G với n đỉnh và một clique cực đại Q của G.
- Nếu khơng có đỉnh v nằm ngồi Q và có chính xác một đỉnh w nằm trong Q và w
không là hàng xóm của v thì xuất ra Q.
- Ngược lại, tìm một đỉnh v nằm ngồi Q sao cho có chính xác một đỉnh w nằm trong Q
khơng là hàng xóm của v.
- Định nghĩa Qv,w: Đưa đỉnh v vào Q và xóa w từ Q.
- Thực hiện Procedure 1 trên Qv,w
- Xuất ta kết quả clique.

3.3.2. Thuật toán
Cho đầu vào là một đồ thị đơn G với n đỉnh được gán nhãn 1,2, …, n, tìm kiếm một
clique có kích cỡ nhỏ nhất là k. Tại mỗi giai đoạn, nếu một clique thu được có kích thước
nhỏ nhất là k thì dừng lại.
Part I: For i=1,2, …,n
● Khởi tạo clique Qi = {i};
● Thực hiện procedure 3.1 trên Qi;
● For r = 1,2, …, k
Thực hiện Procedure 2
● Kết quả là một clique cực đại Qi;
Part II: For mỗi cặp clique cực đại Qi, Qj được tìm trong Part I
● Khởi tạo clique Qi,j = Qi∩Qj
● Thực hiện Procedure 1 trên Qi,j
● For r = 1, 2, …, k
Thực hiện Procesure 2;
● Kết quả là clique cực đại Qi,j
3.3.3.Chứng minh tính đúng đắn của thuật tốn
Chúng tơi minh họa các bước của thuật tốn với một ví dụ nhỏ. Đầu vào là một phần
bù của đồ thị Frutch [10] với n = 12 cạnh như sau:
12


V = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

Hình 3.2: Phần bù của đồ thị Frutch
Bài tốn u cầu: Tìm một clique có kích thước ít nhất k = 5.
Part I cho i = 1 và i = 2 sinh ra clique Q1 và Q2 kích thước 4, chúng tơi sẽ thực hiện chi
tiết bắt đầu I = 3. Chúng tôi khởi tạo một clique như:
Q3 = {i} = {3}
Bây giờ, chúng tôi thực hiện procedure 3.1. Đây là kết quả trình bày hình thức bảng:

❖ Clique Q3 = {3} và Size(Q3) = 1.
Đỉnh có khả năng Các đỉnh có khả năng
p(Q3∪{v})
kề v của Q3
kề của Q3∪{v}
1
5, 6, 8, 9, 12
5
5
1, 7, 8, 11, 12
5
6
1, 9, 11, 12
4
7
5, 9, 11, 12
4
8
1, 5, 9, 11
4
9
1, 6, 7, 8, 11
5
11
5, 6, 7, 8, 9, 12
6
12
1, 5, 6, 7, 11
5
⇨ Maximum p(Q3∪ {v}) = 6 cho v = 11. Thêm đỉnh 11 vào Q3.

❖ Clique Q3 = {3, 11} và Size(Q3) = 2.
Đỉnh có khả năng Các đỉnh có khả
kề v của Q3
năng kề của Q3∪{v}
5
7, 8, 12
6
9, 12
7
5, 9, 12
13

p(Q3∪{v})
3
2
3


8
5, 9
2
9
6, 7, 8
3
12
5, 6, 7
3
⇨ Maximum ρ(Q3∪{v}) = 3 for v = 5. Adjoin vertex 5 to Q3.
❖ Clique Q3 = {3, 5, 11} và Size(Q3) = 3.
Đỉnh có khả năng Các đỉnh có khả p(Q3∪{v})

kề v của Q3
năng kề của Q3∪{v}
7
12
1
8
None
0
12
7
1
⇨ Maximum ρ(Q3∪{v}) = 1 for v = 7. Adjoin vertex 7 to Q3. 
❖ Clique Q3 = {3, 5, 7, 11}. Size: 4.
Đỉnh có khả năng Các đỉnh có khả p(Q3∪{v})
kề v của Q3
năng kề của Q3∪{v}
12
None
0
Maximum ρ(Q3∪{v}) = 0 for v = 12. Adjoin vertex 12 to Q3.
Chúng tôi thu được clique cực đại
Q3 = {3, 5, 7, 11, 12}
Theo kích thước yêu cầu là k = 5 và thuật toán kết thúc.

Hình 3.3: Clique cực đại
3.4. Phân tích độ phức tạp
Tơi sẽ trình bày độ phức tạp của thuật tốn thời gian đa thức, bằng cách xác định một
đa thức theo n số đỉnh của đồ thị đầu vào, đó là một giới hạn trên tổng số bước tính tốn
được thực hiện bởi các thuật toán. Lưu ý chúng ta xem xét: Kiểm tra xem một cặp đỉnh cho
14



trước được kết nối bởi các cạnh trong G, và so sánh giữa một số nguyên cho trước và một số
nguyên cho trước khác. Các thao tác này được xem là các bước tính tốn cơ bản.
❖ Mệnh đề A: Cho một đồ thị đơn G với n đỉnh và một Clique Q, Procedure 1 tốn ít
nhất n5 bước.
Chứng minh: Kiểm tra một đỉnh đặc trưng có khả năng kề với đỉnh khác hay khơng thì
tốn ít nhất là n2 bước. Mỗi clique đặc biệt, tìm số đỉnh đặc trưng p có khả năng kề với các
đỉnh khác thì tốn nhiều nhất là n3 = nn2 bước. Cho mỗi clique đặc trưng, tìm một đỉnh mà có
p là maximum thì tốn n4 = nn3 bước. Procudure 1 xác định khi nhiều nhất n đỉnh là được kết
nối, vì vậy tổng chi phí tốn nhiều nhất n5 = nn4 bước.
❖ Mệnh đề B: Cho một đồ thị đơn giản G với n đỉnh và một clique cực đại Q, Procedure
2 tốn nhiều nhất là n5 + n2 + 1 bước.
Chứng minh: Tìm một đỉnh v nằm ngồi Q có chính xác một đỉnh w nằm trong Q mà
nó khơng là hàng xóm của nhau thì tốn ít nhất n2 bước. Nếu một đỉnh v đã tìm thấy, nó tốn
một bước để trao đổi v và w. Theo mệnh đề A, nó tốn chi phí nhiều nhất n5 bước để thực hiện
Procedure 1 trên clique kết quả.Vì thế, Procedure 2 tốn nhiều nhất n2+1+n5 bước.
❖ Mệnh đề C: Cho một đồ thị đơn giản G với n đỉnh, Part I của thuật toán tốn nhiều
nhất n7+n6+n4+n2 bước.
Chứng minh: Tại mỗi lần lặp, Procedure 1 tốn nhiều nhất là n5 bước. Sau đó,
Procedure 2 được thực hiện ít nhất n lần, vì vậy, tốn chi phí nhiều nhất là n(n5+n2+1) =
n6+n3+n bước. Vì thế, tại mỗi lần lặp, có nhiều nhất n5+n6+n3+n bước thực thi. Do có n lần
lặp, Part I thực hiện nhiều nhất n(n5+n6+n3+n) = n6+n7+n4+n2bước.
❖ Mệnh đề D: Cho một đồ thị đơn giản G với n đỉnh, thuật toán tốn ít hơn
n8+2n7+n6+n5+n4+n3+n2bước để kết thúc.
Chứng minh: Có ít hơn n2 cặp clique cực đại khác nhau được tìm thấy trong Part I.
Trong Part II tốn chi phí nhỏ hơn n2(n5+n6+n3+n) = n7+n8+n5+n3. Vì vậy, tổng chi phí của
thuật tốn trong Part I và Part II là (n7+n6+n4+n2)+(n8+n7+n5+n3) = n8+2n7+n6+n5+n4+n3+n2
bước để kết thúc thuật tốn.
Vậy thuật tốn này có độ phức tạp là một đa thức bậc 8.


15


TÀI LIỆU THAM KHẢO

Tiếng Anh
John David Eblen, “The Maximum Clique Problem: Algorithms, Applications, and
Implementations”, University of Tennessee, Knoxville, 2010.
[2] “Clique (Graph Theory)”, địa chỉ truy cập:
.
[3]
“Bron – Kerbosch algorithm”, địa chỉ truy cập:
.
[4]
“The Clique Algorithm”, địa chỉ truy cập: />[5] Plato, Timaeaus, circa 350 B.C.
[1]

Tiếng Việt
[11] PGS. TS. Đỗ Văn Nhơn ,Bài giảng mơn học “Thuật tốn và phương pháp giải quyết
vấn đề”, Đại học CNTT, 2013.
[12] Giáo trình Lý thuyết đồ thị, địa chỉ truy cập:
.

16