Minimum split coloring

---

Tezin Türü: Doktora

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: 2012

Tezin Dili: İngilizce

Öğrenci: RIDVAN MERT YÜZSEVER

Danışman: TINAZ EKİM

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

Birleşimsel eniyileme, eniyileme alanının önemli bir dalıdır. Gerçek hayattaki örneğin ulaştırma, tarife, üretim ve telekomünikasyon alanlarındaki birçok problem bir birleşimsel eniyileme problemi olarak modellenebilir. Bir birleşimsel eniyileme probleminin sınırlı sayıda çözümü olmasına rağmen, bu çözüm kümesini taramak birçok problemde kolay değildir. Çizge kuramı, on yıllardır eniyileme alanında en çok çalışılan alanlardan biridir. Bu konuda birçok değişik yaklaşımı barındıran büyük bir yazın vardır. Bu alandaki en ünlü problemlerden bir tanesi çizge boyama problemidir. Bunun temel sebebi çok geniş bir uygulama alanı olmasıyla beraber bu problemi genel bir çizgede etkin bir şekilde çözen bir yol bulunamamıştır. Sütun üretme yönteminin dal-ve-sınır ağacının içinde kullanılması zor eniyileme problemleriyle başa çıkmada bir başarı öyküsüdür. Bu yöntem, birleşimsel eniyileme problemlerinin çoğunda çözüm kümesinin tek tek taranmasından ve dinamik programlama yönteminden daha iyidir. Bu tezde, çizge boyama probleminin bir genellemesi olan ve daha geniş bir uygulama alanına sahip Yarık Boyama Problemini inceliyoruz. Biz Yarık Boyama Probleminin genel bir çizgede sütun üretme yönteminin dal-ve-sınır ağacı içinde kullanılarak tam olarak çözülmesini açıklamaktayız.