Théorie des graphes - Coloration

La coloration du graphe n'est rien d'autre qu'un moyen simple d'étiqueter les composants du graphe tels que les sommets, les arêtes et les régions sous certaines contraintes. Dans un graphique, deux sommets adjacents, arêtes adjacentes ou régions adjacentes ne sont pas colorés avec un nombre minimum de couleurs. Ce numéro s'appelle lechromatic number et le graphique s'appelle un properly colored graph.

Pendant la coloration du graphe, les contraintes qui sont définies sur le graphe sont les couleurs, l'ordre de coloration, la manière d'attribuer la couleur, etc. Une coloration est donnée à un sommet ou à une région particulière. Ainsi, les sommets ou régions ayant les mêmes couleurs forment des ensembles indépendants.

Coloration des sommets

La coloration des sommets est une affectation de couleurs aux sommets d'un graphe «G» de telle sorte qu'aucun sommet adjacent n'a la même couleur. En termes simples, deux sommets d'une arête ne doivent pas être de la même couleur.

Numéro chromatique

Le nombre minimum de couleurs requis pour la coloration des sommets du graphe «G» est appelé le nombre chromatique de G, noté X (G).

χ (G) = 1 si et seulement si 'G' est un graphe nul. Si 'G' n'est pas un graphe nul, alors χ (G) ≥ 2.

Example

Note - Un graphe 'G' est dit n-recouvrable s'il existe une coloration de sommet qui utilise au plus n couleurs, c'est-à-dire X (G) ≤ n.

Coloration de la région

La coloration de région est une attribution de couleurs aux régions d'un graphique plan de telle sorte qu'aucune région adjacente n'ait la même couleur. On dit que deux régions sont adjacentes si elles ont un bord commun.

Example

Jetez un œil au graphique suivant. Les régions «aeb» et «befc» sont adjacentes, car il existe un bord commun «be» entre ces deux régions.

De même, les autres régions sont également colorées en fonction de la contiguïté. Ce graphique est coloré comme suit -

Example

Le nombre chromatique de Kn est

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

Considérez cet exemple avec K ₄ .

Dans le graphe complet, chaque sommet est adjacent aux (n - 1) sommets restants. Par conséquent, chaque sommet nécessite une nouvelle couleur. D'où le nombre chromatique de K _n = n.

Applications de la coloration de graphes

La coloration des graphes est l'un des concepts les plus importants de la théorie des graphes. Il est utilisé dans de nombreuses applications en temps réel de l'informatique telles que -

• Clustering
• Exploration de données
• Capture d'image
• Segmentation d'image
• Networking
• Allocation des ressources
• Planification des processus