Graf
Graf – struktura składająca się ze zbioru wierzchołków oraz zbioru krawędzi. Grafy mają szerokie zastosowanie w informatyce, można za ich pomocą przedstawić wiele zagadnień.
Wyróżniamy grafy nieskierowane oraz grafy skierowane. W grafie nieskierowanym relacja sąsiedztwa jest symetryczna, tzn. krawędź łączy wierzchołki „w obie strony”. W grafie skierowanym krawędzie są „jednokierunkowe”. Krawędź grafu skierowanego zazwyczaj jest określana jako łuk.
Graf ważony (inaczej graf z wagami) to taki graf, w którym każdej krawędzi przypisana jest pewna wartość liczbowa. Wartość ta może oznaczać np. długość krawędzi lub jej przepustowość.
Wybrane pojęcia związane z teorią grafów
- Trasa – ciąg kolejnych krawędzi, za pomocą którego możemy przejść z jednego wierzchołka grafu do innego (lub wrócić do tego samego).
- Ścieżka – trasa, w której każda krawędź występuje co najwyżej raz (mogą natomiast powtarzać się wierzchołki).
- Droga (ścieżka prosta) – trasa, w której każdy wierzchołek występuje co najwyżej raz. Wyjątkiem jest wierzchołek końcowy, który może być wierzchołkiem początkowym – taka ścieżka to cykl.
- Pętla – krawędź prowadząca z wierzchołka do niego samego.
- Krawędź wielokrotna – kilka krawędzi łączących tę samą parę wierzchołków.
- Graf prosty – graf nie zawierający żadnych pętli ani krawędzi wielokrotnych.
- Graf spójny – graf, w którym można wyznaczyć ścieżkę między każdą parą wierzchołków.
- Graf pełny – graf prosty, w którym każda para wierzchołków jest bezpośrednio połączona krawędzią.
- Drzewo – graf spójny nie mający żadnych cykli (taki, w którym między każdą parą wierzchołków można wyznaczyć dokładnie jedną ścieżkę).
Reprezentacja w pamięci komputera
W pamięci komputera grafy zazwyczaj są przechowywane w postaci list lub macierzy sąsiedztwa. W przypadku list sąsiedztwa każdemu wierzchołkowi przyporządkowana jest lista wierzchołków z nim sąsiadujących. W przypadku macierzy sąsiedztwa w pamięci przechowywana jest macierz, w której każdy wiersz i każda kolumna odpowiada innemu wierzchołkowi. Liczba na przecięciu wiersza i kolumny informuje, ile krawędzi łączy daną parę wierzchołków (w przypadku grafu ważonego prostego można tam zamieścić wagę krawędzi). W przypadku grafu nieskierowanego macierz jest symetryczna.
Bibliografia
- R.J. Wilson, Wprowadzenie do teorii grafów, Wydawnictwo Naukowe PWN, Warszawa, 2012, ISBN 9788301150662.
Liczba głosów: 0.
Dodano: 6 grudnia 2017 10:31, ostatnia edycja: 30 stycznia 2019 15:58.
Zobacz też
Problem wydawania reszty (ang. change-making problem) – problem obliczeniowy polegający na tym, aby mając określony zbiór nominałów wyrazić daną kwotę za pomocą jak najmniejszej liczby monet. Jest to szczególny przypadek problemu plecakowego.
Notacja dużego O – notacja przedstawiająca asymptotyczne tempo wzrostu, wykorzystywana do zapisywania złożoności obliczeniowej algorytmu. Za pomocą tej notacji zapisywany jest rząd wielkości funkcji wyrażającej liczbę operacji dominujących (w przypadku złożoności czasowej) lub rozmiar wymaganej pamięci (w przypadku złożoności pamięciowej) w zależności od liczby danych wejściowych.
Wykorzystując notację dużego O nie podajemy dokładnego wzoru funkcji, a jedynie jej najbardziej znaczący składnik, w dodatku z pominięciem stałego współczynnika. Przykładowo, funkcję postaci f(n)=5n2+20n+100 możemy zapisać jako O(n2). Zakładamy bowiem, że dla dostatecznie dużych n wpływ pomijanych elementów jest znikomy. Choć oczywiście dla małych n może się zdarzyć, że funkcja o gorszej złożoności będzie się wykonywała szybciej.
Weźmy dla przykładu funkcje f(n) = 1000n+2000 i g(n) = n2. Choć pierwsza funkcja ma pozornie bardzo duże stałe współczynniki, to dla n ≥ 1002 będzie ona przyjmowała wartości mniejsze. Im większe n, tym ta różnica będzie wyraźniejsza. Dla n = 10000 (w przypadku danych przetwarzanych komputerowo nie jest to wielka wartość) f(n) = 10002000 (ok. 10 mln), a g(n) = 100000000 (100 mln), czyli blisko 10 razy więcej.
Możliwe jest również wykorzystanie notacji dużego O dla funkcji wielu zmiennych. Wówczas zapis może wyglądać tak: O(v2e). Znajduje to zastosowanie np. dla algorytmów operujących na grafach, gdzie złożoność zależy zarówno od liczby wierzchołków, jak i liczby krawędzi w grafie.
Algorytm Floyda-Warshalla – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Jest to algorytm oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n3) i złożoność pamięciową O(n2), gdzie n jest liczbą wierzchołków.
Algorytm dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli. Algorytm może być również wykorzystywany do wyszukiwania ujemnych cykli w grafie.