DAA - Klik Maks

Dalam grafik tidak berarah, a cliqueadalah sub-grafik lengkap dari grafik yang diberikan. Sub-grafik lengkap artinya, semua simpul dari sub-grafik ini terhubung ke semua simpul lain dari sub-grafik ini.

Masalah Max-Clique adalah masalah komputasi untuk menemukan klik maksimum dari grafik. Klik maks digunakan dalam banyak masalah dunia nyata.

Mari kita pertimbangkan aplikasi jejaring sosial, di mana simpul mewakili profil orang dan tepi mewakili kenalan bersama dalam grafik. Dalam grafik ini, klik mewakili subkumpulan orang yang semuanya saling mengenal.

Untuk menemukan klik maksimum, seseorang dapat secara sistematis memeriksa semua himpunan bagian, tetapi jenis pencarian brute force ini terlalu memakan waktu untuk jaringan yang terdiri dari lebih dari beberapa lusin simpul.

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

Analisis

Masalah Max-Clique adalah algoritma non-deterministik. Dalam algoritma ini, pertama-tama kami mencoba menentukan satu setk simpul yang berbeda dan kemudian kami mencoba untuk menguji apakah simpul ini membentuk grafik yang lengkap.

Tidak ada algoritma deterministik waktu polinomial untuk menyelesaikan masalah ini. Masalah ini NP-Complete.

Contoh

Perhatikan grafik berikut. Di sini, sub-grafik yang berisi simpul 2, 3, 4 dan 6 membentuk grafik lengkap. Oleh karena itu, sub-grafik ini adalah aclique. Karena ini adalah sub-grafik lengkap maksimum dari grafik yang disediakan, ini adalah a4-Clique.