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ść.

REKLAMA

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.

REKLAMA

Bibliografia

• R.J. Wilson, Wprowadzenie do teorii grafów, Wydawnictwo Naukowe PWN, Warszawa, 2012, ISBN 9788301150662.