Grafico bipartito
Grafico bipartito - un grafico i cui vertici possono essere divisi in due insiemi in modo che ciascun bordo colleghi il vertici da insiemi diversi.
Spesso nel contesto dei grafici bipartiti, viene utilizzato il concetto di colori vertici. Dividere un grafico in due parti si chiama colorare i suoi vertici con due colori diversi. Ogni bordo deve collegare i vertici di un colore diverso.
DFS
.
Algoritmo
Iniziamo a dipingere da un vertice arbitrario, che dipingiamo con un colore arbitrario.
Quando passi lungo ogni bordo, dipingi il vertice successivo con il colore opposto.
Se, durante l'iterazione sui vertici vicini, troviamo un vertice che è già dipinto dello stesso colore di quello attuale, allora c'è un ciclo dispari nel grafico, il che significa che non è bipartito.