Un graphe est dit biparti si on peut colorer ses sommets avec uniquement deux couleurs de telle manière que deux sommets voisins quelconques n'ont pas la même couleur.
Le graphe ci-dessous est biparti.
Coloration
Les sommets sont colorés avec uniquement deux couleurs. Aucun sommet n'a un voisin de la même couleur.
Séparation
Le même graphe dessiné avec les sommets regroupés par couleur.
Cette observation illustre une autre définition des graphes bipartis :
« On considère un graphe connexe non orienté \(G(S, A)\). \(S\) est l'ensemble des sommets, \(A\) l'ensemble des arêtes.
Ce graphe est dit biparti si l'ensemble \(S\) peut être divisé en deux sous-ensembles disjoints \(S_1\) et \(S_2\) tels que chaque arête de \(A\) a une extrémité dans \(S_1\) et l'autre extrémité dans \(S_2\). »
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, le graphe plus haut est représenté par: {0:[1,2,3],1:[0,4,6,7],2:[0,4],...}.
Compléter la fonction est_biparti qui prend en paramètres un graphe graphe supposé connexe et un sommet sommet_initial à partir duquel le parcours est effectué et renvoie True si le graphe est biparti et False sinon. Un tableau couleurs servira à stocker à chaque indice i la couleur du sommet numéro i (voir plus bas).
Algorithme
On utilise une file et un parcours en largeur.
On affecte au premier sommet la couleur \(1\), puis à ses voisins la couleur \(-1\). On parcourt ensuite les voisins des voisins qui n'ont pas déjà été colorés en leur affectant la couleur \(1\), et ainsi de suite.
Si, lorsqu'on explore les voisins d'un sommet s, on en rencontre un qui est déjà coloré, soit sa couleur est différente de celle de s et on ne fait rien, soit sa couleur est identique à celle de s et alors le graphe n'est pas biparti.
Les sommets sont visités dans un parcours en largeur implémenté à l'aide d'une file.
Colorer le sommet initial et le placer dans la file
Tant que le file n'est pas vide :
Défiler un sommet
Visiter chacun de ses voisins :
Si un voisin n'est pas coloré, lui donner une couleur et le placer dans la file
Sinon, contrôler sa couleur et renvoyer éventuellement False
Renvoyer True si le parcours est terminé
Aide: utilisation de deque pour implémenter une file
On crée une file vide avec l'instruction file = deque(). Pour insérer un élément elt dans la file, on écrit file.append(elt).
Pour défiler un élément et l'affecter, on écrit elt = file.popleft(). La fonction len renvoie la longueur de la file.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)