DAA - Max Cliques

Trong một biểu đồ vô hướng, một cliquelà một đồ thị con hoàn chỉnh của đồ thị đã cho. Đồ thị con hoàn chỉnh có nghĩa là, tất cả các đỉnh của đồ thị con này được nối với tất cả các đỉnh khác của đồ thị con này.

Bài toán Max-Clique là bài toán tính toán để tìm ra cực đại của đồ thị. Max clique được sử dụng trong nhiều bài toán trong thế giới thực.

Chúng ta hãy xem xét một ứng dụng mạng xã hội, trong đó các đỉnh đại diện cho hồ sơ của mọi người và các cạnh thể hiện sự quen biết lẫn nhau trong một biểu đồ. Trong biểu đồ này, một nhóm đại diện cho một tập hợp con những người đều biết nhau.

Để tìm một nhóm tối đa, người ta có thể kiểm tra một cách có hệ thống tất cả các tập con, nhưng kiểu tìm kiếm thô bạo này quá tốn thời gian đối với các mạng bao gồm hơn một vài chục đỉnh.

Algorithm: Max-Clique (G, n, k) 
S := Φ 
for i = 1 to k do 
   t := choice (1…n)  
   if t Є S then 
      return failure 
   S := S ∪ t  
for all pairs (i, j) such that i Є S and j Є S and i ≠ j do 
   if (i, j) is not a edge of the graph then  
      return failure 
return success

Phân tích

Bài toán Max-Clique là một thuật toán không xác định. Trong thuật toán này, trước tiên chúng tôi cố gắng xác định một tập hợpk các đỉnh khác nhau và sau đó chúng tôi cố gắng kiểm tra xem các đỉnh này có tạo thành một đồ thị hoàn chỉnh hay không.

Không có thuật toán xác định thời gian đa thức để giải quyết vấn đề này. Vấn đề này là NP-Hoàn thành.

Thí dụ

Hãy xem biểu đồ sau. Ở đây, đồ thị con chứa các đỉnh 2, 3, 4 và 6 tạo thành một đồ thị hoàn chỉnh. Do đó, biểu đồ phụ này là mộtclique. Vì đây là biểu đồ con hoàn chỉnh tối đa của biểu đồ được cung cấp, nó là4-Clique.