Graphe bipartite
Graphe bipartite - un graphe dont les sommets peuvent être divisés en deux ensembles de sorte que chaque arête relie le sommets de différents ensembles.
Souvent, dans le contexte des graphes bipartis, le concept de couleurs sommets est utilisé. Diviser un graphe en deux parties s'appelle colorer ses sommets avec deux couleurs différentes. Chaque arête doit relier des sommets d'une couleur différente.
DFS.
Algorithme
Nous commençons à peindre à partir d'un sommet arbitraire, que nous peignons dans une couleur arbitraire.
En passant le long de chaque arête, peignez le sommet suivant dans la couleur opposée.
Si, en itérant sur des sommets voisins, nous trouvons un sommet qui est déjà peint de la même couleur que le sommet actuel, alors il y a un cycle impair dans le graphe, ce qui signifie qu'il n'est pas bipartite.