Çizgelerde baskın kümeyi bulmak için Malatya merkezilik değerlerini kullanan yeni bir yöntem önerisi

Baskın küme problemi (dominating set problem), çizge teorisinde üzerinde oldukça çalışılan bir problem olup karmaşıklık olarak NP-Tam problemler grubuna girmektedir. Bundan dolayı günümüze kadar bu problemin çözümü için yapılan çalışmalar üç grupta toplanabilir. Sezgisel yöntemler, tam yöntemler ve yaklaşık yöntemler şeklinde gruplandırılabilirler. Sezgisel yöntemler sağlam olmayan her zaman aynı çizge için aynı sonucu veremeyen yöntemlerdir ve bu yöntemler olasılık tabanlı olup karmaşıklık analizleri çoğunlukla yapılmaz. İkinci grupta yer alan tam yöntemlerde ise, çözüm olabilecek bütün durumlar denenir ve ondan sonra çözüm ortaya konulur. Bu yöntemler çalışabildikleri çizgeler için minimum çözümü garanti ederler fakat zaman veya uzay karmaşıklıkları üstel olan yöntemlerdir. Son grupta yer alan yöntemler ise, minimum çözüm iddiaları olmayan yaklaşık çözüm noktasında da kesin iddiaları olmayan yöntemlerdir. Bu tez çalışmasında Malatya Merkezilik kavramının ikincisinin çizge teorisi problemlerinden olan Baskın Küme probleminin çözümü için kullanılabileceği iddiası ortaya konuldu. Malatya Merkezilik yönteminin kullanılması önerilecek yöntemin zaman ve uzay karmaşıklıklarının polinomsal olmasını sağlayacaktır. Aynı zamanda önerilen yöntemin bazı çizge grupları için minimum çözümü elde ettiği ortaya konuldu ve geriye kalan çizgelerde ise, minimum çözüme çok yakın sonuçlar elde edebildiği ortaya konulmuştur (minimum çözümden bir fazla düğümlü çözüm bulması gibi). Tez çalışmasında İkinci Malatya Merkezilik kavramı kullanıldı ve bu yöntemin ilk kullanıldığı tez çalışması oldu. İkinci Malatya Merkezilik kavramının baskın küme probleminin çözümü için kullanılabileceği yorumlarla gösterildikten sonra önerilen yöntemin kodlamaları gerçekleştirildi ve sonuçlar kodlaması gerçekleştirilen yöntemden elde edilmiştir.