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.
Les sommets sont colorés avec uniquement deux couleurs. Aucun sommet n'a un voisin de la même couleur.
graph LR
classDef jaune fill:#ff0, color:#38474f;
classDef bleu fill:#0ff, color:#38474f;
n0((0)) --- n1((1))
class n0 jaune
class n1 bleu
n0 --- n2((2))
class n2 bleu
n0 --- n3((3))
class n3 bleu
n1 --- n4((4))
class n4 jaune
n3 --- n5((5))
class n5 jaune
n3 --- n6((6))
class n6 jaune
n3 --- n7((7))
class n7 jaune
n7 --- n1
n4 --- n2
n6 --- n1
n8((8)) --- n5
class n8 bleu
n8 --- n4
Séparation
Le même graphe dessiné avec les sommets regroupés par couleur.
graph TD
%% défintions
n0((0))
n4((4))
n5((5))
n6((6))
n7((7))
n1((1))
n3((3))
n2((2))
n8((8))
%% sous-gaphes
subgraph SG1 [" "]
n0
n4
n6
n7
n5
end
subgraph SG2 [" "]
n2
n1
n3
n8
end
%% arêtes
n1 --- n0
n3 --- n0
n2 --- n0
n1 --- n4
n2 --- n4
n3 --- n5
n3 --- n6
n3 --- n7
n1 --- n6
n8 --- n5
n1 --- n7
n8 --- n4
%% classes
classDef jaune fill:#ff0, color:#38474f;
classDef bleu fill:#0ff, color:#38474f;
classDef jaune-pale fill:#ffff0018, stroke:#ffff00;
classDef bleu-pale fill:#00ffff18, stroke:#00ffff;
class n4 jaune
class n5 jaune
class n6 jaune
class n7 jaune
class n0 jaune
class n2 bleu
class n3 bleu
class n1 bleu
class n8 bleu
class SG1 jaune-pale;
class SG2 bleu-pale;
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)