informatique (tronc commun des prépas scientifiques) · Chapitre 13 · Exercice de TD
Le graphe biparti, ou le coloriage en deux couleurs
Parcours de graphes · niveau 2
Énoncé
Écrire une fonction déterminant si un graphe non orienté peut être colorié avec deux couleurs de façon à ce que deux sommets reliés soient toujours de couleurs différentes.
Corrigé
On utilise un BFS pour propager deux couleurs alternées ( et ) le long des branches du graphe :
def est_biparti(G: dict) -> bool:
couleur = {}
for depart in G:
if depart in couleur:
continue
couleur[depart] = 0
file = deque([depart])
while file:
s = file.popleft()
for v in G[s]:
if v not in couleur:
couleur[v] = 1 - couleur[s] # Alternance 0 / 1
file.append(v)
elif couleur[v] == couleur[s]:
return False # Conflit de couleur
return TrueExercices semblables
- Mesurer le piège de la file-liste corrigé
- Sortir du labyrinthe corrigé
- Le graphe est-il un arbre ? corrigé
- L'échelle des mots corrigé
- Les arbres, preuve du théorème corrigé