Bağımsız küme problemi sayfasının kaynağını görüntüle

[[Dosya:Independent_set_graph.gif|sağ|frame|
24 düğümlü bu çizgede en büyük bağımsız küme mavi olarak işaretlenmiş 9 düğümden oluşur.]]

'''Bağımsız küme''' bir çizgede birbirleriyle komşu olmayan
düğümleri içeren kümedir. <math>G=(V,E)</math> çizgede düğümler kümesi <math>S \subseteq V</math> '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.<br />
[[Dosya:ÇizgeBağımsızKüme.PNG]] Ş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==

{{Kaynakça}}
*[http://en.wikipedia.org/wiki/Independent_set_(graph_theory) İngilizce Wikipedia "Independent set (graph theory)" maddesi]{{Webarşiv|url=https://web.archive.org/web/20111130082029/http://en.wikipedia.org/wiki/Independent_set_(graph_theory) |tarih=30 Kasım 2011 }} {{İng}}

== Ayrıca bakınız ==

* [[Karmaşıklık]]
* [[NP-Tam]]

== Dış bağlantılar ==

*[http://mathworld.wolfram.com/MaximalIndependentVertexSet.html Wolfram MathWorld: "Maximal Independent Vertex Set" maddesi]{{Webarşiv|url=https://web.archive.org/web/20120116044538/http://mathworld.wolfram.com/MaximalIndependentVertexSet.html |tarih=16 Ocak 2012 }} {{İng}}

[[Kategori:Çizge teorisi]]