Bài toán clique lớn nhất-Ứng dụng và những thách thức tính toán

Đàm Thanh Phương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 9 - 13 
 9
BÀI TOÁN CLIQUE LỚN NHẤT - ỨNG DỤNG 
VÀ NHỮNG THÁCH THỨC TÍNH TOÁN 
Đàm Thanh Phương*, Ngô Mạnh Tưởng, Khoa Thu Hoài 
Trường Đại học Công nghệ thông tin và Truyền thông – ĐH Thái Nguyên 
TÓM TẮT 
Bài toán clique lớn nhất là một bài toán kinh điển của lý thuyết đồ thị và có nhiều ứng dụng. Nhiều 
vấn đề trong các mạng xã hội, sinh học, tài chính được giải quyết thông qua bài toán tìm kiếm các 
clique trong đồ thị. Clique và phân vùng clique cũng được sử dụng như một công cụ phân cụm hay 
phân loại dữ liệu. Tuy nhiên các bài toán thực tế thường được mô hình hoá bằng đồ thị rất lớn và 
cần phải có bộ nhớ lưu trữ đủ lớn cho quá trình thực hiện các thuật toán. Qua bài báo này, chúng 
tôi sẽ thảo luận bốn ứng dụng và xác định những thách thức tính toán đến từ lý thuyết cũng như 
thực hành. 
Từ khoá: Cliques, tựa clique, phân vùng clique, tập độc lập, bài toán clique lớn nhất, bài toán tập 
độc lập lớn nhất. 
GIỚI THIỆU* 
Một đơn đồ thị vô hướng G là cặp 
( ),V E bao gồm tập hữu hạn, khác rỗng các 
đỉnh V và tập hữu hạn ( có thể rỗng) các cạnh 
E V V⊆ × là các cặp không có thứ tự hai 
phần tử phân biệt của V . Trong bài báo này, 
chúng ta chỉ xét các đơn đồ thị vô hướng như 
trên và để vắn tắt, sẽ gọi chung là đồ thị. Hai 
đỉnh ,u v V∈ được gọi là hai đỉnh kề nếu 
( ),u v E∈ , nghĩa là một cạnh của đồ thị. Một 
đồ thị được gọi là đầy đủ nếu có cạnh giữa hai 
đỉnh bất kỳ. Đồ thị bù của G là đồ thị 
( ),G V E= , có cùng tập đỉnh V và tập cạnh 
( ) ( ){ }, , , , ,E i j i j V i j i j E= ∈ ≠ ∉ . Đồ thị 
được gọi là liên thông nếu tồn tại đường đi 
giữa hai đỉnh bất kỳ. Các thành phần liên 
thông của đồ thị là các đồ thị con liên thông 
cực đại. Độ dài của đường đi dài nhất trong số 
tất cả các đường đi ngắn nhất giữa hai đỉnh 
bất kỳ được gọi là đường kính. Mật độ của đồ 
thị được xác định bởi giá trị: 
2
2 E
V V−
. Hai 
đồ thị ( ) ( )1 1 1 2 2 2, , ,G V E G V E= = được gọi 
là đẳng cấu nếu tồn tại một song ánh 
1 2:V Vφ → thoả mãn: : 
( ) ( ) ( )( )1 2, ,u v E u v Eφ φ∈ ⇔ ∈ . 
*
 Tel: 0912 998749, Email: dtphuong@ictu.edu.vn 
Với mỗi tập con S V⊂ , đồ thị con sinh bởi 
S được định nghĩa là 
( ) ( ),G S S E S S= ∩ × 
Một tập đỉnh S được gọi là một clique nếu 
( )G S là đồ thị đầy đủ. Chúng ta cũng phân 
biệt giữa clique cực đại là clique không thuộc 
bất cứ một clique nào rộng hơn nó, với clique 
lớn nhất là clique có số phần tử lớn nhất. Một 
tập đỉnh S được gọi là một tập độc lập (tập 
ổn định) nếu hai đỉnh bất kỳ của S không kề 
nhau. Định nghĩa clique có thể tổng quát hoá 
cho khái niệm tựa clique. Một tựa clique hay 
γ -clique của đồ thị là tập đỉnh Cγ thoả mãn 
đồ thị con ( )G Cγ là liên thông và có ít nhất 
( )1
2
q qγ −  
 
 (1) 
