INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire. Q036 — Donner un algorithme O(V+E) pour déterminer si un graphe non orienté est biparti, avec justification.
Merci pour cette question classique d’algorithmique des graphes. Voici l’algorithme demandé, sa justification et une évaluation de confiance.
Algorithme : parcours en largeur avec coloration
L’idée est de colorer les sommets en deux couleurs, disons 0 et 1, de sorte que deux sommets adjacents aient toujours des couleurs différentes. Un graphe est biparti si et seulement si une telle coloration est possible.
Fonction EstBiparti(G = (V, E)) :
couleur[v] = -1 pour tout v dans V, où -1 signifie non coloré
Pour chaque sommet s dans V :
Si couleur[s] == -1 :
couleur[s] = 0
File F = {s}
Tant que F n'est pas vide :
u = défile(F)
Pour chaque voisin v de u :
Si couleur[v] == -1 :
couleur[v] = 1 - couleur[u]
enfile(F, v)
Sinon si couleur[v] == couleur[u] :
retourner FAUX
retourner VRAI
Justification
Complexité. Chaque sommet est traité au plus une fois, puisqu’il est coloré une seule fois et défilé une seule fois. Chaque arête est examinée au plus deux fois, une fois depuis chacune de ses extrémités. Le coût total est donc en O(V + E), ce qui est linéaire.
Correction. Deux arguments sont nécessaires.
D’abord, si l’algorithme retourne FAUX, c’est qu’il a rencontré une arête (u, v) avec couleur[u] = couleur[v]. Or l’invariant de l’algorithme est que toute arête relie deux sommets de couleurs différentes : en effet, un sommet v reçoit la couleur 1 - couleur[u] au moment où il est découvert depuis u, et cette couleur ne change plus jamais. Une arête reliant deux sommets de même couleur contredit donc la définition d’un graphe biparti, qui exige une partition des sommets en deux classes indépendantes. Le graphe n’est pas biparti.
Ensuite, si l’algorithme retourne VRAI, alors la coloration produite vérifie que toute arête relie deux couleurs différentes. La classe des sommets de couleur 0 et celle des sommets de couleur 1 forment alors deux ensembles indépendants, sans arête interne, donc une bipartition valide. Le graphe est biparti.
Complétude. Le parcours en largeur depuis chaque sommet non encore coloré garantit que toutes les composantes connexes sont traitées, y compris les sommets isolés, qui sont trivialement bipartis. Aucun sommet n’est oublié.
Remarque sur le choix du parcours
Le parcours en largeur n’est pas indispensable : un parcours en profondeur avec la même logique de coloration fonctionnerait tout aussi bien et resterait en O(V + E). Le BFS est simplement un choix naturel et simple à implémenter.
Confiance
Je suis très confiant dans cet algorithme et sa justification : il s’agit d’un résultat standard, vérifiable par la logique de coloration exposée ci-dessus. Ma confiance est de 97 %, la marge restante tenant au fait que je récite de mémoire une procédure classique plutôt qu’une démonstration formelle exécutée pas à pas ici.
N’hésitez pas si vous souhaitez que je détaille un exemple d’exécution ou que je traite un cas particulier, comme un graphe contenant un cycle impair.Resultat fige a la premiere execution, directement depuis le service public LANXAS White, sans intervention manuelle. Cette page est permanente et peut etre re-consultee pour verification.