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

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.
Nội dung trích xuất từ tài liệu:
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à ĐtgTạp chí KHOA HỌC & CÔNG NGHỆ102(02): 9 - 13BÀI TOÁN CLIQUE LỚN NHẤT - ỨNG DỤNGVÀ NHỮNG THÁCH THỨC TÍNH TOÁNĐàm Thanh Phương*, Ngô Mạnh Tưởng, Khoa Thu HoàiTrường Đại học Công nghệ thông tin và Truyền thông – ĐH Thái NguyênTÓM TẮTBà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ềuvấ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ácclique 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 hayphâ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úngtô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ácVới mỗi tập con S ⊂ V , đồ thị con sinh bởiS đượcđịnhnghĩalàđỉnh V và tập hữu hạn ( có thể rỗng) các cạnhE ⊆ V × V là các cặp không có thứ tự haiphầ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ếuMột tập đỉnh S được gọi là một clique nếuG ( S ) là đồ thị đầy đủ. Chúng ta cũng phân( 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ị( )E = {( i, j ) i, j ∈ V , i ≠ j , ( i, j ) ∉ E} . Đồ thịG = V , E , có cùng tập đỉnh V và tập cạnhđược gọi là liên thông nếu tồn tại đường đigiữa hai đỉnh bất kỳ. Các thành phần liênthông của đồ thị là các đồ thị con liên thôngcự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 đỉnhbất kỳ được gọi là đường kính. Mật độ của đồthị được xác định bởi giá trị: 2 E . HaiV2−Vđồ thị G1 = (V1 , E1 ) , G2 = (V2 , E2 ) được gọilà đẳng cấu nếu tồn tại một song ánhφ :V1 → V2 thoả mãn::( u, v ) ∈ E1 ⇔ (φ ( u ) , φ ( v ) ) ∈ E2 .*Tel: 0912 998749, Email: dtphuong@ictu.edu.vnG (S ) = (S, E ∩ S × S )biệt giữa clique cực đại là clique không thuộcbất cứ một clique nào rộng hơn nó, với cliquelớn nhất là clique có số phần tử lớn nhất. Mộttậ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( ) là liên thông và có ít nhấtđồ thị con G Cγ q ( q − 1) γ2 (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 chiatập đỉnh thành các tập ổn định rời nhau. Trongkhi phủ clique là phân vùng tập đỉnh thànhcá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 cliquelớ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à9Đàm Thanh Phương và ĐtgTạp chí KHOA HỌC & CÔNG NGHỆω ( G ) và gọi là chỉ số clique. Tương tự bàitoá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 địnhlớn nhất, ký hiệu là α ( G ) . Số màu hay sắcsố 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ánphủ 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ínhxác giải bài toán có thời gian tăng theo hàmmũ 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ênta 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ánphù hợp. Hai trong các đỉnh của clique lớnnhấ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 cliquelớ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ácthách thức tính toán liên quan đến clique, tựaclique 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ã, ...