ASD Ćwiczenia 12: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 48: Linia 48:
  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Zaadoptuj algorytm do wykrywania wierzchołków rozdzielających. Każdą nowo odwiedzaną krawędź <math>u-v</math> odkładaj na stos. Bez straty ogólności przyjmijmy, że <math>u</math> jest przodkiem <math>v</math> w drzewie. Jeśli <math>u-v</math> jest krawędzią drzewową, to odkładamy ją na stos będąc w wierzchołku <math>u</math>, natomiast jeśli jest to krawędź niedrzewowa, to będąc w wierzchołku <math>v</math>. Po wykryciu każdego wierzchołka rozdzielającego <math>v</math> wypisz wszystkie krawędzie ze stosu kończąc na krawędzi drzewowej <math>v-u</math> takiej, że <math>low[u] \ge nr[v] </math>.
+
Zaadaptuj algorytm do wykrywania wierzchołków rozdzielających. Każdą nowo odwiedzaną krawędź <math>u-v</math> odkładaj na stos. Bez straty ogólności przyjmijmy, że <math>u</math> jest przodkiem <math>v</math> w drzewie. Jeśli <math>u-v</math> jest krawędzią drzewową, to odkładamy ją na stos będąc w wierzchołku <math>u</math>, natomiast jeśli jest to krawędź niedrzewowa, to będąc w wierzchołku <math>v</math>. Po wykryciu każdego wierzchołka rozdzielającego <math>v</math> wypisz wszystkie krawędzie ze stosu kończąc na krawędzi drzewowej <math>v-u</math> takiej, że <math>low[u] \ge nr[v] </math>.
 
</div>
 
</div>
 
</div>
 
</div>

Wersja z 10:40, 17 gru 2009

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. Dwuspójną składową grafu G nazywam każdy jego maksymalny (w sensie zawierania) dwuspójny podgraf.


a) Udowodnij, że każda krawędź grafu należy do dokładnie jednej dwuspójnej składowej.


b) Zaprojektuj algorytm, który w czasie liniowym policzy wszystkie dwuspójne składowe danego (przez listy sąsiedztw), spójnego grafu, tzn. podzieli zbiór wszystkich krawędzi na podzbiory odpowiadające poszczególnym dwuspójnym składowym.

Wskazówka

Zadanie 4

Dotychczas rozważaliśmy tylko grafy nieskierowane. Zaproponuj sposób reprezentacji grafu skierowanego za pomocą list sąsiedztw.

Zadanie 5

Powiemy, że graf skierowany jest silnie spójny, jeśli dla każdej pary wierzchołków , istnieją skierowane ścieżki z do i z do . Zaprojektuj algorytm, który w czasie sprawdza, czy dany graf jest grafem silnie spójnym.

Zadanie 6

Zaproponuj algorytm, który w czasie liniowym zorientuje krawędzie grafu dwuspójnego w taki sposób, żeby otrzymany graf był silnie spójny.