Çizge Teorisinde Devralma Maliyeti Kavramı: Kombinatoryal Bir Analiz

Abstract

Pek çok gerçek dünya problemi kenar boyalı çizgelerle modellenebilir. Verilen bir çizgede bir patika üzerindeki bir dügüm üzerinden geçis yapılırken art arda iki farklı renkli kenardan geçis yapıldıgında olusan maliyete devralma maliyeti denir. Devralma maliyetinin degeri sadece bu iki renge baglıdır. Bu kavramın telekomünikasyon, ulasım agları ve enerji dagıtım agları gibi alanlarda önemli uygulamaları vardır. Örnegin bir kargo ulasım agında her renk karayolu ve hayayolu gibi farklı bir ulasım tipini temsil edebilir. Kargoyu belli bir dügümde bir yerden digerine tekrar yüklemenin maliyeti devralma maliyetine karsılık gelir. Bu kavram çok dogal oldugu ve pek çok uygulamaya sahip oldugu halde literatürde görece az çalısılmıstır. Bu projenin çıktıları bu baglamda literatüre önemli katkılar saglamıstır. Bu projede minimum devralma maliyetli agaç sekilleri, minimum devralma maliyetli döngü kapsaması, minimum devralma maliyetli çap ve minimum devralma maliyetli kenar boyaması problemlerine odaklanılmıstır. Bu problemlerin özel hallerini icncelenmis ve temel olarak parametreli karmasıklık açısından analiz edilmistir. Proje süresince ayrıca çizgelerde total baskınlıkla ilgili yeni bir arastırma problemiyle de ilgilenilmis ve önemli sonuçlar elde edilmistir. Proje sayesinde Fransa ile uzun vadeli bir isbirliginin önü açılmıstır. Yapılan çalısmalar sonucunda 1 adet SCI(E) endeksli dergi makalesi kabul edilmi, 2 adet SCI(E) endeksli dergi makalesi gönderimi yapılmıstır ve yanıt beklenmektedir. 1 adet SCI(E) endeksli dergi makalesi ise gönderime hazırlanmaktadır. Proje kapsamında 1 adet tam metin bildiri ve 2 adet özet bildiri de yayınlanmıstır. 1 adet tam metin bildiri ise gönderilmistir ve yanıt beklenmektedir. Ayrıca projenin son döneminde projeye katılan 1 adet doktora sonrası bursiyer ile çizgelerdeki total baskınlıkla ilgili yeni bir arastırma problemi üzerine çalısılmıs ve elde edilen sonuçlar SCI(E) endeksli bir dergiye gönderilmistir. Bu baglamda proje destegi, yeni arastırma konuları ve isbirliklerinin de önünü açmıstır.