Bağımsız küme problemi - Vikipedi
![](http://upload.wikimedia.org/wikipedia/commons/b/bd/Independent_set_graph.gif)
Bağımsız küme bir çizgede birbirleriyle komşu olmayan düğümleri içeren kümedir. çizgede düğümler kümesi 'de arasında ayrıt olan iki düğüm bulunmuyorsa S bağımsızdır denir. Bağımsız küme problemi NP-Tam bir problemdir. Yani Polinomsal zaman'da problemi çözen bir algoritma bulunamamıştır.
Küçük bağımsız kümelerin bulunması kolaydır (tek bir düğüm de bağımsız küme oluşturur), asıl zor olan en büyük bağımsız kümenin bulunmasıdır. İki komşu seçilmeden uygun düğümler eklenerek en büyük küme bulunmalıdır.
En basit kaba kuvvet(brute-force) algoritma her düğüm alt kümesinin bağımsız küme olup olmadığını kontrol etmektir.
Şekildeki çizgede {3,4,5} bir bağımsız kümedir. En büyük bağımsız küme ise {1,4,5,6} kümesidir.
Kaynakça
[değiştir | kaynağı değiştir]- İngilizce Wikipedia "Independent set (graph theory)" maddesi30 Kasım 2011 tarihinde Wayback Machine sitesinde arşivlendi. (İngilizce)
Ayrıca bakınız
[değiştir | kaynağı değiştir]Dış bağlantılar
[değiştir | kaynağı değiştir]- Wolfram MathWorld: "Maximal Independent Vertex Set" maddesi16 Ocak 2012 tarihinde Wayback Machine sitesinde arşivlendi. (İngilizce)