Pençesiz çizgelerde maksimum-yakın bağımsız küme ve üst sınırları için yeni algoritma

Özet

Günümüzde çizgelerin bazı problemleri için hala yaklaşık çözüm yöntemleri kullanılmaktadır. Bunlar minimum baskın küme, maksimum bağımsız küme, maksimum hizip, mükemmel eşleştirme, Hamilton devresi bunlardan bir kısmıdır. Bu çalışmada maksimum bağımsız küme bulma problemine polinomsal olan bir yöntemin uygulaması üzerinde durulacaktır. Bu amaçla pençesiz çizgelerden olan kral çizgeleri üzerinde örnek çalışmalar gösterilecektir ve pençesiz çizgeler için maksimum bağımsız kümenin eleman sayısı için analitik bir sınır ortaya konulmaya çalışılacaktır.