Coloration propre d'un graphe
La coloration d'un graphe est dit propre lorsque deux sommets voisins quelconques n'ont pas la même couleur.
La coloration du graphe ci-dessous est propre.
Coloration
Les sommets sont colorés avec quatre couleurs. Aucun sommet n'a un voisin de la même couleur.
Un graphe est implémenté à l'aide d'un dictionnaire. Un sommet est représenté par son numéro. Les clés du dictionnaire sont les sommets. La valeur associée à une clé s est la liste des voisins du sommet s.
Par exemple, la graphe plus haut est représenté par: {0: [1, 2, 3], 1: [0, 4, 6, 7], 2: [0, 4], ...}.
La coloration du graphe est créée par un autre dictionnaire qui associe à chaque numéro de sommet une chaîne de caractères qui désigne sa couleur.
Par exemple, la coloration du graphe plus haut est représentée par: {0: "jaune", 1: "bleu"", 2: "vert", ...}.
Compléter la fonction coloration_propre qui prend en paramètres un graphe graphe supposé connexe et un dictionnaire couleurs qui stocke les couleurs associées et renvoie True si la coloration du graphe est propre et False sinon.
Exemples
>>> g = {0: [1, 2], 1: [0, 2], 2: [0, 1]}
>>> couleurs = {0:"rouge", 1:"bleu", 2:"vert", 3:"jaune"}
>>> coloration_propre(g, couleurs)
True
>>> g = {0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}
>>> couleurs = {0:"rouge", 1:"rouge", 2:"vert", 3:"jaune"}
>>> coloration_propre(g, couleurs)
False
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)