Coloration du graphique
La coloration d'un graphique peut être décrite comme un processus d'attribution de couleurs aux sommets d'un graphique. En cela, la même couleur ne doit pas être utilisée pour remplir les deux sommets adjacents. Nous pouvons également appeler la coloration des graphiques sous le nom de Vertex Coloring. Dans la coloration de graphes, nous devons veiller à ce qu’un graphe ne contienne aucune arête dont les sommets d’extrémité sont colorés de la même couleur. Ce type de graphique est connu sous le nom de graphique correctement coloré.
Exemple de coloration de graphique
sauf
Dans ce graphique, nous montrons le graphique correctement coloré, qui est décrit comme suit :
Le graphique ci-dessus contient quelques points, décrits comme suit :
- La même couleur ne peut pas être utilisée pour colorer les deux sommets adjacents.
- Par conséquent, nous pouvons l’appeler un graphique correctement coloré.
Applications de la coloration graphique
Il existe diverses applications de la coloration graphique. Certaines de leurs applications importantes sont décrites comme suit :
- Affectation
- Coloriage de la carte
- Planification des tâches
- Sudoku
- Préparer l'horaire
- Résolution de conflit
Nombre chromatique
Le nombre chromatique peut être décrit comme le nombre minimum de couleurs requis pour colorer correctement n’importe quel graphique. En d’autres termes, le nombre chromatique peut être décrit comme un nombre minimum de couleurs nécessaires pour colorer n’importe quel graphique de telle sorte qu’aucun sommet adjacent d’un graphique ne se voie attribuer la même couleur.
Exemple de nombre chromatique :
Pour comprendre le nombre chromatique, nous considérerons un graphique décrit comme suit :
Le graphique ci-dessus contient quelques points, décrits comme suit :
- La même couleur n’est pas utilisée pour colorer les deux sommets adjacents.
- Le nombre minimum de couleurs de ce graphique est de 3, ce qui est nécessaire pour colorer correctement les sommets.
- Ainsi, dans ce graphique, le nombre chromatique = 3
- Si nous voulons colorer correctement ce graphique, dans ce cas, il nous faut au moins 3 couleurs.
Types de nombres chromatiques de graphiques :
Il existe différents types de graphiques de nombres chromatiques, décrits comme suit :
Graphique cyclique :
Un graphe sera appelé graphe cyclique s'il contient « n » arêtes et « n » sommets (n >= 3), qui forment un cycle de longueur « n ». Il ne peut y avoir que 2 ou 3 degrés pour tous les sommets du graphe cyclique.
Nombre chromatique :
- Le nombre chromatique dans un graphe cyclique sera 2 si le nombre de sommets dans ce graphe est pair.
- Le nombre chromatique dans un graphe cyclique sera 3 si le nombre de sommets dans ce graphe est impair.
Exemples de graphique de cycle :
Il existe divers exemples de graphiques cycliques. Certains d’entre eux sont décrits comme suit :
Exemple 1: Dans le graphique suivant, nous devons déterminer le nombre chromatique.
Solution: Dans le graphique cyclique ci-dessus, il existe 3 couleurs différentes pour trois sommets, et aucun des sommets adjacents n'est coloré de la même couleur. Dans ce graphique, le nombre de sommets est impair. Donc
Nombre chromatique = 3
Exemple 2 : Dans le graphique suivant, nous devons déterminer le nombre chromatique.
Solution: Dans le graphique cyclique ci-dessus, il y a 2 couleurs pour quatre sommets, et aucun des sommets adjacents n'est coloré avec la même couleur. Dans ce graphe, le nombre de sommets est pair. Donc
Nombre chromatique = 2
Exemple 3 : Dans le graphique suivant, nous devons déterminer le nombre chromatique.
Solution: Dans le graphique ci-dessus, il y a 4 couleurs différentes pour cinq sommets, et deux sommets adjacents sont colorés de la même couleur (bleu). Ce graphique n’est donc pas un graphique cyclique et ne contient pas de nombre chromatique.
Exemple 4 : Dans le graphique suivant, nous devons déterminer le nombre chromatique.
Solution: Dans le graphique ci-dessus, il existe 2 couleurs différentes pour six sommets, et aucun des sommets adjacents n'est coloré de la même couleur. Dans ce graphe, le nombre de sommets est pair. Donc
Nombre chromatique = 2
Graphique du planificateur
Un graphique sera appelé graphique de planificateur s’il est dessiné dans un plan. Les bords du graphique du planificateur ne doivent pas se croiser.
Nombre chromatique :
- Dans un graphique de planificateur, le Nombre chromatique doit être inférieur ou égal à 4.
- Le graphique du planificateur peut également être représenté par tous les graphiques cycliques ci-dessus, à l'exception de l'exemple 3.
Exemples de graphiques Planer :
Il existe divers exemples de graphiques planeurs. Certains d’entre eux sont décrits comme suit :
Exemple 1: Dans le graphique suivant, nous devons déterminer le nombre chromatique.
Solution: Dans le graphique ci-dessus, il y a 3 couleurs différentes pour trois sommets, et aucune des arêtes de ce graphique ne se croise. Donc
Gimp enregistrer au format JPEG
Nombre chromatique = 3
Ici, le nombre chromatique est inférieur à 4, ce graphique est donc un graphique plan.
Exemple 2 : Dans le graphique suivant, nous devons déterminer le nombre chromatique.
Solution: Dans le graphique ci-dessus, il y a 2 couleurs différentes pour quatre sommets, et aucune des arêtes de ce graphique ne se croise. Donc
Nombre chromatique = 2
Ici, le nombre chromatique est inférieur à 4, ce graphique est donc un graphique plan.
Exemple 3 : Dans le graphique suivant, nous devons déterminer le nombre chromatique.
Solution: Dans le graphique ci-dessus, il y a 5 couleurs différentes pour cinq sommets, et aucune des arêtes de ce graphique ne se croise. Donc
Nombre chromatique = 5
Ici, le nombre chromatique est supérieur à 4, ce graphique n’est donc pas un graphique plan.
Exemple 4 : Dans le graphique suivant, nous devons déterminer le nombre chromatique.
Solution: Dans le graphique ci-dessus, il y a 2 couleurs différentes pour six sommets, et aucune des arêtes de ce graphique ne se croise. Donc
Nombre chromatique = 2
Ici, le nombre chromatique est inférieur à 4, ce graphique est donc un graphique plan.
Graphique complet
Un graphe sera appelé graphe complet si une seule arête est utilisée pour joindre tous les deux sommets distincts. Chaque sommet d'un graphe complet est connecté à tous les autres sommets. Dans ce graphique, chaque sommet sera coloré avec une couleur différente. Cela signifie que dans le graphe complet, deux sommets ne contiennent pas la même couleur.
Nombre chromatique
Dans un graphe complet, le nombre chromatique sera égal au nombre de sommets de ce graphe.
Exemples de graphique complet :
Il existe différents exemples de graphiques complets. Certains d’entre eux sont décrits comme suit :
Exemple 1: Dans le graphique suivant, nous devons déterminer le nombre chromatique.
Solution: Il existe 4 couleurs différentes pour 4 sommets différents, et aucune des couleurs n'est la même dans le graphique ci-dessus. Selon la définition, un nombre chromatique est le nombre de sommets. Donc,
circuit additionneur complet
Nombre chromatique = 4
Exemple 2 : Dans le graphique suivant, nous devons déterminer le nombre chromatique.
Solution: Il existe 5 couleurs différentes pour 5 sommets différents, et aucune des couleurs n'est la même dans le graphique ci-dessus. Selon la définition, un nombre chromatique est le nombre de sommets. Donc,
Nombre chromatique = 5
Exemple 3 : Dans le graphique suivant, nous devons déterminer le nombre chromatique.
Solution: Il existe 3 couleurs différentes pour 4 sommets différents, et une couleur est répétée sur deux sommets dans le graphique ci-dessus. Ce graphique n’est donc pas un graphique complet et ne contient pas de nombre chromatique.
Graphique biparti
Un graphe sera appelé graphe biparti s’il contient deux ensembles de sommets, A et B. Le sommet de A ne peut se joindre qu’aux sommets de B. Cela signifie que les arêtes ne peuvent pas joindre les sommets avec un ensemble.
Nombre chromatique
Dans tout graphe biparti, le nombre chromatique est toujours égal à 2.
Exemples de graphe biparti :
Il existe divers exemples de graphes bipartis. Certains d’entre eux sont décrits comme suit :
Exemple 1: Dans le graphique suivant, nous devons déterminer le nombre chromatique.
Solution: Il y a 2 ensembles de sommets différents dans le graphique ci-dessus. Donc le nombre chromatique de tous les graphes bipartis sera toujours 2. Donc
Nombre chromatique = 2
Arbre:
Un graphe connecté sera appelé arbre s’il n’y a aucun circuit dans ce graphe. Dans un arbre, le nombre chromatique sera égal à 2 quel que soit le nombre de sommets de l’arbre. Tout graphe biparti est aussi un arbre.
Nombre chromatique
Dans tout arbre, le nombre chromatique est égal à 2.
js remplacement
Exemples d'arbre :
Il existe différents exemples d'arbre. Certains d’entre eux sont décrits comme suit :
Exemple 1: Dans l’arbre suivant, nous devons déterminer le nombre chromatique.
Solution: Il existe 2 couleurs différentes pour quatre sommets. Un arbre avec un nombre quelconque de sommets doit contenir le nombre chromatique égal à 2 dans l'arbre ci-dessus. Donc,
Nombre chromatique = 2
Exemple 2 : Dans l’arbre suivant, nous devons déterminer le nombre chromatique.
Solution: Il existe 2 couleurs différentes pour cinq sommets. Un arbre avec un nombre quelconque de sommets doit contenir le nombre chromatique égal à 2 dans l'arbre ci-dessus. Donc,
Nombre chromatique = 2
Exemple concret de nombre chromatique
Supposons que Marry soit manager dans la société Xyz. L'entreprise embauche de nouveaux employés et elle doit établir un programme de formation pour ces nouveaux employés. Elle doit planifier les trois réunions et elle essaie d'utiliser au maximum les quelques plages horaires pour les réunions. Si un employé doit assister à deux réunions différentes, le responsable doit alors utiliser des horaires différents pour ces réunions. Supposons que nous souhaitions obtenir une représentation visuelle de cette réunion.
Pour la représentation visuelle, Marry utilise le point pour indiquer la rencontre. S'il y a un employé qui a deux réunions et qui souhaite rejoindre les deux réunions, alors les deux réunions seront connectées à l'aide d'un Edge. Les différentes plages horaires sont représentées à l'aide de couleurs. Le gestionnaire remplit donc les points avec ces couleurs de telle sorte que deux points ne contiennent pas la même couleur partageant un bord. (Cela signifie qu'un employé qui doit assister aux deux réunions ne doit pas avoir le même créneau horaire). La représentation visuelle de ceci est décrite comme suit :
