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
- Tez No: 1024429
- Danışmanlar: DOÇ. DR. SELMAN YAKUT
- Tez Türü: Yüksek Lisans
- Konular: Mühendislik Bilimleri, Bilim ve Teknoloji, Engineering Sciences, Science and Technology
- Anahtar Kelimeler: Grafik renklendirme, Grafik teorisi, Kısıt tatmin problemleri, Malatya Merkezlilik Algoritması, Sekiz-vezir problemi, Sudoku, Constraint satisfaction problems, Malatya Centrality Algorithm, graph coloring, Sudoku, Eight-Queens problem, graph theory
- Yıl: 2026
- Dil: Türkçe
- Üniversite: İnönü Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Yazılım Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Kısıt tatmin problemleri, bir takım kısıtlar altında değişkenlere uygun olan değerlerin atanmasının amaçlandığı ve çözüm uzaylarının karmaşıklığı ve büyüklüğünden dolayı ciddi hesaplama zorlukları barındıran problemlerdir. Sudoku ve Sekiz-Vezir problemleri, içerdikleri kısıtlar ve kombinatoryal yapı nedeniyle bu problem sınıfının en bilinen ve çok incelenen önemli örnekleri arasında yer almaktadır. Bu problemlerin çözüm çalışmalarında geri izleme, kısıt yayılımı, sezgisel arama ve optimizasyon temelli oldukça fazla yöntem tasarlanmış ve geliştirilmiş olmasına karşın, özellikle problemin boyutundaki büyümeler ile çözüm adımlarının etkili bir biçimde yönetilmesi güncelliğini koruyan bir araştırma alanı olarak önemini sürdürmektedir. Bu tezde, Önemli Kısıt tatmin problemlerinden olan Sudoku ve Sekiz-Vezir problemlerinin çözümünde Malatya Merkezilik Algoritması ile graf teorisine dayalı ve kontrollü graf renklendirme içeren bir yöntem geliştirilmiştir. Önerilen yöntemde problemler birer graf yapısı olarak modellenmiş, problemde yer alan kutucuklar birer düğüm ve bu düğümler arasında yer alan kısıtlar gözetilerek kenar bağlantıları tanımlanmıştır. Üretilen graf yapılarının üzerinde Malatya Merkezilik Algoritması uygulanarak düğümlerin merkezilik değerleri hesaplanmış ve bu değerler düğümlerin önceliklerinin belirlenmesinde kullanılmıştır. Ardından düğümler elde edilen merkezilik değerleri gözetilerek sıralanmış ve kontrollü bir biçimde renklendirme süreci yürütülmüş problem çözümleri elde edilmiştir. Önerilen yaklaşım, 1.000.000 adet Sudoku bulmacasına kadar ve farklı zorluk seviyelerinde diğer graf renklendirme algoritmaları ile karşılaştırılmış, diğer bir çalışmada ise yaklaşım 64x64 boyutunda kadar büyütülen Sekiz-Vezir problemleri ele alınarak güncel graf renklendirme algoritmaları ile karşılaştırılmış ve incelenmiştir. Sonuçlar göz önüne alındığında, Malatya Merkezilik algoritması düğüm merkezilik hesabına dayalı önceliklendirme mekanizmasının graf renklendirme sürecinin yönlendirilmesinde etkili sonuçlar ürettiğini ve kısıt tatmin problemlerinin çözümüne yönelik uygulanabilir etkili bir yaklaşım sunduğunu göstermektedir.
Özet (Çeviri)
Constraint satisfaction problems involve assigning appropriate values to variables under a set of constraints and pose significant computational challenges due to their large solution spaces. Sudoku and the Eight-Queens problem are among the most widely studied examples of this problem class because of their combinatorial structures and constraint-based nature. Although numerous approaches based on backtracking, constraint propagation, heuristic search, and optimization techniques have been developed, effectively managing the solution process, particularly as problem size increases, remains an active research topic. This thesis proposes a graph-based method that combines the Malatya Centrality Algorithm with a controlled graph coloring approach for solving Sudoku and Eight -Queens problems. In the proposed method, each problem is transformed into a graph structure in which cells are represented as nodes and constraint relationships are represented as edges. The centrality values of the nodes are calculated using the Malatya Centrality Algorithm and are subsequently employed to determine node priorities. The nodes are then ordered according to their centrality values, and solutions are obtained through a controlled graph coloring process. The proposed approach was evaluated on Sudoku problems with different difficulty levels and on Eight-Queens problems of various sizes. In addition, its performance was compared with several contemporary graph coloring algorithms. The experimental findings demonstrate that the centrality-based node prioritization mechanism effectively guides the graph coloring process and provides a practical approach for solving constraint satisfaction problems.
Benzer Tezler
- Ulaşım ağlarının graf tabanlı analizleri
Graph-based analysis of transportation networks
AKIN ÇAĞLAR
Yüksek Lisans
Türkçe
2025
Trafikİnönü ÜniversitesiYazılım Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ FURKAN ÖZTEMİZ
- Çizgelerde baskın kümeyi bulmak için Malatya merkezilik değerlerini kullanan yeni bir yöntem önerisi
A new method proposed using Malatya centrality values to find the dominating set in graphs
ŞEYDA KARCI
Yüksek Lisans
Türkçe
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİnönü ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ FATİH OKUMUŞ
- 6 Şubat 2023 depremlerinin doğal gaz tüketimine etkisi: Malatya örneği
The impact of the February 6, 2023 earthquakes on natural gas consumption: Case of Malatya
SEÇKİN ODABAŞI
Yüksek Lisans
Türkçe
2025
Mühendislik BilimleriKonya Teknik ÜniversitesiHarita Mühendisliği Ana Bilim Dalı
PROF. DR. İBRAHİM ÖZTUĞ BİLDİRİCİ
- 6 Şubat Kahramanmaraş depreminden en çok etkilenen illerin Cumhuriyet Dönemi endüstri mirası yapılarının koruma kapsamında incelenmesi
Investigation of republican period industrial heritage structures in the provinces most affected by the february 6 Kahramanmaraş earthquake wi̇thin the scope of conservation
EMRE İPEK
Yüksek Lisans
Türkçe
2026
MimarlıkSüleyman Demirel ÜniversitesiMimarlık Ana Bilim Dalı
DR. ÖĞR. ÜYESİ AYŞE BETÜL GÖKARSLAN
- Şubat 2023 Türkiye depremlerinden etkilenen köprülerin hasar durumlarının tahmini
Estimation of damage conditions of bridges affected by february 2023 Türkiye earthquakes
MUSTAFA GÖVERCİN
Yüksek Lisans
Türkçe
2024
İnşaat Mühendisliğiİstanbul Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. AHMET ABDULLAH DÖNMEZ
PROF. DR. YASİN FAHJAN