GiS - algorytmy -- pełnie podsumowanie do przedmiotu grafy i sieci na WZIM PDF

Preview

Summary

GiS - algorytmy - pełnie podsumowanie do przedmiotu grafy i sieci na WZIM...

Description

Algorytm Kruskala Na wejściu: Dowolny graf ważony ( ). Na wyjściu: Najtańsze drzewo rozpinające grafu . Sposób postępowania: 1. Stwórz pusty graf taki, że ( ) ( ). 2. Wybierz krawędź ( ) o najmniejszej wadze. 3. Jeśli ( ) * + nie zawiera cykli, dodaj do ( ). 4. Jeśli graf nie jest spójny, wróć do kroku 2. Algorytm Prima Na wejściu: Dowolny graf ważony ( ). Na wyjściu: Najtańsze drzewo rozpinające grafu . Sposób postępowania: 1. Stwórz pusty graf taki, że ( ) ( ). Stwórz pusty zbiór krawędzi . 2. Wybierz dowolny wierzchołek ( ). Wszystkie krawędzie z nim incydentne dodaj do . 3. Wybierz krawędź ( ) o najmniejszej wadze. Jeśli ( ) * + nie zawiera cykli, dodaj do ( ). Usuń ze zbioru . Dodaj do wszystkie niewykorzystane krawędzie incydentne z nowo połączonym wierzchołkiem. 4. Jeśli graf nie jest spójny, wróć do kroku 3. Algorytm Dijkstry Na wejściu: Dowolny graf ważony ( ) z wyróżnionymi wierzchołkami Na wyjściu: Długość najkrótszej drogi łączącej i .

.

Sposób postępowania: ) i nadaj im etykiety 1. Wszystkie wierzchołki z ( ) oznacz jako nieodwiedzone ( ( ) równe ( ( ) ) Stwórz zbiór wierzchołków do odwiedzenia * +. 2. ( ) , ( ) 3. Weź dowolny wierzchołek . 3. Dla dowolnego sąsiada wierzchołka ustaw ( ) * ( ) ( ) ( )+, gdzie ( ) jest wagą tej krawędzi oraz ( ) . Dodaj do zbioru . 4. Usuń ze zbioru . 5. Jeśli nie jest pusty, wróć do kroku 3. Algorytm Fleury’ego Na wejściu: Dowolny graf eulerowski Na wyjściu: Cykl Eulera

( ).

Sposób postępowania: 1. Wybierz dowolny wierzchołek ( ) i dodaj do . 2. Ustalona jest ścieżka . Wybierz krawędź incydentną z , która nie jest + chyba, że nie ma innej możliwości. mostem w grafie * 3. Powróć do kroku 2, jeśli może być wykonany.

Dolne ograniczenie cyklu Hamiltona Na wejściu: Dowolny graf hamiltonowski ( ). Na wyjściu: Dolne ograniczenie cyklu Hamiltona w . Sposób postępowania: 1. Wybierz dowolny wierzchołek ( ). 2. Stwórz najtańsze drzewo rozpinające grafu * + i oblicz jego wagę. 3. Zsumuj wagi wszystkich krawędzi incydentnych z i dodaj do wagi drzewa z kroku 2. Uzyskana wartość jest dolnym ograniczeniem cyklu Hamiltona. Wielomian chromatyczny Na wejściu: Dowolny graf ( ) o | ( )|, dostępnych kolorów. Na wyjściu: Wielomian ( ) opisujący ilość możliwych pokolorowań grafu przy użyciu kolorów. Założenia: Wielomian chromatyczny grafu pełnego: ( ) ( ) ( ) Wielomian chromatyczny dla drzewa: ( )

(

)

Sposób postępowania: 1. Wybierz dowolną krawędź ( ). 2. Stwórz graf * + oraz - powstały z grafu na skutek ściągnięcia krawędzi . 3. ( ) ( ) ( ) 4. Procedurę powtarzać do momentu, w którym uzyskamy grafy o znanych wielomianach chromatycznych. Kod Prüfera Pozwala na jednoznaczny zapis drzewa przy pomocy ciągu liczb lub stworzenie drzewa na podstawie ciągu liczbowego. I. Drzewo kod Prüfera: 1. Stwórz pusty ciąg oraz zbiór zawierający wszystkie liście drzewa . 2. Wybierz ze zbioru liść o najmniejszej wartości. Ponieważ jest liściem, posiada dokładnie jednego sąsiada , z którym łączy się krawędzią . ). Zapisz jako ostatni wyraz ciągu . 3. Usuń z drzewa ( 4. Jeśli w drzewie pozostały 2 wierzchołki, zakończ algorytm. W przeciwnym wypadku zaktualizuj zbiór liści i przejdź do kroku 2. II. Kod Prüfera drzewo 1. Niech będzie ciągiem wierzchołków – kodem Prüfera. Stwórz zbiór zawierający wartości wszystkich wierzchołków drzewa . Stwórz nowe puste drzewo. 2. Wybierz ze zbioru wierzchołek o najmniejszej wartości, która nie występuje w ciągu . 3. Wybierz pierwszy element z ciągu . 4. Dodaj do tworzonego drzewa krawędź . Usuń pierwszy wyraz ciągu . Usuń ze zbioru . 5. Jeśli w pozostały dokładnie 2 wierzchołki, połącz je krawędzią. W przeciwnym wypadku przejdź do kroku 2.

Algorytm Floyda-Warshalla Na wejściu: Graf ważony, także skierowany, ( ) o | ( )|. Na wyjściu: Macierz poprzedników w najkrótszych ścieżkach pomiędzy parami wierzchołków. Sposób postępowania: ()

1. Stwórz początkową macierz wag

[

w wierzchołku w kierunku . Jeśli

, to

()

to

()

()

jest wagą krawędzi o początku

. Jeśli wierzchołki się nie komunikują,

.

2. Stwórz początkową macierz to

()

] , gdzie

()

[

()

. W przeciwnym wypadku

] poprzedników. Jeśli (

()

()

lub

,

)

). Stworzymy macierze oraz . 3. Rozpoczynamy iterację ( 4. W macierzy wpisujemy bez zmian z macierzy ty wiersz oraz tą kolumnę, a także wszystkie wyrazy, gdzie

()

.

5. Dla wszystkich pozostałych wyrazów ( )

()

( )

{

( )

( )

}. Jeśli

()

, zakreślamy nowy wyraz.

6. W macierzy wyróżniamy ty wiersz. Jeśli W przeciwnym wypadku 7. Jeśli

()

( )

()

został zakreślony, to

()

( )

.

, zakończ. W przeciwnym wypadku wróć do kroku 3.

Aby wyznaczyć najkrótszą ścieżkę pomiędzy wierzchołkami oraz korzystamy z . 1. Stwórz ciąg, który będzie uzupełniany od końca. Jako ostatni wyraz wybierz . 2. Odczytaj z macierzy wyraz . Niech . 3. Jeśli , zakończ. W przeciwnym wypadku wpisz jako pierwszy wyraz ciągu i wróć do kroku 2.

....