Chromatic İLE Clique İLE Independence ile Graf İnvaryantları
Matematik
Normal
Özet
Grafların karakteristik sayıları.
Ayrıntılı Açıklama
Graf parametreleri:
- Chromatic: Minimum renk sayısı χ(G)
- Clique: Maksimum tam alt graf ω(G)
- Independence: Maksimum bağımsız küme α(G)
χ(G) ≥ ω(G) her zaman geçerlidir.
- Chromatic: Minimum renk sayısı χ(G)
- Clique: Maksimum tam alt graf ω(G)
- Independence: Maksimum bağımsız küme α(G)
χ(G) ≥ ω(G) her zaman geçerlidir.
Formül
χ(G) ≥ n/α(G)