cạnh, trong đó q Cγ= và [ ]0,1γ ∈ . Trong 
trường hợp đặc biệt, khi 0γ = , ( )G Cγ có 
thể không có cạnh nào và khi 1γ = thì Cγ là 
một clique của G . Tô màu đồ thị là phân chia 
tập đỉnh thành các tập ổn định rời nhau. Trong 
khi phủ clique là phân vùng tập đỉnh thành 
các clique rời nhau. Sau đây, ta gọi một phủ 
clique là phân vùng clique. 
Bài toán clique lớn nhất là bài toán tìm clique 
lớn nhất trong đồ thị đã cho. Ta ký hiệu số 
phần tử của clique lớn nhất trong đồ thị G là 
Đàm Thanh Phương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 9 - 13 
 10
( )Gω và gọi là chỉ số clique. Tương tự bài 
toán tập ổn định lớn nhất là bài toán tìm tập 
ổn định có số phần tử lớn nhất trong đồ thị. 
Chỉ số ổn định là số phần tử của tập ổn định 
lớn nhất, ký hiệu là ( )Gα . Số màu hay sắc 
số của đồ thị ( )Gχ là số nhỏ nhất các tập ổn 
định cần để tô màu đồ thị. Tương tự, số nhỏ 
nhất các clique cần để phân vùng clique đồ thị 
G được gọi là chỉ số phủ clique và ký hiệu 
( )Gχ . Bài toán clique lớn nhất và bài toán 
phủ clique là một trong 21 bài toán mà 
Richard Karp đã chứng minh là NP đầy đủ 
Nghĩa là, trừ khi P = NP, các thuật toán chính 
xác giải bài toán có thời gian tăng theo hàm 
mũ với số đỉnh của đồ thị. 
Vì một clique trong G cũng là một tập ổn 
định trong G nên ta có 
( ) ( )G Gα ω= (2) 
Hơn nữa ta cũng có các kết quả sau: 
 ( ) ( )G Gχ χ= (3) 
( ) ( )G Gω χ≤ (4) 
( ) ( )G Gα χ≤ (5) 
Dễ thấy số tập ổn định cần thiết để phủ đồ thị 
bằng số clique cần thiết để phủ đồ thị bù nên 
ta có đẳng thức (3). Vì vậy việc tìm sắc số đồ 
thị và chỉ số phủ clique là tương đương và tuỳ 
thuộc vào ứng dụng ta sẽ sử dụng bài toán 
phù hợp. Hai trong các đỉnh của clique lớn 
nhất không thể nằm cùng trong một tập ổn 
định nào. Vì vậy để phân chia tập đỉnh của đồ 
thị thành các tập ổn định rời nhau thì số tập 
ổn định ít nhất phải bằng số đỉnh của clique 
lớn nhất. Từ đó ta có bất đẳng thức (4). Bất 
đẳng thức (5) có được từ (2), (3), (4) với chú ý 
rằng đồ thị bù của đồ thị G chính là đồ thị G . 
Trong bài báo này chúng tôi thảo luận về các 
thách thức tính toán liên quan đến clique, tựa 
clique và phân vùng clique phát sinh từ bốn 
ứng dụng: Đồ thị các cuộc gọi, lý thuyết mã, 
đối sánh cấu trúc phân tử và giả thuyết Keller. 
ĐỒ THỊ CUỘC GỌI 
Các công ty điện thoại thường phải đối mặ 
với các tập dữ liệu khổng lồ. Ví dụ dữ liệu 
cuộc gọi đường dài của công ty AT&T trong 
năm 1999: xấp xỉ 300 triệu cuộc gọi một 
ngày, tương đương với yêu cầu không gian 
lưu trữ khoảng 20 terabytes một năm [1]. Việc 
phân tích tập dữ liệu này lại rất quan trọng 
cho công ty trong việc nghiên cứu mẫu khách 
hàng và tối ưu hoá hoạt động của họ. 
Cho một tập dữ liệu cuộc gọi trong một 
khoảng thời gian (ví dụ xếp từ các ngày đến 
các tháng). Chúng ta có thể xây dựng một đồ 
thị gọi là đồ thị cuộc gọi như sau: Mỗi người 
sử dụng điện thoại đại diện cho một đỉnh của 
đồ thị, mỗi cuộc gọi là một cạnh có hướng. 
Kết quả là ta được một đa đồ thị có hướng bởi 
vì một người A có thể gọi cho người B nhiều 
lần. Các tựa clique vô hướng của đồ thị này 
có thể cung cấp thông tin về nhóm người có 
mối liên kết cao. 
Đồ thị có hàng triệu đỉnh thường được gọi là 
đồ thị lớn. Ngay cả việc hiển thị trực quan 
trên màn hình hay các phân tích thống kê cơ 
bản là các nhiệm vụ khó khăn. Với các đồ thị 
rất lớn, chúng thường không phù hợp với bộ 
nhớ RAM của máy tính hoặc thậm chí vào bộ 
nhớ chính. Vì thế, thuật toán bộ nhớ mở rộng 
đã được phát triển. Đồ thị cuộc gọi có các tính 
chất quan trọng đặc biệt sau [2], [3]: 
- Đồ thị rất lớn, tới hàng triệu đỉnh. 
- Đồ thị có mật độ rất thấp, trong khoảng 
0,0000001 
- Đồ thị thường không liên thông, mặc dù 
chứa thành phần liên thông lớn 
- Đường kính vô hướng thấp, trong khoảng 
( )log n 
- Bậc vào ind và bậc ra outd của đỉnh phân 
phối theo luật: ( ) inin inP d d γ−
 với [2,3]inγ ∈ 
