Grafik Boyama — Kromatik Sayı ve Uygulamaları

Grafik boyama genellikle tepe boyama anlamına gelir: her tepeye, komşu tepeler aynı rengi paylaşmayacak şekilde bir renk atarsınız. Bunu sağlayan en küçük renk sayısına kromatik sayı denir ve $\chi(G)$ ile gösterilir.

Hızlı sezgiyi isterseniz, renkler sadece çakışmasız etiketlerdir. İki tepe, aralarında kenar yoksa aynı rengi kullanabilir.

Bir dakikada grafik boyama tanımı

Geçerli bir boyamada, her kenar farklı renkteki iki tepeyi bağlar. Kuralın tamamı budur.

Dolayısıyla $\chi(G)=3$ ise, aynı anda şu iki ifade doğrudur:

• $3$ renkle geçerli bir boyama vardır
• yalnızca $2$ renkle geçerli bir boyama yoktur

Bu yüzden kromatik sayı bir minimumdur; sadece bir çizimde kullandığınız renk sayısı değildir.

Aksi belirtilmedikçe, giriş düzeyi bir derste grafik boyama, basit yönsüz bir grafın tepelerini boyamak demektir. Kenar boyama farklı kuralları olan başka bir problemdir.

Kromatik sayı aslında neyi ölçer

Renk adlarının önemi yoktur. Kırmızı, mavi ve yeşil kullanabilirsiniz ya da $1$, $2$ ve $3$ etiketlerini.

Önemli olan gruplamadır. Aynı renge sahip tüm tepeler, kendi içinde hiç kenar bulunmayan bir küme oluşturur; yani o grubun içinde çakışma yoktur.

Grafik boyamayı çizelgeleme ve kaynak tahsisi problemlerinde faydalı yapan bakış açısı budur. Bir renk çoğu zaman “bu öğeler aynı zaman dilimini paylaşabilir” anlamına gelir.

Çözümlü örnek: neden 5-çevrim 3 renk gerektirir

Kenarları $AB, BC, CD, DE,$ ve $EA$ olan çevrim grafı $C_5$'i ele alalım.

Önce $2$ rengi deneyin. $A$'ya $1$ rengini, $B$'ye $2$ rengini verin. Sonra boyama çevrim boyunca zorunlu olarak şöyle ilerler:

$$A=1,\quad B=2,\quad C=1,\quad D=2$$

Şimdi $E$'ye bakın. Hem $D$'ye hem de $A$'ya komşudur; dolayısıyla $D$ yüzünden $2$ rengini, $A$ yüzünden de $1$ rengini kullanamaz.

Demek ki $2$ renk yetmez.

Ama $3$ renk işe yarar. Geçerli bir boyama şu şekildedir:

$$A=1,\quad B=2,\quad C=1,\quad D=2,\quad E=3$$

dolayısıyla

$$\chi(C_5)=3$$

Bu örneği hatırlamaya değer, çünkü önemli bir örüntüyü gösterir: çevrim graflarında çift uzunluklu bir çevrim $2$ renkle boyanabilir, ama tek uzunluklu bir çevrim $3$ renk gerektirir.

Küçük graflarda grafik boyama hakkında nasıl düşünülür

İki hızlı kontrol yardımcı olur.

İlk olarak, zorunlu bir çakışma arayın. Yukarıdaki örnekte, tek uzunluklu bir çevrim boyunca iki rengi sırayla vermek, son tepenin eldeki iki seçenekle de çakışmasına yol açar.

İkinci olarak, bir alt sınır arayın. Bir graf bir üçgen içeriyorsa, bu üç tepe ikişer ikişer komşudur; dolayısıyla zaten $3$ farklı renk gerektirir. Bu her zaman tam cevabı vermez, ama kromatik sayının en az $3$ olduğunu kanıtlar.

Grafik boyama problemlerinde yaygın hatalar

Yaygın bir hata, tepeleri sadece çizimde birbirine yakın göründükleri için komşu sanmaktır. Boyama kısıtı yalnızca gerçek bir kenardan doğar.

Bir başka hata da her tepenin kendi rengine ihtiyaç duyduğunu varsaymaktır. Komşu olmayan tepeler aynı rengi yeniden kullanabilir ve verimli boyamalar genellikle renkleri olabildiğince tekrar kullanır.

Öğrenciler bazen tepe boyama ile kenar boyamayı da karıştırır. Bu sayfada kural, komşu kenarlar hakkında değil, komşu tepeler hakkındadır.

Son bir hata da gereken minimum sayı yerine, o anda kullandığınız renk sayısını rapor etmektir. Bir grafı $4$ renkle boyamak, kromatik sayının $4$ olduğunu kanıtlamaz.

Grafik boyama nerelerde kullanılır

Standart bir uygulama çizelgelemedir. Her tepenin bir sınavı temsil ettiğini ve bir kenarın, iki sınavın ortak öğrencileri olduğu için aynı anda yapılamayacağını gösterdiğini düşünün. Bu durumda bir renk bir zaman dilimini temsil edebilir.

Bu modelde kromatik sayı, mümkün olan en az zaman dilimi sayısını verir. Eğer $\chi(G)=4$ ise, yalnızca $3$ zaman dilimiyle geçerli bir çizelge yoktur.

Aynı fikir, komşu bölgelerin farklı olması gereken harita boyamada ve aynı anda gereken değişkenlerin aynı yazmacı paylaşamadığı derleyici tasarımında da ortaya çıkar.

Benzer bir grafik boyama problemi deneyin

Tepeleri $P,Q,R,S,T$ ve kenarları $PQ, QR, RS, ST, TP,$ ve $PR$ olan bir graf çizin.

Alt sınır elde etmek için önce bir üçgen bulun. Sonra grafı mümkün olduğunca az renkle boyamayı deneyin ve komşu tepelerden herhangi birinin aynı renkte olup olmadığını kontrol edin. Bir sonraki adımı isterseniz, daha büyük bir graf üzerinde kendi sürümünüzü deneyin ve boyamanızın sadece geçerli değil, aynı zamanda minimal olduğunu da kanıtlayıp kanıtlayamayacağınıza bakın.