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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
Linia 19: Linia 19:
  
 
==Zadanie 2==
 
==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.
+
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>. Zaadaptuj algorytm wykrywania mostów grafie do znajdowania wszystkich wierzchołków rozdzielających.
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">

Aktualna wersja na dzień 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 . Zaadaptuj 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.