Azami döngüsüz eşleştirme problemi

Bu tezin amacı, doymuş düğümlerin herhangi bir döngü içermeyen indüklenmiş alt çizgelerinin olduğu Azami Eşleştirme anlamına gelen Azami Döngüsel Eşleştirmeyi bulmaktır. Azami Eşleştirme Problemi, mümkün olan en büyük eşleştirme kümesini bulmaya çalışır. Kombinatoryal algoritma ile çözülebilen literatürde sıklıkla rastlanan bir problemdir. Bununla birlikte, azami döngüsüz eşleştirme problemi için, sadece azami eşleştirmeyi değil, aynı zamanda doymuş düğümlerin indüklenmiş alt çizgelerinin herhangi bir döngüye sahip olmamasını istiyoruz. Bu amaçla, döngüsüzlük kısıtına ihtiyaç vardır. Belirli çizge sınıfları için oluşturulmuş bazı kesin ve yaklaşık algoritmalar olmasına rağmen, genel çizgeler için azami döngüsüz eşleştirmeyi bulan bir algoritma yoktur. Bu çalışmada dört algoritma oluşturulmuştur. Farklı yoğunluk seviyelerine ve boyutlara sahip rastgele oluşturulmuş çizgeler, bunların performanslarını analiz etmek için kullanılır. Algoritmalardan ikisi, Kompakt ve Ayrıştırma formülasyonları olan kesin algoritmalardır. Bunların verimliliğine bağlı olarak, Ayrıştırma daha iyi performans sergilemiştir. Diğer iki algoritma ise Modifikasyon ve Konstrüksiyon yaklaşımı olan buluşsal yöntemlerdir. Hem optimale yaklaşma hem de zaman verimliliği açısından Konstrüksiyon yaklaşımının Modifikasyon yaklaşımından daha iyi performans gösterdiği gözlemlenmiştir. Kesin ve buluşsal yöntemlerin en iyileri karşılaştırıldığında Ayrıştırma formülasyonu optimallik yönünden en iyi performansı göstermiştir ancak büyük boyuta sahip çizgeler için uygulanabilir değildir. Konstrüksiyon yaklaşımı daha kısa zamanda optimala yakın makul sonuçlar verir. Ayrıca çizge boyutu ve yoğunluğu büyüdükçe döngüsüzlük kısıtının etkisinin arttığı görülmektedir.