Graf Boyama
Bir grafı olabildiğince az renkle boyayın
Bu hesaplayıcı hakkında
Graf Boyama, kromatik sayı χ(G)'yi, yani bir grafın köşelerini hiçbir kenar aynı renkteki iki köşeyi birleştirmeyecek şekilde boyamak için gereken en az renk sayısını bulur ve en uygun boyamalardan birini gösterir. Köşe sayısını ve bir kenar listesini girin; χ'yi dal-sınır aramasıyla kesin olarak hesaplar, en büyük derece Δ'yı ve en büyük klik ω'yı (χ için bir alt sınır) verir, iki parçalı ve tam grafları işaretler ve boyanmış grafı çizer. Zaman çizelgeleme, yazmaç atama, harita boyama ve kromatik sayıları incelemek için kullanışlıdır.
Bir graf nasıl boyanır
- Köşe sayısını girin; köşeler 1'den n'ye kadar numaralandırılır.
- Kenarları 1-2, 2-3 gibi çiftler olarak listeleyin; her bağlantı için bir çift.
- Kromatik sayı χ(G)'yi ve her köşeye atanan rengi okuyun.
- Neden bu kadar renk gerektiğini görmek için χ'yi en büyük klik ω ile karşılaştırın veya keşfetmek için bir ön ayar yükleyin.
Yaygın örnekler
- Bir üçgen (K₃) 3 renk gerektirir; köşelerinin her çifti komşudur.
- Çift uzunluklu devreler iki parçalıdır ve yalnızca 2 renk gerektirir; C₅ gibi tek uzunluklu devreler 3 renk gerektirir.
- Tam graf Kₙ tam olarak n renk gerektirir.
- ω büyüklüğündeki en büyük klik en az ω rengi zorunlu kılar; dolayısıyla χ(G) ≥ ω.
- Grötzsch grafı hiç üçgen içermediği halde 4 renk gerektirir; yani χ klik sayısını aşabilir.
Sıkça sorulan sorular
Kromatik sayı nedir?
Kromatik sayı χ(G), bir grafın köşelerini hiçbir kenar aynı renkteki iki köşeyi birleştirmeyecek şekilde boyamak için gereken en küçük renk sayısıdır.
En az renk sayısı nasıl bulunur?
Graf küçük olduğu için hesaplayıcı kesin arama yapar: önce 1 rengi, sonra 2'yi ve böyle devam ederek dener ve uygun bir boyamanın var olduğu ilk sayıyı döndürür. Bu sayının gerçek en küçük değer olduğu garantidir.
En büyük derece ve en büyük klik nedir?
En büyük derece Δ, herhangi bir köşede birleşen en fazla kenar sayısıdır. En büyük klik ω, hepsi birbirine komşu olan en büyük köşe kümesidir; bu köşelerin hepsi farklı renkte olmak zorunda olduğundan χ(G) en az ω'dır.
Üçgen içermeyen bir graf neden yine de çok renk gerektirebilir?
Büyük bir klik çok sayıda rengi zorunlu kılar, ama tek neden bu değildir. Tek uzunluklu devreler ve Grötzsch grafı gibi graflar hiç üçgen içermeden de ek renk gerektirir; dolayısıyla χ(G) klik sayısından büyük olabilir.
Graf boyutunun bir sınırı var mı?
Evet. Kesin graf boyama hesaplama açısından zor bir problemdir; bu yüzden hesaplayıcı, sonuçları anında ve kesin tutmak için grafı 12 köşeyle sınırlar.