và ( ) outout outP d d γ−
 với 2outγ < , ở đây 
( )P d là tỷ số của số đỉnh có bậc d trên 
tổng số đỉnh của đồ thị. 
Trong [3], Abello đã nghiên cứu đồ thị cuộc 
gọi trong 1 ngày với các cuộc gọi cố định tại 
AT&T và nhận được một đồ thị cuộc gọi với 
Đàm Thanh Phương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 9 - 13 
 11
53 triệu đỉnh và 170 triệu cạnh. Để khai thác 
cấu trúc ở trên, tác giả đã phải thực hiện tiền 
xử lý mở rộng. Các phân tích thuật toán của 
đồ thị đó là rất quan trọng. Tuy nhiên, các 
thuật toán được biết đến không áp dụng tốt 
trên đồ thị như vậy. Điều này dẫn chúng ta 
đến thử thách đầu tiên. 
Thách thức 1 (Thuật toán cho các đồ thị 
cực lớn với mật độ rất thấp): Thiết kế một 
thuật toán hiệu quả cùng với tập dữ liệu cho 
bài toán γ -clique lớn nhất trong đồ thị lớn có 
các tính chất như đồ thị cuộc gọi. 
Các đồ thị tương tự đồ thị cuộc gọi có thế kể 
đến như đồ thị internet, đồ thị SMS, đồ thị từ 
mạng xã hội 
ĐỒ THỊ TRONG LÝ THUYẾT MÃ 
Bài toán cần quan tâm là: gửi một thông điệp 
qua kênh truyền có độ nhiễu cao với độ tin 
cậy lớn nhất có thể. Trong lý thuyết mã, 
người ta mong muốn tìm được một mã nhị 
phân đủ lớn có thể khắc phục một số lỗi nhất 
định với kích thước đã cho của từ nhị phân. 
Với từ nhị phân thể hiện bởi véc tơ 
( )0,1 nu ∈ , ký hiệu ( )eF u là tập hợp tất cả 
các véc tơ có thể thu được từ u do một lỗi e 
nào đó, chẳng hạn mất hoặc chuyển vị các bit. 
Chú ý rằng các phần từ của ( )eF u không nhất 
thiết có độ dài n vì có thể là kết quả của việc 
mất bit. Tập con ( )0,1 nC ⊆ được gọi là mã 
sửa lỗi e nếu 
( ) ( ) ; ,e eF u F v u v C∩ = ∅ ∀ ∈ với u v≠ . 
Bài toán đặt ra là tìm tập mã sửa lỗi lớn nhất, 
nghĩa là số phần tử của C là lớn nhất. 
Xét đồ thị gồm tập đỉnh là tập tất cả các véc 
tơ nhị phân ( )0,1 nu ∈ và có cạnh ( ),u v khi 
( ) ( )e eF u F v∩ ≠ ∅ . Theo cách này, mỗi 
cạnh thể hiện sự xung đột với mã sửa lỗi e . 
Đồ thị như vậy được gọi là đồ thị xung đột. 
Theo cấu trúc của đồ thị, một mã sửa lỗi 
tương đương với một tập ổn định trong G . 
Vì vậy mã sửa lỗi lớn nhất có thể tìm được 
thông qua việc giải bài toán tập độc lập lớn 
nhất trong đồ thị G vừa đề cập. 
Các cận dưới tốt của kích thước mã là điều có 
ý nghĩa đặc biệt cho các mã bất đối xứng, 
chẳng hạn như các mã sửa lỗi trong kênh Z ( 
các thành phần khác không của mọi véc tơ có 
thể thay đổi từ 1 đến 0). Vì điều này, một số 
phương pháp phân vùng đã được đề xuất, 
bằng cách phân vùng tập ổn định nhỏ nhất 
trên đồ thị xung đột [4]. Việc tìm kiếm các 
cận dưới tốt cho kích thước mã như trên và 
thuật toán phân vùng tập ổn định phù hợp là 
một thách thức cần thiết phải giải quyết. 
Thách thức 2: (Thuật toán cho các đồ thị 
xung đột trong lý thuyết mã) Thiết kế thuật 
toán hiệu quả cho bài toán phân vùng tập ổn 
định tối thiểu phù hợp với đồ thị xung đột ứng 
dụng trong lý thuyết mã. 
Một số ví dụ khác trong đó phân vùng clique 
tối thiểu được sử dụng như những cận dưới là 
các bài toán phủ bắt buộc, trong đó tập các 
điểm yêu cầu phải được phủ bởi tập điểm 
tiềm năng. Như bài toán vị trí xe cứu thương 
hay bài toán lát 
ỨNG DỤNG TRONG BÀI TOÁN SO KHỚP 
CẤU TRÚC PHÂN TỬ 
Trong ngành công nghiệp dược phẩm và hoá 
chất nông nghiệp, bài toán xác định mối quan 
hệ cấu trúc giữa các cặp cấu trúc phân tử ba 
chiều là một bài toán quan trọng. Những cấu 
trúc phân tử ba chiều có thể được thể hiện 
bằng đồ thị. Ví dụ đối với cấu trúc Protein, 
các đỉnh của đồ thị được cho bởi các thành 
phần cấu trúc thứ cấp xoắn α và phiếm nếp 
gấp β , trong khi các cạnh được định nghĩa 
thông qua liên kết góc và khoảng cách giữa 
chúng [5]. Hơn nữa các đỉnh và cạnh đều 
được gán nhãn tương ứng với các kiểu nguyên 
tử và khoảng cách giữa các nguyên tử. 
Cho một cặp đồ thị đã được gán nhãn 
( ) ( )1 1 1 2 2 2, ; ,G V E G V E= = . Khi đó xây 
dựng đồ thị C , gọi là đồ thị tương ứng của 
hai đồ thị trên, như sau: Nếu hai đỉnh 
1 1 2 2,v V v V∈ ∈ có cùng nhãn thì cặp 1 2v v là 
một đỉnh của C ; Hai đỉnh 1 2v v và 
' '
1 2v v có 
liên kết cạnh nếu các cạnh ( )'1 1 1,v v E∈ và 
( )'2 2 2,v v E∈ có nhãn giống nhau. 
Đàm Thanh Phương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 9 - 13 
 12
