ASD Ćwiczenia 12: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 2: | Linia 2: | ||
Pokaż, w jaki sposób sprawdzić w czasie liniowym, czy graf jest grafem dwudzielnym | Pokaż, w jaki sposób sprawdzić w czasie liniowym, czy graf jest grafem dwudzielnym | ||
a) z pomocą przeszukiwania wszerz, | a) z pomocą przeszukiwania wszerz, | ||
| Linia 8: | Linia 8: | ||
b) z wykorzystaniem przeszukiwania w głąb. | b) z wykorzystaniem przeszukiwania w głąb. | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | |||
Wskazówka | Wskazówka | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
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. | 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. | ||
<div | </div> | ||
</div> | </div> | ||
Wersja z 14:53, 28 wrz 2006
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
