Çizge Boyama
Çizge boyama, çizge elemanlarına, bitişik elemanların farklı olmasını sağlayacak şekilde etiketler veya renkler atama işlemidir ve bu işlem için gereken minimum renk sayısını inceler.
Tanım
Bir çizgenin uygun boyaması, bitişik iki köşenin aynı rengi paylaşmayacağı şekilde köşelerine renk atanmasıdır; kromatik sayı ise böyle bir atama için gereken en az renk sayısıdır.
Kapsam
Bu konu, uygun köşe boyamasını ve kromatik sayıyı, kenar boyamasını ve kromatik indeksi, boyamaları sayan kromatik polinomu ve Brooks teoremi, Vizing teoremi ile düzlemsel çizgeler için Dört Renk Teoremi gibi önemli sonuçları ele almaktadır. Boyamayı bağımsızlık, klikler ve çizge parametrelerinin daha geniş kuramı ile ilişkilendirmektedir.
Temel sorular
- Belirli bir çizgeyi uygun şekilde boyamak için gereken en az renk sayısı kaçtır?
- Bir çizge, belirli bir paletle kaç farklı uygun boyamaya izin verir?
- Hangi çizgeler az renkle boyanabilir ve hangi engeller çok sayıda renk gerektirir?
- Kenar boyamaları ve liste boyamaları temel kavramı nasıl genişletmektedir?
Anahtar kavramlar
- Uygun köşe boyaması
- Kromatik sayı
- Kromatik polinom
- Kenar boyaması ve kromatik indeks
- Brooks teoremi
- Dört Renk Teoremi
Temel kuramlar
- Dört Renk Teoremi
- Her düzlemsel çizge, en fazla dört renkle uygun şekilde boyanabilir; bu ifade bir yüzyıldan fazla süredir açık bir problem olup, ilk kez 1976'da Appel ve Haken tarafından kapsamlı bilgisayar destekli durum analizi kullanılarak ispatlanmıştır.
- Vizing teoremi
- Herhangi bir basit çizgenin kenarları, ya maksimum derece ya da maksimum derecenin bir fazlası kadar renkle uygun şekilde boyanabilir, bu da tüm çizgeleri iki dar sınıfa ayırmaktadır.
Klinik önem
Boyama, çakışmasız kaynak tahsisini modellemektedir: çatışmasız zaman çizelgeleme, derleyicilerdeki yazmaç tahsisi, kablosuz ağlarda frekans ataması ve Sudoku benzeri kısıt problemleri gibi durumların tümü çizge boyamaya indirgenmektedir.
Tarihçe
1852'de ortaya atılan Dört Renk Sanısı, boyama kuramının büyük bir kısmını yönlendirmiştir; Appel ve Haken tarafından 1976'da bilgisayar destekli olarak yapılan ispatı, bilgisayar destekli matematiğin erken dönemdeki önemli bir kilometre taşı olmuş ve ispatın doğası üzerine tartışmaları tetiklemiştir.
Tartışmalar
- Bilgisayar destekli ispatların durumu
- Dört Renk Teoremi'nin makine tarafından kontrol edilen durumlara dayanması, bir insanın elle doğrulayamayacağı kadar uzun bir ispatın gerçek bir matematiksel ispat olarak kabul edilip edilmeyeceği sorusunu gündeme getirmiştir.
Öne çıkan isimler
- Kenneth Appel
- Wolfgang Haken
- Vadim Vizing
İlgili konular
Temel eserler
- diestel2017
Sıkça sorulan sorular
- Bir çizgenin kromatik sayısı nedir?
- Bitişik köşelerin her zaman farklı renkler almasını sağlayacak şekilde gereken en küçük renk sayısıdır; örneğin, tek sayılı bir döngünün kromatik sayısı üçtür.
- Dört Renk Teoremi tüm haritalara uygulanır mı?
- Bölgelerin bağlantılı olduğu düzlem veya küre üzerine çizilen haritalara uygulanmaktadır; torus gibi yüzeyler üzerindeki haritalar daha fazla renk gerektirebilmektedir.