Çizge boyama problemleri üzerine kapsamlı bir araştırma

Çizge teorisi, yüksek teorik öneminden dolayı ve pratikte uygulama alanlarının sık olması sebebiyle matematiğin önemli araştırma alanlarından biridir. Özel olarak çizge boyama probleminin inceleneceği bu tezde; öncelikle bazı temel kavramlar verilecektir. Bunun yanı sıra çizge boyama problemi ile ilgili olarak var olan teorik alt/üst limitler ile ilgili önemli sonuçlar sunulacaktır. Ayrcıca karmaşıklık teoresinin önemli kavramları ve temelleri tanıtılacak olup bunlar yardımıyla P ve NP probleleri formel ve informel olarak tanıtılacaktır. Bunlarla beraber NP-Tam problem sınıfı verilecek ve Cook-Levin Teoremi yardımıyla bu sınıfın boş olmadığı gösterilecektir. Bu sayede verilen herhangi bir çizgenin verilmiş bir k doğal sayısı için $k$ renk ile uygun bir biçimde boyanıp boyanamadığını belirlemenin bir NP-tam problem olduğunu göreceğiz. Bu problemi polinom zamanda çözen algoritmalar mevcut değildir fakat literatürde bilinen ve optimal olmasa dahi verilen çizgelerin boyanmalarına yönelik bazı önemli algoritmalar vardır. Bunlardan Greedy, DSatur, HEA ve TabuCol algoritmaları detayları ile sunulucak ve karşılaştırmaları özgün olarak rasgele üretilen çizgeler üzerinden yapılacaktır. Çizge boyama problemi gerçek hayatta bazı uygulamalara da sahiptir. Bu uygulamalarla ilgili çeşitli detaylar sunulacatır. Bu kapsamda en önemli ve yaygın uygulaması olan sınav takvimi oluşturmak adına özgün bir tasarım yapılarak Greedy algoritması mantığıyla Python programlama dilinde bir yazılım gerçeklenmiştir. Sonuç olarak bu tez çizge boyama ve karmaşıklık teoreisi üzerine nitelikli bir Türkçe kaynak olacaktır. Ayrıca yazılan bu program yardımıyla "Hacettepe ¨Üniversitesi, Fen Fakültesi, Matematik Bölümü" hizmetine sunulacaktır.