DAA - Max Cliques
Yönlendirilmemiş bir grafikte cliqueverilen grafiğin tam bir alt grafiğidir. Tam alt grafik, bu alt grafiğin tüm köşelerinin bu alt grafiğin diğer tüm köşelerine bağlı olduğu anlamına gelir.
Max-Clique problemi, grafiğin maksimum kliğini bulmanın hesaplama problemidir. Max clique, birçok gerçek dünya probleminde kullanılır.
Köşelerin insanların profilini temsil ettiği ve kenarların bir grafikte karşılıklı tanışmayı temsil ettiği bir sosyal ağ uygulamasını düşünelim. Bu grafikte bir klik, birbirini tanıyan bir grup insanı temsil ediyor.
Maksimum bir kliği bulmak için, sistematik olarak tüm alt kümeler incelenebilir, ancak bu tür kaba kuvvet araması, birkaç düzineden fazla köşeden oluşan ağlar için çok zaman alıcıdır.
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 successAnaliz
Max-Clique problemi, deterministik olmayan bir algoritmadır. Bu algoritmada, önce bir dizi belirlemeye çalışıyoruzk farklı köşeler ve sonra bu köşelerin tam bir grafik oluşturup oluşturmadığını test etmeye çalışıyoruz.
Bu problemi çözmek için polinom zamanlı deterministik bir algoritma yoktur. Bu sorun NP-Complete.
Misal
Aşağıdaki grafiğe bir göz atın. Burada, 2, 3, 4 ve 6 köşelerini içeren alt grafik tam bir grafik oluşturur. Dolayısıyla, bu alt grafik birclique. Bu, sağlanan grafiğin maksimum tam alt grafiği olduğundan,4-Clique.
