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ị G V E G V E 1 1 1 2 2 2 = = ( , , , ) ( ) được gọi

là đẳng cấu nếu tồn tại một song ánh

1 2 φ :V V → thoả mãn: :

(u v E u v E , , )∈ ⇔ ∈ 1 2 (φ φ ( ) ( )) .

*

Tel: 0912 998749, Email: [email protected]

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à