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: Belirtilmemiş.
- 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ı: 65
Ö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
- Graf matrisleri ve enerji
Graph matrices and energy
ÇİLEM YAMAÇ
Yüksek Lisans
Türkçe
2019
MatematikBursa Uludağ ÜniversitesiMatematik Ana Bilim Dalı
PROF. DR. İSMAİL NACİ CANGÜL
- Tatil köylerinde arsa-yerleşim şeması-yoğunluk ilişkileri
The Relationship among building area-settlement schema density compenents in holiday villages
ÖMER EREM
- Dijital görüntü işleme
Digital image processing
MURAT GÜMÜŞER
Yüksek Lisans
Türkçe
2001
MatematikYıldız Teknik ÜniversitesiMatematik Ana Bilim Dalı
YRD. DOÇ. DR. İBRAHİM EMİROĞLU
- İnce dönel kabukların dönel simetrik olan ve olmayan yükler altında statik hesabı ile ilgili bir yaklaşım
An Approach to solve problems of thin shells of revolution under statical, axially symmetrical and nonsymmetrical loads
FARUK YÜKSELER