Malatya merkezilik algoritmasına dayalı graf renklendirme algoritmasının harita renklendirme ve ders çizelgeleme uygulamaları
Map coloring and course scheduling applications of the graph coloring algorithm based on the malatya centrality algorithm
- Tez No: 965611
- Danışmanlar: DR. ÖĞR. ÜYESİ SELMAN YAKUT
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2025
- Dil: Türkçe
- Üniversite: İnönü Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Graf renklendirme problemi(GCP), ilk kez 1852 yılında Francis Guthrie tarafından İngiltere haritası üzerinde çalışırken ortaya atılmıştır. Guthrie, komşu bölgelerin farklı renklerle boyanması gerektiğini ve bunun dört renk ile mümkün olduğunu gözlemlemiştir. Bu problem zamanla graf kuramının temel konularından biri hâline gelmiştir. Graf renklendirmede temel amaç, komşu düğümlere farklı renkler atamak ve mümkün olan en az sayıda rengi kullanmaktır. Bu tezde, GCP'ye yeni bir yaklaşım olarak Malatya Vertex Coloring(MVC) Algoritması geliştirilmiştir. MVC, graf yapısındaki her düğüm için Malatya Merkezilik değeri hesaplayarak en etkili düğümü belirler; bu düğümü komşularından farklı bir renkle boyar ve graf üzerinden çıkarır. İşlem, tüm düğümler renklendirilene kadar devam eder. Algoritmanın temel hedefi, kullanılan renk sayısını azaltmak ve çözümü polinom zamanda tamamlamaktır. Geliştirilen algoritma öncelikle GCP'ye uygulanmış, ardından harita renklendirme ve ders çizelgeleme gibi gerçek dünya problemlerinde test edilmiştir. Asya, Avrupa, Türkiye, ABD eyaletleri ve İstanbul ilçeleri gibi çeşitli haritalar üzerinde başarılı sonuçlar elde edilmiştir. MVC, klasik Dört Renk Teoremi'nden farklı olarak öngörülebilirliği ve hesaplama verimliliğiyle dikkat çekmektedir. Ayrıca üniversite ders çizelgeleme problemi(CSP) üzerinde de uygulanarak, dersler arası çakışmalar minimize edilmiş ve geçerli çizelgeler oluşturulmuştur. Elde edilen bulgular, MVC algoritmasının sezgisel ve klasik yöntemlere karşı güçlü, etkili ve uygulanabilir bir alternatif olduğunu ortaya koymuştur.
Özet (Çeviri)
The Graph Coloring Problem (GCP) was first introduced in 1852 by Francis Guthrie while working on the map of England. Guthrie observed that adjacent regions needed to be colored differently and that this could be achieved using only four colors. Over time, this problem became one of the fundamental topics in graph theory. The primary goal in graph coloring is to assign different colors to adjacent vertices while minimizing the total number of colors used. In this thesis, a novel approach to the graph coloring problem, the Malatya Vertex Coloring (MVC) Algorithm, is proposed. The MVC algorithm calculates the Malatya Centrality (MC) value for each vertex in the graph to identify the most influential node. This node is then colored with a color different from its neighbors and removed from the graph. The process continues until all vertices are colored. The main objective of the algorithm is to reduce the number of colors used and to achieve this within polynomial time. Initially, the proposed algorithm was applied to the graph coloring problem, and subsequently tested on real-world problems such as map coloring and course timetabling. Successful results were obtained on various maps including Asia, Europe, Turkey, U.S. states, and districts of Istanbul. Unlike the classical Four Color Theorem, MVC stands out for its predictability and computational efficiency. Furthermore, the algorithm was applied to the university course timetabling problem, where course conflicts were minimized and valid timetables were generated. The findings demonstrate that the MVC algorithm is a robust, effective, and practical alternative to classical and heuristic-based methods.
Benzer Tezler
- Malatya merkezilik tabanlı graf renklendirme yönteminin sudoku ve 8 vezir kısıt tatmin problemlerine uygulanması
Application of the Malatya centre-based graph colouring method to sudoku and the 8-queen constraint satisfaction problems
ERKAN KARAGÖZ
- Haber metinlerinin özetlenmesinde graf teorisi ve Malatya merkezilik algoritmasının kullanılması
Using graph theory and Malatya centrality algorithm in summarizing news texts
CEVHER TAYYİB BAKAN
- Kablosuz sensör ağlarının çizge teorisi temelli yöntem ile konumlandırılması
Location of wireless sensor networks using graph theory based method
CEMALETTİN SONAKALAN
- Drone görüntülerinden derin öğrenme teknikleri ile kayısı rekolte tahmini
Apricot harvest prediction with deep learning techniques from drone images
RECEP BİÇER
