Numărul cromatic de vârfuri

Această intrare pe tema geometriei este doar o schiță . Contribuiți la îmbunătățirea acestuia în conformitate cu convențiile Wikipedia . Urmați sfaturile de proiectare de referință .

Având în vedere un grafic G și un set C de culori, numărul cromatic al lui G este numărul minim de culori necesar pentru a colora vârfurile lui G astfel încât, luând oricum două vârfuri adiacente în G , să aibă culori diferite.

Prin colorarea vârfurilor înțelegem o funcție f : V ( G ) → C care atribuie fiecărui vârf al lui G o singură culoare conform regulii menționate anterior.

Numărul cromatic al lui G este indicat de litera greacă χ ( G ) (chi).

Exemplu

Reprezentăm un grafic cu numărul cromatic 2 ( grafic bipartit ):

Definiți partiția P = { A = { v ₁ , v ₂ , v ₃ , v ₄ , v ₅ }, B = { u ₁ , u ₂ , u ₃ , u ₄ }}.

Vârfurile părții A pot fi colorate de aceeași culoare ca: pentru fiecare x , y aparținând lui A , cu x ≠ y , arcul { x , y } nu aparține lui G ; și, de asemenea, pentru partea B : pentru fiecare x , y aparținând lui B , cu x ≠ y , arcul { x , y } nu aparține lui G.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică