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

Dodano: 6 grudnia 2017 10:31, ostatnia edycja: 30 stycznia 2019 15:58.

REKLAMA

Zobacz też

Metoda Forda-Fulkersona – algorytm służący do wyznaczania maksymalnego przepływu. Jest to algorytm bardzo ogólny, dlatego często nie jest nazywany algorytmem, a metodą. Popularną implementacją tej metody jest algorytm Edmondsa-Karpa. Algorytm można opisać następująco:

  1. Wyznacz sieć residualną (opis sieci residualnej znajduje się w dalszej części artykułu).
  2. Znajdź w sieci residualnej dowolną ścieżkę powiększającą.
  3. Jeśli nie udało się wyznaczyć żadnej ścieżki powiększającej, zakończ działanie algorytmu.
  4. W przeciwnym razie zwiększ przepływ w sieci (w sposób opisany w dalszej części artukułu) i wróć do punktu 1.
→ Czytaj całość

Sortowanie przez scalanie – rekurencyjny algorytm sortowania wykorzystujący metodę dziel i zwyciężaj.

→ Czytaj całość

Kolejka (ang. Queue) – struktura danych, w której elementy pobierane są z początku, a dodawane na końcu. Z kolejki można zatem pobrać tylko ten element, który był dodany najwcześniej. Kolejka bywa określana również jako kolejka FIFO (z ang. First In, First Out), w odróżnieniu od kolejki LIFO, czyli stosu.

→ Czytaj całość
Polityka prywatnościKontakt