Minimum yarık boyama

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.