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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 1: Linia 1:
 
==Zadanie 1==
 
==Zadanie 1==
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:
  
  
Linia 59: Linia 59:
  
 
==Zadanie 6==
 
==Zadanie 6==
Zaproponuje algorytm, który w czasie liniowym zorientuje krawędzie grafu dwuspójnego w taki sposób, żeby otrzymany graf był silnie spójny.
+
Zaproponuj algorytm, który w czasie liniowym zorientuje krawędzie grafu dwuspójnego w taki sposób, żeby otrzymany graf był silnie spójny.

Wersja z 21:26, 3 gru 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. 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.