Với một cặp cấu trúc phân tử ba chiều, một 
đồ thị con chung lớn nhất trong hai đồ thị 
tương ứng của chúng liên hệ đến tập lớn nhất 
các nguyên tử có khoảng cách phù hợp. Vì 
vậy đồ thị con chung lớn nhất là một độ đo sự 
tương tự cấu trúc và cho thông tin quan trọng 
về hai phân tử. 
Theo cách xây dựng đồ thị C tương ứng từ 
hai đồ thị mô tả hai phân tử, ta nhận thấy đồ 
thị con giữa hai đồ thị 1 2,G G tương đương 
với clique trong đồ thị C . Vì vậy ta có thể 
tìm đồ thị con chung lớn nhất giữa hai đồ thị 
1 2,G G thông qua việc giải bài toán clique lớn 
nhất trong đồ thị C tương ứng. 
Thách thức 3 (Thuật toán cho đồ thị tương 
ứng với mật độ thấp): Thiết kế thuật toán 
hiệu quả cho bài toán clique lớn nhất trên đồ 
thị tương ứng phát sinh từ bài toán so khớp 
cấu trúc phân tử hoá học ba chiều. 
Những thách thức tương tự cũng xảy ra khi 
tính toán clique lớn nhất cho bài toán ghép 
protein, trong đó người ta muốn tìm hiểu xem 
hai loại protein hình thành liên kết ổn định 
hay không, hoặc để so sánh các cấu trúc 
protein. [7] 
GIẢ THUYẾT KELLER 
Giả thuyết Keller liên quan đến giả thuyết 
Minkowski, trong đó nói rằng bài toán lưới lát 
n

 bởi các khối đơn vị, tồn tại hai khối cùng 
