Solving perfect graph modification problems and generating perfect graphs
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Boğaziçi Üniversitesi, FEN BİLİMLERİ ENSTİTÜSÜ, FEN BİLİMLERİ ENSTİTÜSÜ, Türkiye
Tezin Onay Tarihi: 2025
Tezin Dili: İngilizce
Öğrenci: BURAK NUR ERDEM
Danışman: TINAZ EKİM
Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
Özet:Çizge değiştirme problemleri, çeşitli çizge sınıfları için kapsamlı biçimde incelenmiş olup, literatürde bu problemlerle ilgili çok sayıda hesaplama karmaşıklığı sunan çalışma bulunmaktadır. Bununla birlikte, NP-zor durumların üstesinden gelmek için sunulan kesin algoritmalar nispeten azdır. Bu çalışmada, minimum kusursuz düzenleme, minimum kusursuz tamamlama, minimum kusursuz silme ve kusursuz sandviç problemleri için tamsayılı programlamaya dayalı kesin çözüm yöntemleri tanıtılmaktadır. Düzenleme problemi, bir çizgeyi kusursuz bir çizge haline dönüştürmek için gereken minimum ayrıt ekleme ve silme sayısını ararken, tamamlama problemi değişiklikleri yalnızca ayrıt eklemeleri ve silme problemi yalnızca ayrıt silmeleri ile sınırlandırır. Kusursuz sandviç problemi ise bir karar problemi olarak formüle edilir ve girdi olarak verilen çizgenin var olmayan ayrıtlarının yalnızca belirli bir altkümesinden bazıları ayrıta çevrilerek kusursuz bir çizge üretilip üretilemeyeceğini sorgular. Yaklaşımımız, Güçlü Kusursuz Çizge Teoremini kullanarak, tek delikleri ve bunların tümleyenlerini bir tamsayı programlama modeli içinde doğrusal kısıtlamalar olarak kodlamaktadır. Kısıtlamaların sayısının üstel büyümesi nedeniyle, daha büyük çizgeleri ele almak için yöntemler sunuyoruz. İhlal edilen kısıtları dinamik olarak tespit eden bir kesen düzlem algoritması öneriyoruz. Kesme düzlemi algoritmasının performansını güçlendirmek için, rastgele çizgelerde beklenen tek delik ve tümleyenlerinin sayısını analiz ediyoruz. Buna ek olarak, verilen çizgeyi kusursuz çizgeye dönüştüren buluşsal bir algoritma tanıtıyoruz ve bu algoritmayı kesen düzlem algoritmamızın içinde daha iyi üst sınırlar bulmak için kullanıyoruz. Yöntemlerimizin performansını yaptığımız deneylerle değerlendiriyoruz. Son olarak, önerdiğimiz buluşsal algoritmayı çizge üretme bakış açısından değerlendiriyoruz ve ürettiği kusursuz çizgelerin yapılarını inceliyoruz.