Malatya merkezilik algoritmasına dayalı graf renklendirme algoritmasının harita renklendirme ve ders çizelgeleme uygulamaları
| dc.contributor.advisor | Yakut, Selman | |
| dc.contributor.author | Karaca, Cezayir | |
| dc.date.accessioned | 2026-02-24T13:02:32Z | |
| dc.date.available | 2026-02-24T13:02:32Z | |
| dc.date.issued | 2025 | |
| dc.department | Fen Bilimleri Enstitüsü, Bilgisayar Mühendisliği Ana Bilim Dalı | |
| dc.description.abstract | 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. | |
| dc.description.abstract | 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. | |
| dc.identifier.endpage | 39 | |
| dc.identifier.startpage | 1 | |
| dc.identifier.uri | https://tez.yok.gov.tr/UlusalTezMerkezi/TezGoster?key=ftqJzTasnJUH9hg-S5861mzjiuHb0UZAWPl306GWs_U7RxhTpt5BxclvMVMALo6t | |
| dc.identifier.uri | https://hdl.handle.net/11616/106615 | |
| dc.identifier.yoktezid | 965611 | |
| dc.language.iso | tr | |
| dc.publisher | İnönü Üniversitesi | |
| dc.relation.publicationcategory | Tez | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.snmz | KA_TEZ_20260224 | |
| dc.subject | Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol | |
| dc.subject | Computer Engineering and Computer Science and Control | |
| dc.title | Malatya merkezilik algoritmasına dayalı graf renklendirme algoritmasının harita renklendirme ve ders çizelgeleme uygulamaları | |
| dc.title.alternative | Map coloring and course scheduling applications of the graph coloring algorithm based on the malatya centrality algorithm | |
| dc.type | Master Thesis |
