Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
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
- İngilizce Wikipedia "Independent set (graph theory)" maddesi30 Kasım 2011 tarihinde Wayback Machine sitesinde arşivlendi. (İngilizce)
Ayrıca bakınız
Dış bağlantılar
- Wolfram MathWorld: "Maximal Independent Vertex Set" maddesi16 Ocak 2012 tarihinde Wayback Machine sitesinde . (İngilizce)
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Bagimsiz kume bir cizgede birbirleriyle komsu olmayan dugumleri iceren kumedir G V E displaystyle G V E cizgede dugumler kumesi S V displaystyle S subseteq V de arasinda ayrit olan iki dugum bulunmuyorsa S bagimsizdir denir Bagimsiz kume problemi NP Tam bir problemdir Yani Polinomsal zaman da problemi cozen bir algoritma bulunamamistir 24 dugumlu bu cizgede en buyuk bagimsiz kume mavi olarak isaretlenmis 9 dugumden olusur Kucuk bagimsiz kumelerin bulunmasi kolaydir tek bir dugum de bagimsiz kume olusturur asil zor olan en buyuk bagimsiz kumenin bulunmasidir Iki komsu secilmeden uygun dugumler eklenerek en buyuk kume bulunmalidir En basit kaba kuvvet brute force algoritma her dugum alt kumesinin bagimsiz kume olup olmadigini kontrol etmektir Sekildeki cizgede 3 4 5 bir bagimsiz kumedir En buyuk bagimsiz kume ise 1 4 5 6 kumesidir KaynakcaIngilizce Wikipedia Independent set graph theory maddesi30 Kasim 2011 tarihinde Wayback Machine sitesinde arsivlendi Ingilizce Ayrica bakinizKarmasiklik NP TamDis baglantilarWolfram MathWorld Maximal Independent Vertex Set maddesi16 Ocak 2012 tarihinde Wayback Machine sitesinde Ingilizce