Przeczytaj
Co to jest graf?
GrafGraf to struktura, która składa się z dwóch rodzajów elementów – wierzchołkówwierzchołków i krawędzikrawędzi.
Wierzchołek grafu jest elementem, który stanowi reprezentację pewnego obiektu, miejsca czy rzeczy. W zależności od struktury, jaka została przedstawiona w formie grafu, jego wierzchołkami (inaczej nazywanymi węzłami) mogą być np. samochody, planety, miasta na mapie czy cząsteczki chemiczne.
![Ilustracja przedstawia dwa grafy. Pierwszy graf ukazuje połączenia chemiczne między związkami chemicznymi. Połącznia związków C1, C2, C3, C4, C5 połączone ze sobą prostymi, C1, C2, C3, C6 połączone ze związkami H. C4, z O , następnie z C8, O, C9, z trzema związkami H. C5 z C7, z dwiema O oraz H. Po prawej stronie znajduje się graf ilustrujący połączenie komputerów w sieci lokalnej. Znajduje się na nim 8 ikon komputerów stacjonarnych połączonych z głównym serwerem.](https://static.zpe.gov.pl/portal/f/res-minimized/R1GOAS8DemW9s/1690815076/1biygkqLtWf7Pcvs1iixjmIeyLvEM6Oc.png)
Krawędź grafu to z kolei powiązanie między dwoma wierzchołkami. Może ona mieć postać materialną (jak w przypadku kabli łączących komputery w sieci czy też dróg między miastami) lub niematerialną (jak relacje społeczne – np. przyjaźnie łączące uczniów danej klasy). Każda krawędź reprezentowana jest przez parę wierzchołków.
Graf, w którym każda para różnych wierzchołków połączona jest krawędzią, nazywamy grafem pełnym. Graf pełny o wierzchołkach oznaczany jest symbolem . Liczbę krawędzi w takim grafie wyznacza wyrażenie .
Oznaczenia i definicje
Mianem grafu prostego określamy parę , w której jest skończonym zbiorem elementów (wierzchołków lub inaczej węzłów), a – skończonym zbiorem nieuporządkowanych par różnych elementów (krawędzi) zbioru . W takim przypadku oznacza zbiór wierzchołków, a – zbiór krawędzi grafu .
Często będziemy posługiwać się więcej niż jednym grafem. Dla ich rozróżnienia zbiór wierzchołków grafu oznaczać będziemy jako , a zbiór krawędzi jako .
Posługując się grafami, często pomijamy cechy geometryczne, takie jak odległość między punktami – umiejscowienie wierzchołków służy jedynie przejrzystej wizualizacji.
![Przykłady grafów Ilustracja przedstawia trzy grafy. 1: Połączone 5 punktów, z których każdy połączony jest dodatkowo z szóstym punktem środkowym. 2: Graf przedstawia połączenie sześciu punktów z nieregularnymi połączeniami. 3: Graf łączy 6 punktów tworząc kształt gwazdy.](https://static.zpe.gov.pl/portal/f/res-minimized/R17JwVf9PGbu3/1690815077/cAxCR6yIVs71EW4WP0ftoMnQihpVvtEh.png)
Wierzchołki grafu zwykle oznaczamy kolejnymi liczbami naturalnymi lub literami (jak na rysunku poniżej: , , itd.), natomiast krawędzie będące nieuporządkowaną parąnieuporządkowaną parą wierzchołków, np. , możemy zapisać jako . Mówimy wtedy, że krawędź łączy wierzchołki i .
![Ilustracja przedstawia graf. Węzły grafu podpisane są literami: r, q, p, s, v, y. Każdy z węzłów łączy się z węzłem środkowym zawierającym literę u.](https://static.zpe.gov.pl/portal/f/res-minimized/RET85GKwO8DtD/1690815077/1WsStgxzBwbkm8DjsQZsHQPzLQUxos0Z.png)
Przedstawione wcześniej przykłady grafów to grafy proste. Gdyby dopuścić jednak, że krawędzie grafu mogą łączyć także wierzchołek sam ze sobą oraz że pary wierzchołków mogą być połączone więcej niż jedną krawędzią, mielibyśmy do czynienia z multigrafem. Krawędź łączącą wierzchołek sam ze sobą nazywamy pętlą, zaś krawędź, która łączy wierzchołki już połączone – krawędzią wielokrotną.
Oto przykłady pętli oraz krawędzi wielokrotnych:
![Ilustracja przedstawia przykład pętli oraz krawędzi wielokrotnych. Po lewej stronie zielonym kolorem zaznaczono pętle linię która tworzy pętlę powracającą do tego samego węzła. Po prawej stronie zaznaczono zakrzywione linie łączące węzły przedstawiające krawędzie wielokrotne.](https://static.zpe.gov.pl/portal/f/res-minimized/Rc3qpc8Blle3c/1690815078/2gcf4s8TBAb6M0hvvT2vWWIEqGi7SCEb.png)
Wiele algorytmów grafowych korzysta z wag krawędzi, które można interpretować na różne sposoby. Przykładem może być algorytm Dijkstryalgorytm Dijkstry (czyli algorytm wyszukujący najkrótsze połączenie między dwoma wierzchołkami) – wagi krawędzi traktujemy wówczas jako odległość między wierzchołkami i na tej podstawie algorytm znajduje najkrótszą ścieżkę między dwoma węzłami grafu. Graf, w którym krawędzie mają przypisane wagi, nazywamy grafem ważonym.
![Ilustracja przedstawia graf o połączeniach węzeł prosta węzeł: A, 10, C. C, 5, D. D, 6, E. E, 4, B. B, 14, F. F, 7, A. F, 8, C. C, 2, B. D, 1, B.](https://static.zpe.gov.pl/portal/f/res-minimized/R1ANkZTZ7oYfe/1690815078/1L43X257EGvWImyBNSMZ0VXWQkU16nQ9.png)
Dwa wierzchołki nazywamy sąsiednimi, gdy są one połączone krawędzią. Możemy wtedy również powiedzieć, że wierzchołki te są incydentne z tą krawędzią. Jeśli krawędzie mają jeden wspólny wierzchołek, również określamy je jako sąsiednie.
Stopień wierzchołkaStopień wierzchołka grafu oznaczamy symbolem . Jest to liczba krawędzi incydentnych z wierzchołkiem . Zbiór wierzchołków sąsiednich dla wierzchołka nazywamy sąsiadami wierzchołka .
Trasy, drogi, cykle
Trasą w grafie nazywamy ciąg krawędzi: , w którym każde dwie kolejne krawędzie ze sobą sąsiadują lub są identyczne. Taka trasa wyznacza kolejno ciąg wierzchołków, które łączy: . W trasie tej nazywamy wierzchołkiem początkowym, zaś – wierzchołkiem końcowym. Liczbę krawędzi wchodzących w skład trasy nazywamy jej długością. Szczególny przypadek trasy, gdzie wszystkie krawędzie są różne, nazywamy ścieżką. Ścieżkę, w której wierzchołki są różne (z wyjątkiem wierzchołka początkowego i końcowego), nazywamy drogą.
![Ilustracja przedstawia graf połączonych liter: u, q, r, t, s, v, p, x, w. Proste łączące litery r, s, q, t z literą u są koloru niebieskiego.](https://static.zpe.gov.pl/portal/f/res-minimized/R11lQKShCIs93/1690815078/o3l9Rta1ALaekFHON7SYXOFbtvynRtZi.png)
Na powyższym grafie zaznaczono ścieżkę , w której jest wierzchołkiem początkowym, a – wierzchołkiem końcowym. W tym przypadku długość ścieżki jest równa . Warto zauważyć, że wierzchołek powtarza się na powyższej ścieżce dwukrotnie – z tego powodu nie możemy nazwać jej drogą.
Przykładową drogę , w której jest wierzchołkiem początkowym, a wierzchołkiem końcowym, przedstawiono na grafie:
![Ilustracja przedstawia graf połączonych liter: u, q, r, t, s, v, p, x, w. Proste łączące litery t, u, s, v, p są koloru niebieskiego.](https://static.zpe.gov.pl/portal/f/res-minimized/RCViTV3sWTqWi/1690815079/1eV39q5SkQwFwsfkgoJJ75dSaVytiTrL.png)
Jeśli w rozpatrywanym grafie każda para wierzchołków połączona jest drogą, mamy do czynienia z grafem spójnymgrafem spójnym.
Jeśli dla pewnej ścieżki zachodzi równość , to ścieżkę tę nazywamy ścieżką zamkniętą. Ścieżka zamknięta, która zawiera co najmniej jedną krawędź, to cykl. Oznacza to, że jedyną ścieżką zamkniętą niebędącą cyklem, jest ścieżka niezawierająca żadnej krawędzi.
![Ilustracja przedstawia dwa grafy. 1: przedstawia graf połączonych liter: u, q, r, t, s, v, p, x, w. Proste łączące litery p, q, r, t, s, v są koloru niebieskiego. 2: przedstawia graf połączonych liter: u, q, r, t, s, v, p, x, w. Proste łączące litery r, q, u są koloru niebieskiego.](https://static.zpe.gov.pl/portal/f/res-minimized/RU06weaVPBZMC/1690815079/23EDEoYMJrR7KUh1AqdmjdNkJDfGMsG2.png)
Powyżej zaznaczono dwa cykle: oraz . Możemy je znaleźć w tym samym grafie. Jeśli chcemy wiedzieć, czy dany graf zawiera cykl, możemy skorzystać z następującej własności:
Jeżeli najmniejszy stopień wierzchołka w grafie jest nie mniejszy niż , to graf zawiera cykl.
Izomorfizm
Grafy i są izomorficzneizomorficzne, jeżeli między ich wierzchołkami istnieje podobieństwo polegające na tym, że liczba krawędzi łączących wybraną parę wierzchołków grafu oraz liczba krawędzi łączących dwa odpowiadające im wierzchołki grafu są takie same. Izomorfizm zapisujemy jako wyrażenie , a odpowiedniość wierzchołków i oznaczamy symbolem . Grafy izomorficzne mają taką samą strukturę, mogą różnić się tylko nazwami wierzchołków i krawędzi.
![Ilustracja przedstawia dwa grafy. 1: W kształcie sześciokąta gdzie każda litera łączy się z literą sąsiednią oraz z literą na przeciw niej, zawiera w węzłach litery: s, r, q, p, u, t. 2: Graf izomorficzny względem pierwszego to graf z literami p prim, t prim, r prim, s prim, q prim, u prim. Ułożone są w dwóch rzędach po trzy węzły, każdy węzeł z jednego rzędu łączy się z każdym węzłem z rzędu drugiego.](https://static.zpe.gov.pl/portal/f/res-minimized/R5s0w2cQJ8rtp/1690815080/2SP9rP2NJUtUtsK9JnT1hJr0NEXz4ajO.png)
Na przedstawionym rysunku wierzchołki grafu G odpowiadają wierzchołkom grafu H. Przykładowo, wierzchołek grafu G ma trzech sąsiadów, co oznacza że odpowiada wierzchołkowi w grafie H, czyli .
Rozrysuj w formie grafu relacje panujące w pewnym gronie. Załóż, że: Anna zna Bartka; Czarek zna Daniela; Czarek i Daniel znają Emilię; Bartek zna Franka, Daniela oraz Emilię.
Słownik
struktura składająca się z niepustego zbioru wierzchołków oraz ze zbioru krawędzi; dla grafu zbiór wierzchołków oznaczamy (ang. verticies – wierzchołki), a zbiór krawędzi – (ang. edges – krawędzie); liczbę elementów zbioru oznaczamy literą , zaś liczbę elementów zbioru –
graf, w którym każda para wierzchołków połączona jest drogą
właściwość grafów polegająca na tym, że liczba krawędzi łączących dane dwa wierzchołki jednego grafu jest równa liczbie krawędzi łączących odpowiadające im wierzchołki drugiego grafu; jeśli graf jest izomorficzny z grafem , to gdy jakieś dwa wierzchołki są połączone krawędzią w jednym z grafów, odpowiadające im wierzchołki w drugim grafie również łączy krawędź; izomorfizm grafów zachowuje takie własności jak: liczba wierzchołków, liczba krawędzi, stopnie wierzchołków, czy spójność grafu
nieuporządkowana para (niekoniecznie różnych) elementów zbioru wierzchołków, tj. takich, które są ze sobą połączone; w reprezentacji graficznej jest to linia łącząca te wierzchołki; krawędź może łączyć ze sobą jeden wierzchołek (wtedy nazywana jest pętlą)
zbiór złożony jedynie z dwóch różnych elementów:
liczba krawędzi incydentnych z danym wierzchołkiem
inaczej: punkt, węzeł; element niepustego zbioru, który wraz ze zbiorem krawędzi tworzy graf