Graf

Graf (nazywany też grafem ogólnym) jest to para składająca się z niepustego zbioru , zawierającego wierzchołki (nazywane również węzłami bądź punktami grafu) oraz rodziny krawędzi (jedno lub dwuelementowych podzbiorów zbioru ) nazywanej , łączących te wierzchołki. Krawędzie mogą łączyć ze sobą dwa różne wierzchołki, lecz mogą również łączyć wierzchołek z samym sobą. Może się również zdarzyć sytuacja, w której te same dwa węzły grafu są połączone wieloma krawędziami.

Wyróżniamy również tzw. graf prosty, czyli graf, w którym nie występują pętle (krawędzie łączące wierzchołek z samym sobą) oraz krawędzie wielokrotne (te same dwa węzły grafu mogą być połączone maksymalnie jedną krawędzią). Jeśli graf nie spełnia warunków bycia grafem prostym, nazywamy go multigrafem.

Przykład grafu prostego.

Przykład multigrafu. Wierzchołki 1 i 3 są połączone podwójną krawędzią, a wierzchołek 2 jest połączony sam ze sobą pętlą.

Możemy również wyodrębnić graf skierowany (inaczej digraf). Jest to graf, w którym krawędzie są spolaryzowane, to znaczy mają swój zwrot. Jeśli w grafie ogólnym zilustrujemy sobie krawędzie jako odcinki łączące wierzchołki, to krawędzie w grafie skierowanym możemy wyobrazić sobie jako strzałki. Graf skierowany możemy zdefiniować podobnie do grafu ogólnego, zastępując zbiór krawędzi zbiorem krawędzi skierowanych . Cechy grafu ogólnego i grafu skierowanego łączy graf mieszany, który zawiera zarówno krawędzie skierowane, jak i nieskierowane.

Przykład grafu skierowanego.

Graf ważony jest grafem ogólnym lub skierowanym, w którym wierzchołkom (graf ważony wierzchołkowo) lub krawędziom (graf ważony krawędziowo) przypisane zostały wartości liczbowe nazywane wagami.

Przykład grafu ważonego krawędziowo.

Wierzchołki grafu i są sąsiednie, jeśli łączy je krawędź. Oznacza to również, że te wierzchołki i krawędź są ze sobą incydentne. Analogicznie, warunkiem sąsiedztwa krawędzi jest posiadanie wspólnego wierzchołka.

Liczbę krawędzi incydentnych z danym wierzchołkiem nazywamy stopniem tego wierzchołka (pętle liczy się dwukrotnie). Stopień wierzchołka oznacza się jako . Stopień grafu, oznaczany symbolem Δ, jest największym ze stopni wierzchołka w grafie. Stopnie wszystkich wierzchołków grafu ułożone w kolejności od najmniejszego do największego tworzą ciąg stopni grafu. W oparciu o stopień wierzchołka możemy wyróżnić wierzchołek izolowany, czyli wierzchołek stopnia zero, a także wierzchołek końcowy, o stopniu równym jeden.

Ciąg stopni tego grafu to (1, 2, 2, 2, 3). Stopień grafu Δ = 3. W grafie występuje jeden wierzchołek końcowy E.

Graf, w którym wszystkie wierzchołki są tego samego stopnia n, nazywamy grafem regularnym stopnia n lub grafem n-regularnym. Graf 3-regularny ma swoją własną nazwę – graf kubiczny.

Graf kubiczny, czyli 3-regularny

Graf, którego wierzchołki nie mają nadanych symboli nazywa się grafem nieoznakowanym (w przeciwnym wypadku nazywa się go grafem oznakowanym).

Grafy stosuje się w wielu dziedzinach nauki, między innymi:
• geografia (np. mapy samochodowe)
• informatyka (np. drzewa binarne, sieci neuronowe)
• elektryka (np. schematy elektryczne)
• chemia (np. wzory strukturalne)

Dwa grafy oraz nazywamy izomorficznymi, gdy dla każdego wierzchołka grafu możemy przypisać wierzchołek grafu w ten sposób, aby gdy w grafie dwa wierzchołki są połączone krawędzią, to przypisane do nich wierzchołki w grafie również są połączone krawędzią. Jeśli dwa grafy są izomorficzne, to uznajemy je za tożsame.

Grafy i są izomorficzne (wierzchołek zostaje przypisany do , do , itd.).

