Le graphe biparti, ou le coloriage en deux couleurs

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 13 — Parcours de graphes

É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 ( $0$ et $1$ ) 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 True

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.