Sprawdzenie dwudzielności Aby przekonać się, czy dany graf jest dwudzielny, wystarczy użyć algorytmu przeszukiwania grafu (BFS lub DFS) i kolorować wierzchołki (początkowo o kolorze neutralnym) na dwa kolory tak, aby przechodzony wierzchołek miał kolor przeciwny względem poprzednika. Jeśli natrafimy na dwa wierzchołki o tym samym kolorze połączone krawędzią, to graf nie jest dwudzielny. W przeciwnym wypadku graf jest dwudzielny, podział zbioru wierzchołków na rozłączne podzbiory wyznaczają ich kolory.
Zobacz też klasa grafów teoria grafów twierdzenie Bondy’ego-Chvátala twierdzenie Diraca (1952) twierdzenie o liczbie krawędzi twierdzenie Ore (1961)
Przypisy
Linki zewnętrzne [dostęp 2025-10-12]. Graph, bipartite , Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-10-05].
dwudzielny