Treść zadania

W macierzy dane są szacowane czasy transmisji między komputerami w sieci. Czasy transmisji w obu kierunkach są takie same. Zerowy czas t_ij oznacza brak bezpośredniego połączenia między komputerem i a j. Dla podanej sieci połączeń należy odpowiedzieć czy istnieje możliwość uzyskania połączenia między dowolną parą komputerów (być może pośrednio). Jeśli istnieje, to należy określić czas trwania transmisji między każdą parą komputerów, oraz zidentyfikować komputery, których awaria spowoduje utratę spójności sieci.

Podstawowe definicje grafów.

Przykładowa graficzna reprezentacja grafu:

Grafem G nazywamy parę (V, K), gdzie:

V - oznacza zbiór węzłów lub inaczej nazywanych wierzchołkami, natomiast

K - to zbiór (x, y) należący do V² reprezentuje zbiór krawędzi,

Widząc graf ( powyższy rysunek ) możemy zauważyć, że wierzchołki są połączone ze sobą krawędziami, a gdy nadamy im kierunki ( strzałki na rysunku) mówimy o grafie skierowanym.

Przyjrzyjmy się dwóm węzłom x i y (wierzchołki) połączonych krawędzią - węzeł x jest węzłem początkowym, a węzeł y końcowym.

Graf z mojego rysunku ma następujące cechy:

(A,B), (A,C), (A,D), (B, C), (B,D), (B,E), (C,F),(D,F),(E,D).

Krawędziom grafu można przypisać pewne wagi ( czas transferu danych pomiędzy komputerami) - wówczas zmienia się definicja grafu:

graf G =(V, K, W), gdzie

W - oznacza zbiór wartości odpowiadających danym krawędziom, a najkrótszą ścieżkę z wierzchołka a do wierzchołka z wyznacza ścieżka o minimalnej wadze, której koszt (czas transferu) jest minimalny.

Sposoby reprezentacji grafów.

Istnieją cztery standardowe sposoby reprezentowania grafu G=(V, K), za pomocą:

Najczęściej wykorzystuje się listy sąsiedztwa lub macierze sąsiedztwa.

W reprezentacji grafu G = ( V,K ) za pomocą listy sąsiedztwa dana jest tablica T zawierająca |V| list, po jednej dla każdego wierzchołka z V. Dla każdego wierzchołka u należącego do zbioru V elementami listy sąsiedztwa T[u] są wszystkie wierzchołki v takie, że krawędź ( u,v ) należy do K; tzn. T[u] składa się ze wszystkich wierzchołków sąsiadujących z u w grafie G.

Zazwyczaj porządek wierzchołków na każdej liście sąsiedztwa jest dowolny.

Przykład dla rysunku: (dla grafu nieskierowanego )

A: -> B -> C -> D -> NIL

B: -> A -> C -> D -> E -> NIL

C: -> A -> B -> F -> NIL

D: -> A -> B -> E -> F -> NIL

E: -> B -> D -> NIL

F: -> C -> D -> NIL

Jeśli graf posiada wagi na krawędziach to mogą one zostać zapamiętane wraz z każdym wierzchołkiem v na liście sąsiedztwa u.

W liście krawędzi graf G = ( V,K ) jest reprezentowany przez listę wszystkich krawędzi występujących w grafie w postaci: < węzeł początkowy, węzeł końcowy, [waga krawędzi] [OPCJONALNIE ] >.

Przykład dla rysunku:

< A , B >

< A , C >

< A , D >

< B , C >

< B , D >

< B , E >

< C , F >

< D , F >

< E , D >

W reprezentacji grafu G = ( V,K ) za pomocą macierzy sąsiedztwa zakładamy, że wierzchołki są ponumerowane 1,2, ..., |V| w dowolny sposób. Reprezentacja macierzowa grafu G składa się wtedy z macierzy T = (a_ij) wymiaru |V| x |V| takiej, że

a_ij = 1 jeśli (i,j) należy do K,

a_ij = 0 w przeciwnym przypadku,

Przykład dla rysunku:

