Çizge boyama problemleri üzerine kapsamlı bir araştırma
A comprehensive research on graph coloring problem
- Tez No: 951980
- Danışmanlar: DR. ÖĞR. ÜYESİ TALHA ARIKAN
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: Türkçe
- Üniversite: Hacettepe Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 97
Özet
Ç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.
Özet (Çeviri)
Graph theory is one of the most significant research areas in mathematics due to its wide range of practical applications. In this thesis, we focus specifically on the graph coloring problem. First, we introduce some fundamental concepts. Subsequently, we present key theoretical results concerning existing lower and upper bounds related to graph coloring. Additionally, we discuss essential concepts and foundations of computational complexity theory. Using these, we formally and informally introduce the classes of P and NP problems. Furthermore, we define the class of NP-complete problems and demonstrate, via the Cook-Levin Theorem, that this class is non-empty. Consequently, we establish that determining whether a given graph can be properly colored with a given number of colors k (where k is a natural number) is an NP-complete problem. Although no known polynomial-time algorithm solves this problem optimally, several heuristic algorithms exist in the literature for graph coloring. Among these, we examine the Greedy, DSatur, HEA, and TabuCol algorithms in detail and provide an original comparative analysis based on randomly generated graphs. The graph coloring problem also has real-world applications. We discuss various practical implementations, with a particular focus on examination scheduling, one of its most prominent and widely used applications. In this context, we develop an original design and implement a software solution in Python using Integer Linear Programming (ILP). In conclusion, this thesis serves as a comprehensive Turkish-language resource on graph coloring and computational complexity. Moreover, the developed software will be made available for use by the Department of Mathematics, Faculty of Science, Hacettepe University.
Benzer Tezler
- Greedy algorithms for distance-2 graph coloring and bipartite graph partial coloring
İki mesafeli çizge boyama ve iki parçalı çizge boyama için açgözlü algoritmalar
MUSTAFA KEMAL TAŞ
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ KAMER KAYA
- Hybrid evolutionary algorithms for solving the register allocation problem
Yazmaç özgüleme problemi için evrimsel karma algoritmalar
BETÜL DEMİRÖZ
Yüksek Lisans
İngilizce
2004
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ.DR. HALUK TOPÇUOĞLU
- Hyper-heuristics for grouping problems
Gruplama problemleri için çok hedefli üst buluşsallar
MURAT BİRBEN
Yüksek Lisans
İngilizce
2011
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYeditepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ENDER ÖZCAN
- Linear linkage encoding in genetic algorithms
Genetik algoritmalarda doğrusal bağlantı gösterimi
ÖZGÜR ÜLKER
Yüksek Lisans
İngilizce
2006
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYeditepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
Y.DOÇ.DR. EMİN ERKAN KORKMAZ
Y.DOÇ.DR. ENDER ÖZCAN
- On the graph coloring problem
Çizge boyama problemi
AHMED MOHAMMED ABBAS ABBAS
Yüksek Lisans
İngilizce
2016
MatematikYıldız Teknik ÜniversitesiMatematik Ana Bilim Dalı
DOÇ. DR. FATİH DEMİRKALE