Zrozumienie dwupodziałów w teorii grafów

W teorii grafów dwupodział grafu to podział jego zbioru wierzchołków na dwa rozłączne zbiory (zwane zbiorami cząstkowymi) w taki sposób, że wszystkie krawędzie łączą wierzchołki z różnych zbiorów cząstkowych. Innymi słowy, nie ma krawędzi pomiędzy wierzchołkami tego samego zbioru cząstkowego.

Na przykład rozważmy graf z 4 wierzchołkami {a,b,c,d} i podzielimy zbiór wierzchołków na dwie części: {a,b} i {płyta CD}. Graf jest dwudzielny, ponieważ wszystkie krawędzie łączą wierzchołki różnych części.

Dwudzielnego podziału można użyć w celu zmniejszenia złożoności algorytmów rozwiązywania problemów grafowych, takich jak przechodzenie przez graf, znajdowanie najkrótszej ścieżki i dopasowywanie grafów.