W przypadku, gdy na krawędziach grafu występują wagi to na przecięciu kolumny v i wiersza u znajdzie się zamiast 1 odpowiednia wartość wagi(czasu transferu danych miedzy komputerem v a u.

Reprezentacja grafu za pomocą macierzy incydencji różni się tym, że w kolumnach macierzy występują krawędzie (takie jak w liście krawędzi, kolumn jest tyle ile jest krawędzi).

Natomiast 1 w macierzy oznacza incydentność danego wierzchołka z krawędzią.

Przykład dla rysunku:

Podobnie jak dla macierzy wierzchołków i tu mogą występować wagi na przecięciu wierzchołka u i krawędzi (v,u) lub (u,w).

Punkt artykulacji.

Wierzchołek a grafu niezorietowanego G=<V,A> nazywamy punktem artykulacji, jeżeli usunięcie tego wierzchołka i wszystkich incydentnych z nim krawędzi powoduje zwiększenie składowych spójnych grafu. Równoważnie możemy powiedzieć, że a jest punktem artykulacji, jeżeli istnieją wierzchołki u,v różne od a takie, że droga z u do v - a zakładamy , że istnieje co najmniej jedna taka droga - przechodzi przez wierzchołek a. Graf niezorientowany nazywamy dwuspójnym , jeśli jest on spójny i nie zawiera punktów artykulacji. W tym ćwiczeniu punktem artykulacji będzie ten komputer w sieci, którego awaria spowoduje awarię całej sieci. Punktów artykulacji w takiej sieci może być wiele.

Tabele i wykresy:

- wyszukiwanie najkrótszej ścieżki

- wyszukiwanie punktów artykulacji

Wnioski:

Zajętość pamięci przez reprezentacje grafu:

Badany przeze mnie graf miał max 60 wierzchołków. W liście krawędzi aby odnaleźć optymalne ścieżki za każdym razem trzeba było przeszukiwać wszystkie krawędzie - po to, aby odczytać szukaną wartość wagi. Miało to istotny wpływ na szybkość działania. Słaba efektywność operacji poszukiwania najkrótszej ścieżki w grafie przy zastosowaniu reprezentacji w postaci listy krawędzi wynikała z samej budowy tej reprezentacji. Reprezentacja listy krawędzi może być efektywna tylko wtedy gdy ustalamy tylko czy dana krawędź istnieje w grafie czy też nie. Lepiej radziła sobie reprezentacja w postaci listy incydencji. Ze wszystkich reprezentacji zawiera ona najmniej informacji nadmiarowych - tablica wskaźników o wielkości równej ilości wierzchołków wskazuje na listy krawędzi incydentnych dla danego wierzchołka.

Najepsze wyniki uzyskały operacje przeprowadzane na reprezentacji w postaci macierzy sąsiedztwa - są już one bardzo szybkie. Macierz ta ma wymiary (ilość wierzchołków * ilość wierzchołków). Odwołania do niej są dość szybkie, spowodowane, zaś za jedyny mankament reprezentacji macierzy sąsiedztwa uznałem to, że tablica wierzchołków jest nadmiarowa, czyli informacje o sąsiedztwie wierzchołków powtórzone są w niej dwukrotnie. Trochę gorzej wypadła macierz incydencji.

Myślę, że jedną z ważniejszych zalet reprezentacji grafów tablicowych jest prosta implementacja programowa, a ponadto korzystanie z nich nie jest trudne. Natomiast za wadę możemy uznać fakt, że: jedynie grafy o ustalonej z góry liczbie węzłów mogą być łatwo reprezentowane w postaci tablic.

W wypadku grafów o liczbie węzłów zmieniającej się w trakcie wykonywania programu, trafnym posunięciem wydaje się użycie reprezentacji - listy incydencji (słownik węzłów).

Przy szukaniu punktów artykulacji (komputerów , których awaria spowoduje awarię sieci) przy wypełnieniu grafu 50% najszybsza była lista incydencji a tuż za nią macierz sąsiedztwa. Później kolejną strukturą jest macierz krawędzi, której pomiar wykonany został tylko dla max 40 wierzchołków ze względu na ograniczenia pamięciowe. Jednak najgorzej wypadła lista krawędzi. Dzieje się to dlatego, że dominującą czynnością podczas szukania punktów artykulacji jest znajdowanie kolejnych nie odwiedzonych wierzchołków incydentnych z danym wierzchołkiem. Czynność ta jest wykonywana dla każdej struktury reprezentacji grafu różnie:

Podsumowując, bardzo szybką i łatwą w implementacji strukturą jest macierz sąsiedztwa ale zajmuje dużo pamięci. Idealna jest tam, gdzie nie zależy nam na pamięci i graf jest statyczny a żądamy od algorytmów poszukiwania najkrótszej ścieżki i poszukiwania punktów artykulacji efektywności.

Przeciwieństwem jest lista krawędzi, która w obu testach była najwolniejsza ale ta reprezentacja ma też zalety takie jak: bardzo szybko znajduje się w tej reprezentacji krawędzie, oraz jeżeli lista jest strukturą dynamiczną to łatwo można dokładać nowe krawędzie - wniosek idealna tam gdzie graf się zmienia.

1

9

E

B

G

D

A

F

C

H

y

x

E

B

D

A

F

C