ASD Ćwiczenia 12: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 4: | Linia 4: | ||
a) | a) za pomocą przeszukiwania wszerz, | ||
b) z wykorzystaniem przeszukiwania w głąb. | b) z wykorzystaniem przeszukiwania w głąb. | ||
| Linia 17: | Linia 17: | ||
</div> | </div> | ||
</div> | </div> | ||
==Zadanie 2== | |||
Niech <math>G=(V,E)</math> będzie grafem spójnym. '''Wierzchołkiem rozdzielającym''' w grafie <math>G</math> nazywamy każdy wierzchołek, którego usunięcie rozspójnia <math>G</math>. Zaadoptuj algorytm wykrywania mostów grafie do znajdowania wszystkich wierzchołków rozdzielających. | |||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | |||
Wskazówka | |||
<div class="mw-collapsible-content" style="display:none"> | |||
Udowodnij następujące twierdzenie. | |||
---- | |||
Niech <math>T</math> będzie drzewem przeszukiwania w głąb grafu <math>G</math>. Wierzchołek <math>v</math> jest wierzchołkiem rozdzielającym w grafie <math>G</math> wtedy i tylko wtedy, gdy <math>v</math> jest korzeniem <math>T</math> i ma w <math>T</math> dwóch synów lub <math>v</math> nie jest korzeniem, ale posiada syna <math>u</math> takiego, że <math>nr[v] \le low[u]</math>. | |||
</div> | |||
</div> | |||
==Zadanie 3== | |||
Graf spójny bez wierzchołków rozdzielających nazywamy '''grafem dwuspójnym'''. | |||
Wersja z 10:03, 29 wrz 2006
Zadanie 1
Pokaż, w jaki sposób sprawdzić w czasie liniowym, czy graf jest grafem dwudzielnym
a) za pomocą przeszukiwania wszerz,
b) z wykorzystaniem przeszukiwania w głąb.
Wskazówka
Zadanie 2
Niech będzie grafem spójnym. Wierzchołkiem rozdzielającym w grafie nazywamy każdy wierzchołek, którego usunięcie rozspójnia . Zaadoptuj algorytm wykrywania mostów grafie do znajdowania wszystkich wierzchołków rozdzielających.
Wskazówka
Zadanie 3
Graf spójny bez wierzchołków rozdzielających nazywamy grafem dwuspójnym.