(n-1) mặt. Định lý Minkowski đã được chứng 
minh bởi Hajos năm 1950. Keller đề xuất 
tổng quát hoá định lý Minkowski bằng cách 
bỏ giả sử lưới. Trong thực tế, Prron đã chứng 
minh điều này là đúng với 6n ≤ . Tuy nhiên 
với 8n ≥ , giả sử lưới là cần thiết và đã được 
chứng minh bởi Lagarias. Giả thuyết Keller 
vẫn còn là vấn đề mở với 7n = . 
Sau nhiều năm, các tranh luận về giả thuyết 
Keller vẫn chưa kết thúc. Qua đó, nhiều lớp 
đồ thị đối với bài toán clique lớn nhất cũng 
được phát sinh. Corradi và Szabo [6] đã xây 
dựng đồ thị gọi là đồ thị Keller nΓ với 
n
+∈
 . Tập đỉnh của nΓ là các véc tơ với 
độ dài n , với giá trị 0, 1, 2 hoặc 3. Hai đỉnh 
bất kỳ có kết nối cạnh khi và chỉ khi trong n 
toạ độ, có đúng hai toạ độ khác nhau. Đồ thị 
Keller là đồ thị dày đặc với kích thước clique 
bị chặn bởi 2n . Corradi và Szabo đã chứng 
minh rằng, tồn tại phản ví dụ về giả thuyết 
Keller khi và chỉ khi nΓ có clique kích thước 
bằng 2n . 
Với sự giúp đỡ của những kết quả này, 
Lagarias và Shor đã chỉ được phản ví dụ cho 
trường hợp số chiều 10n = . Tương tự, 
Mackey đã xây dựng được clique với số chiều 
bằng 8, và chứng minh giả thuyết Keller 
không đúng khi 8n ≥ . Tuy nhiên trong 
trường hợp 7n = vẫn là vấn đề mở, và có 
thách thức sau: 
Thách thức 4 ( Bài toán mở [6]) Với đồ thị 
Keller 7Γ , tìm clique lớn nhất có kích thước 
bằng 128 hoặc chứng minh không tồn tại 
clique như thế. 
KẾT LUẬN 
Chúng tôi đã hệ thống các ứng dụng dẫn tới 
các bài toán cliques, tựa clique, phân vùng 
clique trên các đồ thị lớn. Cấu trúc và tính 
chất của các đồ thị này có những điểm khác 
nhau. Nhưng nói chung kích thước và mật độ 
của chúng đều lớn. Điều này gây khó khăn 
cho việc thiết kế các thuật toán phù hợp với mỗi 
bài toán để có thể giải quyết chúng hiệu quả. 
TÀI LIỆU THAM KHẢO 
[1]. Hayes, B.: Graph Theory in Practice: PartI. 
American Scientist 88(1), 9(2000) 
[2]. Nanavati et all: Analyzing the Structure and 
Evolution of Massive Telecom Graphs. IEEE 
Trans actions on Knowledge and Data 
Engineering 20(5),703– 718(2008) 
[3]. Abello, Pardalos, Resende: On Maximum 
Clique Problems in Very Lagre Graphs. External 
Memory Algorithms .DIMACS Series, pp.119–
130, (1999) 
[4]. vanPul, et all: New lower bounds for constatn 
weight codes. IEEE Trans. Inform. Theory 35, 
1324–1329 (1989) 
[5]. Mitchell et all : Use of techniques derived from 
Graph theory to compare secondary structure motifs 
in proteins. J.Mol.Biol.212, 151 (1990) 
[6]. Corradi and Szabo : A Combinatorial 
Approach for Keller’s Conjecture. Periodica 
Math. Hung. 21(2), 95–100 (1990) 
[7]. Butenko, S.,Wilhelm, W.: Clique-detection 
models in computational biochemistry and 
genomics. Euorpean Journal of Operational 
Research 173,1–17 (2006) 
Đàm Thanh Phương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 9 - 13 
 13
SUMMARY 
THE MAXIMUM CLIQUE PROBLEM – APPLICATIONS AND 
COMPUTATIONAL CHALLENGES 
Dam Thanh Phuong*, Ngo Manh Tuong, Khoa Thu Hoai 
College of Information and Communication Technology - TNU 
Maximum clique is a classical problem of graph theory and have many applications. 
Many problems in social, biology and finance networks resolved through finding cliques. 
Clique partitions and clique have also been used as a clustering or data classification 
tools. However, the actual problem is often modeled by a very large graph and requires 
large data storage memory for implementation of algorithms. In this paper, we discuss 
four applications and identify computational challenges which are both of theoretical and 
practical. 
Keywords: Cliques, quasi – cliques, clique partitions, independent set, maximum clique problem, 
maximum independent set. 
Ngày nhận bài:8/11/2012, ngày phản biện:19/12/2012, ngày duyệt đăng:26/3/2013 
*
 Tel: 0912 998749, Email: dtphuong@ictu.edu.vn