Introduction to edge-coloring problem
Kenar-renklendirme problemine giriş
- Tez No: 737479
- Danışmanlar: DR. ÖĞR. ÜYESİ CELALETTİN KAYA
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Grafik teorisi, Graflar, Renklendirme, Sınıflandırma, Graph theory, Graphs, Coloring, Classification
- Yıl: 2022
- Dil: İngilizce
- Üniversite: Çankırı Karatekin Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Bu tezde çalışılan graf kenar renklendirme problemi temel olarak; bir grafın bütün kenarlarını, grafın birbirine komşu iki kenarının farklı renklerde olacak şekilde renklendirilmesi esasına dayanmaktadır. Buradaki zorluk, bir grafın böylesi bir kenar renklendirilmesinin elde edilebilmesi için gereken minimum sayıda rengin bulunmasıdır. Bir $G$ grafı için ihtiyaç duyulan minimum sayıda renge, bu grafın“kromatik indeksi”denir ve tüm tez boyunca $\chi'(G)$ olarak gösterilmiştir. Bu tezin ilk bölümü, graflarla, alt graflarla, graflardaki bağlantılılık kavramıyla, graflardaki eşleştirme ve faktörizasyon kavramlarıyla ilgili temel tanımların verildiği, bir graf teoriye giriş bölümüdür. İkinci bölüm, bizim esas konumuz olan graf kenar renklendirme ile ilgilidir. Bu bölümde, $\chi'$ parametresini yorumlamak için birden fazla yol verilmiş, $\chi'$ parametresi için üst ve alt sınırlar bulmak ile ilgili önemli çeşitli teoremler ifade ve ispat edilmiştir. Ayrıca, ikinci bölümde, sınıflandırma problemine giriş yapılmıştır. Bu bölümü, (dairesel kenar renklendirme, liste kenar renklendirme ve toplam renklendirme gibi) bazı çeşitli renklendirme konularına değinerek sonlandırdık. Bu tezin üçüncü ve son bölümü, etkin bir şekilde çalışan renklendirme algoritmalarının araştırılmasına ve geliştirilmesine yardımcı olan bazı ana sonuçların, bazı önemli teoremlerin ve varsayımların ifadelerinin bir incelemesi ve açıklamasıdır. Bu algoritmaların geliştirilmesi, kolay bir iş olmayan grafların kromatik indeksinin belirlenmesinde çok büyük bir adımdır.
Özet (Çeviri)
The problem of graph edge coloring, studied in this thesis, relies mainly on coloring the edges of a graph in a way that two distinct adjacent edges are assigned different colors. The challenge is to find the minimum number of colors necessary to give a proper edge coloring to a graph. This minimum number of colors is called the“chromatic index”of a graph $G$ and it is denoted by $\chi'(G)$ throughout this thesis. The first chapter of this thesis is an introduction to graph theory, by giving the basic but fundamental definitions of graphs, subgraphs, the concept of connectivity of graphs, also the concepts of matchings and factorization of graphs. The second chapter of this thesis talks about our main topic which is graph edge coloring, giving multiple ways to interpret the parameter $\chi'$, illustrating and proving various important theorems related to finding upper and lower bound for $\chi'$, but also an introduction to the classification problem. We end the second chapter by discussing some types of edge coloring (circular edge coloring, list edge coloring and total coloring). The third and the last chapter of this thesis is a study and description of some main results and statement of some important theorems and conjectures that would help the search and development of efficiently realized coloring algorithms, these algorithms when developed are a huge step forward into determining the chromatic index of graphs which is not an easy task.
Benzer Tezler
- Yapım aşamasında geçici kenar koruma sistemlerinin işsağlığı ve güvenliği açısından değerlendirilmesi
The assesment of temporary edge protection system with regards to occupational safety and health in construction process
MUHAMMED SADİ KARADEMİR
Yüksek Lisans
Türkçe
2018
İnşaat MühendisliğiMimar Sinan Güzel Sanatlar ÜniversitesiYapı Mühendisliği Ana Bilim Dalı
PROF. DR. SEMA ERGÖNÜL
- The effects of the double-wavelenght leading edge serrations on aerodynamic performance of the wing
Çift dalga boylu hücum kenarı çentiklerinin kanadın aerodinamik performansı üzerindeki etkileri
ZEHRA NUR KAPLAN
Yüksek Lisans
İngilizce
2023
Uçak Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
DR. DUYGU ERDEM
- Offloading decision with mobility-aware for mobile edge computing in 5G networks
5g şebekesinde mobil kenar bilgi işlem için mobilite bilinci ile aktarma kararları
SAEID JAHANDAR BONAB
Yüksek Lisans
İngilizce
2021
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. MUSTAFA ERGEN
- Dynamic and aeroelastic analysis of a helicopter blade with actively controlled trailing edge flap in forward flight
Aktif olarak kontrol edilen firar kenarı flabına sahip bir helikopter palinin ileri uçuş şartları altında dinamik ve aeroelastik incelemesi
ÖZGE ÖZDEMİR ÖZGÜMÜŞ
Doktora
İngilizce
2012
Uçak Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
PROF. DR. METİH ORHAN KAYA
- Mütûn-i Erbaa'da İmam Ebü Yûsuf'a atfedilen ibâdetle ilgili görüşlerin tahkiki
The exa min ation of the vtews attributed to İmam Abu Yûsuf tn the four classical hanafî text books (al-Mutun al-'Arba'a)
MEHMET EKİNCİ
Yüksek Lisans
Türkçe
2011
DinSelçuk ÜniversitesiTemel İslam Bilimleri Ana Bilim Dalı
PROF. DR. ORHAN ÇEKER