Топ-100
Indietro

ⓘ Numero cromatico dei vertici. Dato un grafo G e un insieme C di colori, il numero cromatico di G è il minimo numero di colori necessari a colorare i vertici di ..




                                     

ⓘ Numero cromatico dei vertici

Dato un grafo G e un insieme C di colori, il numero cromatico di G è il minimo numero di colori necessari a colorare i vertici di G in modo che, presi comunque due vertici adiacenti in G, essi abbiano diverso colore.

Per colorazione dei vertici si intende una funzione f: V G → C che assegna ad ogni vertice di G uno e un solo colore secondo la regola citata precedentemente.

Il numero cromatico di G si indica con la lettera greca χG chi.

                                     

1. Esempio

Rappresentiamo un grafo di numero cromatico 2 grafo bipartito:

Definiamo la partizione P = { A ={ v 1, v 2, v 3, v 4, v 5 }, B={ u 1, u 2, u 3, u 4 } }.

I vertici della parte A possono essere colorati dello stesso colore in quanto: per ogni x, y appartenenti ad A, con x ≠ y, larco { x, y } non appartiene a G ; e anche per la parte B: per ogni x, y appartenenti a B, con x ≠ y, larco { x, y } non appartiene a G.