Vérifier qu'un graphe est biparti — exercice corrigé de NSI (terminale) (chapitre 4)

Vérifier qu'un graphe est biparti

Les graphes · niveau 3 (difficile)

Énoncé

Vérifier qu'un graphe est biparti.

Un graphe est biparti si l'on peut colorier ses sommets en deux couleurs de sorte que toute arête relie deux sommets de couleurs différentes. Écrire une fonction est_biparti(G).

Corrigé

On effectue un BFS en coloriant le sommet de départ en $0$ , puis chaque voisin avec la couleur opposée à la sienne. Si l'on découvre une arête entre deux sommets de même couleur, le graphe n'est pas biparti.


from collections import deque

def est_biparti(G):
    couleur = {}
    for depart in G:
        if depart in couleur:
            continue
        couleur[depart] = 0
        file = deque([depart])
        while file:
            u = file.popleft()
            for v in G[u]:
                if v not in couleur:
                    couleur[v] = 1 - couleur[u]
                    file.append(v)
                elif couleur[v] == couleur[u]:
                    return False
    return True

print(est_biparti({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}))  # True
print(est_biparti({0: [1, 2], 1: [0, 2], 2: [0, 1]}))             # False

La complexité est $O (n + m)$ .