ASD Ćwiczenia 12

Zadanie 1

Pokaż, w jaki sposób sprawdzić w czasie liniowym, czy graf jest grafem dwudzielnym

a) z pomocą przeszukiwania wszerz,

b) z wykorzystaniem przeszukiwania w głąb.

Wskazówka

Skorzystaj z faktu, że graf jest grafem dwudzielnym wtedy i tylko wtedy, gdy nie zawiera żadnego cyklu o długości nieparzystej. Przeanalizuj te miejsca w obu algorytmach, w których wykrywany jest cykl.