TAILIEUCHUNG - 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. | Đàm Thanh Phương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 9 - 13 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 Với mỗi tập con S ⊂ V , đồ thị con sinh bởi S được định nghĩa là đỉ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 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 ( 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 đ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 .
đang nạp các trang xem trước