Grafy i nie są izomorficzne (w grafie wierzchołki i są połączone krawędzią, w grafie wierzchołki im odpowiadające nie są połączone).

Wiedząc, że grafy izomorficzne uznajemy za tożsame, jesteśmy w stanie wymienić wszystkie grafy proste o podanej ilości wierzchołków, np. wszystkie nieoznakowane grafy proste o trzech wierzchołkach to:

Inny wynik uzyskamy jednak podczas zliczania grafów oznakowanych, ponieważ jest innym grafem od grafu . Do zliczenia wszystkich oznakowanych grafów prostych możemy posłużyć się wzorem , gdzie n oznacza liczbę wierzchołków w grafie.

Dowód:
W grafie prostym G o liczbie wierzchołków n, każda para wierzchołków może być połączona bądź niepołączona krawędzią. Liczba tych hipotetycznych krawędzi to liczba krawędzi w tym grafie, gdyby wszystkie wierzchołki były połączone dokładnie jedną krawędzią.

Każdy z n wierzchołków może być połączony z każdym z n – 1 pozostałych wierzchołków. Jeśli więc przejdziemy po wszystkich wierzchołkach, łącząc je ze wszystkimi innymi wierzchołkami, otrzymamy graf o liczbie n wierzchołków, z których każdy z nich jest połączony dwoma krawędziami (ponieważ gdy byliśmy na wierzchołku A połączyliśmy go z wierzchołkiem B, a następnie, będąc na wierzchołku B, połączyliśmy go z powrotem z wierzchołkiem A). Liczba krawędzi w tym grafie wynosi (na każdy z n wierzchołków przypada n – 1 krawędzi).

Aby odnaleźć liczbę krawędzi w grafie, w którym każdy z wierzchołków jest połączony dokładnie jedną krawędzią, dzielimy tą liczbę przez dwa, otrzymując wzór . Ten wzór pozwala nam ustalić, ile krawędzi może powstać w grafie o liczbie wierzchołków n. Oznacza to, że każdy wariant takiego grafu możemy przedstawić jako liczbę binarną (liczbę, w której każda z cyfr może przybrać wartość 0 lub 1) o cyfrach, w której każda cyfra symbolizować będzie taką hipotetyczną krawędź. Jeśli dana cyfra jest jedynką, oznacza to, że krawędź istnieje, jeśli natomiast cyfra jest zerem, to krawędź nie istnieje.

Tak więc wszystkie warianty grafu o n wierzchołkach możemy przedstawić jako liczba binarna o cyfrach. Taka liczba binarna może przyjmować wartości od 0 do , czyli, włącznie z zerem, jest to wartości. Skoro każda z wartości oznacza jeden wariant takiego grafu, to oznakowanych grafów prostych o n wierzchołkach jest , co należało udowodnić.

Trasa to ciąg wierzchołków grafu, z których każde dwa kolejne wierzchołki są połączone krawędzią. Długością trasy nazywamy liczbę krawędzi po których „przechodzimy”.

Trasa w tym grafie ma długość 3.

Trasa, w której nie powtarzają się wierzchołki nazywamy drogą. Trasa, która zaczyna się i kończy tym samym wierzchołkiem nazywamy cyklem.

Trasa jest cyklem.

Graf spójny jest grafem w którym każde dwa dowolnie wybrane wierzchołki można połączyć trasą (składa się z jednej „części”). Graf, który nie spełnia tych warunków nazywa się grafem niespójnym.

Graf jest grafem niespójnym. Graf jest grafem spójnym.

Drzewo to graf spójny, w którym nie występują żadne cykle. W drzewie dowolną parę wierzchołków można połączyć dokładnie jedną drogą.

Drzewo binarne, czyli drzewo, w którym wierzchołki są maksymalnie trzeciego stopnia. Drzewo binarne znajduje swoje zastosowanie w informatyce.

Grafem planarnym nazywa się graf, który można narysować w taki sposób, żeby jego krawędzie się nie przecinały.

Ten graf nie jest grafem planarnym, jednak po usunięciu wierzchołka E…

Krawędzie pomiędzy wierzchołkami A i C oraz B i C na tym rysunku się przecinają, jednak graf ten jest grafem planarnym, ponieważ możemy go przedstawić w ten sposób:

Podgrafem grafu G nazywamy graf, którego wierzchołki zawierają się w zbiorze wierzchołków grafu G, a jego krawędzie – w zbiorze krawędzi grafu G.

