Dwudzielność grafu
RNO-Wiki
Zapoznaj się z definicją grafu dwudzielnego na Wikipedii [1].
Sprawdzanie dwudzielności grafu można zrealizować w bardzo prosty sposób. Wystarczy go przejrzeć w głąb lub wszerz odpowiednio kolorując wierzchołki; zakładamy, że dysponujemy tylko dwoma kolorami. Jeśli podczas odwiedzania wierzchołka napotykamy konflikt, tj. jego sąsiad ma taki sam kolor, to przerywamy przeglądanie z odpowiedzią, że dany graf nie jest grafem dwudzielnym.
Implementacja
Implementacja w pseudo języku
int color[]; // tablica kolorów wierzchołków ; // Na początku zakłada się, że wszystkie wierzchołki nie mają żadnego koloru bool dfs(int u, int c) // odwiedź wierzchołek u ; pokoloruj go na kolor c { // pokoloruj wierzchołek u na kolor c // dla wszystkich sąsiadów v wierzchołka u wykonaj: // jeśli v ma kolor c to zwróć FALSE // jeśli v nie ma żadnego koloru, to wykonaj // dfs(v, d) // d - to kolor przeciwny do c // jeśli dfs zwróciło FALSE, to zwróć FALSE // zwróć TRUE }
