Graf

Minimalne drzewo rozpinające, przykład (1) Graf prosty (po lewej) i drzewo (po prawej)
Graf, 4 wierzchołki (2) Graf pełny z wagami
Graf skierowany (3) Graf skierowany z wagami

Graf – struktura G = (V, E) składająca się ze skończonego zbioru wierzchołków V oraz skończonego zbioru krawędzi E, gdzie każda krawędź e ∈ E jest dwuelementowym zbiorem wierzchołków u, v ∈ V. Wierzchołki u, v połączone krawędzią e = {u, v} określane są sąsiednimi. Grafy mają szerokie zastosowanie w informatyce, można za ich pomocą przedstawiać rożnego rodzaju relacje pomiędzy obiektami.

Powyższa definicja dotyczy grafu nieskierowanego, gdzie 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 krawędzi, za pomocą którego możemy przejść z jednego wierzchołka grafu do innego (lub wrócić do tego samego). W niektórych źródłach definiowana jako ciąg wierzchołków, w którym każde dwa kolejne wierzchołki są sąsiednie (połączone krawędzią).
  • Ś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 (inaczej kontur).
  • 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ę).

Terminologia dotycząca grafów może różnić się w zależności od źródła. Przykładowo, czasami trasa określana jest jako droga.

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.
Ocena: 0 Tak Nie
Liczba głosów: 2.

Dodano: 6 grudnia 2017 10:31, ostatnia edycja: 28 grudnia 2022 16:19.

REKLAMA

Zobacz też

Algorytm heurystyczny, heurystyka – algorytm niedający (w ogólnym przypadku) gwarancji znalezienia rozwiązania optymalnego, umożliwiający jednak znalezienie rozwiązania dość dobrego w rozsądnym czasie. Algorytmy tego typu używane są w takich problemach obliczeniowych, gdzie znalezienie rozwiązania optymalnego ma zbyt dużą złożoność obliczeniową (w szczególności są to problemy NP-trudne) lub w ogóle nie jest możliwe. Metody heurystyczne zaliczają się do sztucznej inteligencji.

Pojęcie algorytmów heurystycznych jest bardzo szerokie, dotyczy ono różnych technik projektowania algorytmów. Wiele heurystyk wykorzystuje losowość, inne zaś są deterministyczne (wówczas dla takich samych danych wejściowych algorytm zawsze zwróci ten sam wynik).

Ogólny algorytm heurystyczny (opisujący samą ideę poszukiwań) bywa określany w literaturze jako metaheurystyka. Zgodnie z tym nazewnictwem, metaheurystyką jest np. algorytm zachłanny (jako ogólna idea), zaś heurystyką jest np. algorytm najbliższego sąsiada (jako zastosowanie idei algorytmu zachłannego do konkretnego problemu).

Przykładowe techniki konstruowania algorytmów heurystycznych to:

→ Czytaj całość
Sortowanie bąbelkowe (ang. bubble sort) – prosty algorytm sortowania polegający na porównywaniu za sobą sąsiednich elementów. Złożoności czasowa algorytmu wynosi O(n2).
→ Czytaj całość

Ten artykuł opisuje pewną modyfikację algorytmu opartego na programowaniu dynamicznym rozwiązującego problem wydawania reszty. Algorytm ten daje gwarancję znalezienia rozwiązania optymalnego. Algorytm zaproponował J.W. Wright w pracy The Change-Making Problem (link w bibliografii).

→ Czytaj całość
Polityka prywatnościKontakt