Graf jest podgrafem grafu

Pierwszym problemem rozwiązanym dzięki teorii grafów jest, opublikowany w 1736 roku przez Leonharda Eulera, problem mostów królewieckich. Przez miasto Królewiec (współczesny Kaliningrad) przepływała rzeka Pregoła, nad którą postawiono siedem mostów, w sposób przedstawiony na zdjęciu poniżej.

(źródło zdjęcia: edupedia.pl)

Problem brzmiał: czy da się przejść przez wszystkie mosty nie przechodząc przez żaden dwukrotnie, tak, aby wrócić to punktu wyjścia?

Rozwiązanie:
Problem ten da się przedstawić za pomocą grafu, w którym krawędzie symbolizują królewieckie mosty.

Euler zauważył, że za każdym razem gdy „wchodził” na wierzchołek jednym mostem, musiał go opuścić innym mostem, co oznaczało, że stopień tego wierzchołka musi być parzysty. Aby graf zawierał cykl eulerowski (cykl, który przechodzi przez każdy wierzchołek dokładnie jeden raz), każdy wierzchołek w tym grafie musi być stopnia parzystego. Graf przedstawiający mosty królewieckie nie spełnia tego warunku, zatem odbycie spaceru po wszystkich mostach Królewca przechodząc po każdym dokładnie jeden raz, tak, aby powrócić do miejsca z którego się zaczynało jest niemożliwe.

Innym znanym problemem teorii grafów jest problem komiwojażera. Brzmi on następująco: komiwojażer (podróżujący sprzedawca) musi odwiedzić wszystkie miasta dokładnie jeden raz i wrócić do miasta, z którego wyjeżdżał, tak, aby przebyć jak najkrótszą trasę. Miasta możemy przedstawić jako wierzchołki na grafie ważonym. Wagi krawędzi oznaczają dystans jaki komiwojażer musi przebyć, aby przemieścić się z jednego miasta do drugiego.

Problemem nie jest tak naprawdę własnoręczne obliczenie rozwiązania, ale ułożenie algorytmu, który znalazłby najkrótszą trasę w jak najkrótszym czasie, czyli o jak najmniejszej złożoności obliczeniowej (algorytm powinien wymagać wykonania jak najmniejszej ilości operacji matematycznych). Problem komiwojażera jest znany ze swojej trudności, mimo nieskomplikowanych warunków zadania, a także ze swojego praktycznego zastosowania w branży logistycznej. Dla grafu przedstawionego powyżej odpowiedzią byłaby droga: Gdańsk Warszawa Katowice Wrocław Gdańsk.

Inną wersją tego problemu jest asymetryczny problem komiwojażera, w którym graf jest grafem skierowanym, a każde miasto jest połączone dwoma krawędziami – w jedną i w drugą stronę. W praktyce oznacza to, że droga z miasta A do miasta B nie jest równa drodze z miasta B do miasta A. Jest to bardziej skomplikowany, ale też częściej spotykany w praktyce wariant.

Z dwóch grafów możemy wyznaczyć ich sumę. Suma grafów oraz to graf , którego zbiór wierzchołków to suma zbiorów wierzchołków grafów i , a jego zbiór krawędzi to suma zbiorów krawędzi tych grafów. Grafy oraz nazywamy składowymi grafu . Suma grafów zawsze będzie grafem niespójnym.
=
Zadania:

Zadanie 1.
Wyznacz ciąg stopni podanego grafu.

Zadanie 2.
Czy podane grafy są izomorficzne?

Zadanie 3.
Ile jest różnych oznakowanych grafów prostych o pięciu wierzchołkach?
Zadanie 4.
Czy podany graf jest grafem eulerowskim (czy zawiera cykl eulerowski)?

Zadanie 5.
Czy podany graf jest grafem regularnym?


Odpowiedzi:

Zadanie 1.
Ciąg stopni tego grafu to (2, 2, 3, 4, 5).

Zadanie 2.
Podane grafy nie są izomorficzne.
Zadanie 3.

Istnieją 1024 różne oznakowane grafy proste o pięciu wierzchołkach.
Zadanie 4.
Tak, ponieważ każdy wierzchołek jest parzystego stopnia.

Zadanie 5.
Tak, ponieważ każdy wierzchołek jest tego samego stopnia (trzeciego). Co więcej, graf ten jest grafem kubicznym.