Teoria dei grafi - Colorazione

La colorazione del grafico non è altro che un modo semplice per etichettare i componenti del grafico come vertici, bordi e regioni sotto alcuni vincoli. In un grafico, non esistono due vertici adiacenti, bordi adiacenti o regioni adiacenti colorati con un numero minimo di colori. Questo numero è chiamatochromatic number e il grafico si chiama a properly colored graph.

Durante la colorazione del grafico, i vincoli impostati sul grafico sono i colori, l'ordine di colorazione, il modo di assegnare il colore, ecc. Viene data una colorazione a un vertice oa una particolare regione. Pertanto, i vertici o le regioni aventi gli stessi colori formano insiemi indipendenti.

Colorazione dei vertici

La colorazione dei vertici è un'assegnazione di colori ai vertici di un grafo 'G' in modo tale che non ci siano due vertici adiacenti dello stesso colore. In poche parole, non esistono due vertici di un bordo dello stesso colore.

Numero cromatico

Il numero minimo di colori richiesto per la colorazione dei vertici del grafo "G" è chiamato come numero cromatico di G, indicato con X (G).

χ (G) = 1 se e solo se 'G' è un grafo nullo. Se 'G' non è un grafo nullo, allora χ (G) ≥ 2.

Example

Note - Un grafo 'G' si dice copribile con n se c'è una colorazione dei vertici che usa al massimo n colori, cioè X (G) ≤ n.

Colorazione della regione

La colorazione delle regioni è un'assegnazione di colori alle regioni di un grafico planare in modo tale che due regioni adiacenti non abbiano lo stesso colore. Si dice che due regioni siano adiacenti se hanno un bordo comune.

Example

Dai un'occhiata al grafico seguente. Le regioni "aeb" e "befc" sono adiacenti, poiché esiste un confine comune "be" tra queste due regioni.

Allo stesso modo, anche le altre regioni sono colorate in base all'adiacenza. Questo grafico è colorato come segue:

Example

Il numero cromatico di Kn è

• n
• n–1
• [n/2]
• [n/2]

Considera questo esempio con K ₄ .

Nel grafo completo, ogni vertice è adiacente ai rimanenti (n - 1) vertici. Quindi, ogni vertice richiede un nuovo colore. Da qui il numero cromatico di K _n = n.

Applicazioni della colorazione dei grafi

La colorazione dei grafi è uno dei concetti più importanti nella teoria dei grafi. Viene utilizzato in molte applicazioni in tempo reale dell'informatica come:

• Clustering
• Estrazione dei dati
• Acquisizione di immagini
• Segmentazione delle immagini
• Networking
• Assegnazione delle risorse
• Pianificazione dei processi