Graf (matematyka)

Graf – podstawowy obiekt rozważań teorii grafów^[1][2] , struktura matematyczna służąca do przedstawiania i badania relacji między obiektami^[3] [4] . W uproszczeniu graf to zbiór wierzchołków, które mogą być połączone krawędziami w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków^[5].

Zobacz też: inne znaczenia wyrazu „graf”.

Wierzchołki grafu mogą być numerowane i czasem stanowią reprezentację jakichś obiektów, natomiast krawędzie mogą wówczas obrazować relacje między takimi obiektami^[6]. Wierzchołki należące do krawędzi nazywane są jej końcami^[7]. Krawędzie mogą mieć wyznaczony kierunek, a graf zawierający takie krawędzie nazywany jest grafem skierowanym^[8] lub orgrafem^[9]. Krawędź grafu może posiadać wagę, to znaczy przypisaną liczbę, która określa na przykład odległość między wierzchołkami (jeśli np. graf jest reprezentacją połączeń między miastami)^[10]. W grafie skierowanym wagi mogą być zależne od kierunku przechodzenia przez krawędź (np. jeśli graf reprezentuje trud poruszania się po jakimś terenie, to droga pod górkę będzie miała przypisaną większą wagę niż z górki)^[11].

Za pierwszego teoretyka i badacza grafów uważa się^[12] szwajcarskiego matematyka i fizyka Leonarda Eulera, który rozstrzygnął zagadnienie mostów królewieckich. Pierwsze użycie określenia „graf” przypisywane jest Jamesowi Josephowi Sylvesterowi – matematykowi angielskiego pochodzenia^[13].

Zastosowanie grafów

Zastosowanie grafów

Drzewo binarne

Niedeterministyczny automat skończony

Graficzne przedstawienie cząsteczki propanu^[14]

Za najstarszy przykład zastosowania grafów w rozwiązaniu zadanego problemu uznaje się^[12] zagadnienie mostów królewieckich, opis którego opublikował w 1736 roku Leonhard Euler^[15]:

→ →

Grafy mogą służyć do praktycznych zastosowań (także z pomocą komputerów)^[16] w wielu różnorodnych problemach^[8][17], np.: sieć dróg z wierzchołkami reprezentującymi skrzyżowania i krawędziami przedstawiającymi ulice^[8], sieć pomieszczeń i korytarzy w budynkach^[18], dzięki czemu możliwe jest komputerowe wynajdywanie najlepszej drogi ze swojego obecnego położenia do pożądanego celu. Algorytmy grafowe stanowią istotną część programów obsługujących urządzenia GPS^[19]. System sztucznej inteligencji w niektórych grach komputerowych musi odszukać dla sterowanych przez program postaci najlepszą drogę, która pozwoli zaatakować przeciwnika. Zagadnienie to może być rozwiązane w oparciu o własności grafów^[20]. Przedstawienie w formie grafów sieci komputerowych pozwala na stworzenie oprogramowania usprawniającego trasowanie w Internecie. W dużych organizacjach realizację zlecanych przez klientów zadań można przedstawić w postaci grafów, dzięki czemu możliwe jest zwiększenie wydajności: wierzchołki mogą reprezentować pracowników, a krawędzie grafu – przepływ zadań^[21]. Za pomocą związanych z grafami pojęć można opisywać też m.in. rysunki obwodów, schematy blokowe, ponieważ przedstawiają one połączenia lub relacje, zachodzące między różnymi fragmentami wykresu^[8].

Drzewa grafowe przydatne są w praktycznej reprezentacji różnego rodzaju hierarchii^[22]. Mistrzostwa sportowe czy drzewo genealogiczne mogą być w przejrzysty sposób opisane przez drzewa binarne^[19]. Do tworzenia kodów Huffmana można wykorzystać drzewa binarne z wagami^[23]. Idea działania danego niedeterministycznego automatu skończonego może być w przejrzysty sposób pokazana przez odpowiedni graf^[24].

Wzrasta również znaczenie i wykorzystanie teorii grafów w dziedzinach takich, jak chemia, lingwistyka, geografia, architektura i inne^[16].

Definicje

Graf nieskierowany

Graf skierowany

Graf z wagami^[25]

Multigraf^[26]

Różni autorzy stosują bardzo odmienne sposoby definiowania i oznaczania elementów grafu^[7][27].

Graf

Jedną z definicji grafu jest: graf (nieskierowany) ${\displaystyle G}$ składa się z dwóch zbiorów: ${\displaystyle V}$ oraz ${\displaystyle E,}$ przy czym ${\displaystyle V}$ jest niepustym zbiorem, którego elementy nazywane są wierzchołkami, a ${\displaystyle E}$ jest rodziną dwuelementowych podzbiorów zbioru wierzchołków ${\displaystyle V,}$ zwanych krawędziami^[28]: ${\displaystyle E\subseteq \{\{u,v\}:u,v\in V\}.}$ Definicja ta nie wymaga, by ${\displaystyle V}$ i ${\displaystyle E}$ były skończone. W praktyce rozważa się także grafy o nieskończonej liczbie wierzchołków – wtedy liczba krawędzi może być zarówno skończona, jak i nieskończona^[7].

Graf skierowany

Osobny artykuł: Graf skierowany.

Graf skierowany lub inaczej digraf^[8] składa się z dwóch zbiorów – niepustego zbioru wierzchołków ${\displaystyle V}$ oraz rodziny ${\displaystyle A}$ par uporządkowanych elementów zbioru ${\displaystyle V,}$ zwanych krawędziami lub łukami grafu skierowanego. Kolejność wierzchołków w parze wyznacza kierunek krawędzi – w przypadku pary ${\displaystyle v,u}$ łuk biegnie z wierzchołka ${\displaystyle v}$ do wierzchołka ${\displaystyle u}$^[29]. Podobnie, jak w przypadku grafu nieskierowanego, definicja ta ma sens zarówno wtedy, gdy zbiory ${\displaystyle V}$ lub ${\displaystyle A}$ są skończone, jak i nieskończone^[30].

Graf mieszany

Osobny artykuł: Graf mieszany.

Graf mieszany to uporządkowana trójka grafu ${\displaystyle G=(V,E,A)}$ gdzie zbiory ${\displaystyle V,}$ ${\displaystyle E,}$ ${\displaystyle A}$ są zdefiniowane jak wyżej, czyli zawiera jednocześnie krawędzie skierowane i nieskierowane^[31].

Grafy z wagami

Przez zdefiniowanie funkcji z ${\displaystyle V,}$ ${\displaystyle E}$ lub ${\displaystyle A}$ w pewien zbiór ${\displaystyle X}$ można przypisać krawędziom lub wierzchołkom etykiety, służące do przechowywania dodatkowych informacji^[32]. Etykiety liczbowe są często nazywane wagami^[33], a graf grafem z wagami (grafem z ważeniem, grafem ważonym).

W grafie ważonym krawędziowo zbiór tworzący graf jest rozszerzony o funkcję ${\displaystyle \delta \colon E\to K}$ taką, że dla każdej krawędzi ${\displaystyle e\in E,}$ ${\displaystyle \delta (e)}$ jest wagą danej krawędzi^[11].

Grafem ważonym wierzchołkowo nazywa się graf ${\displaystyle G_{\omega }:=(V,E,\omega ),}$ w którym ${\displaystyle \omega \colon V\to \mathbb {N} }$ jest funkcją przypisującą każdemu wierzchołkowi pewną liczbę naturalną nazywaną wagą wierzchołka. Graf taki oznacza się przez ${\displaystyle G_{\omega }}$ (lub po prostu ${\displaystyle G,}$ a to, że jest ważony wynika z kontekstu), natomiast wagę wierzchołka ${\displaystyle v}$ oznacza się przez ${\displaystyle \omega (v)}$^[34].

Warianty definicji

W wielu zastosowaniach podstawowe definicje grafów nie są wystarczające, dlatego wprowadza się pewne modyfikacje^[7]. Na przykład aby wprowadzić pętlę, czyli krawędź, której oba końce są tym samym wierzchołkiem, w definicji grafu nieskierowanego należy dopuścić zbiory jednoelementowe ${\displaystyle \{v\}}$^[27] albo użyć dwuelementowego multizbioru ${\displaystyle \{v,v\}.}$ W grafie skierowanym pętla jest naturalnie reprezentowana przez parę ${\displaystyle v,v}$^[7].

Czasami potrzebna jest możliwość połączenia dwóch wierzchołków przy pomocy więcej niż jednej krawędzi (w przypadku grafu skierowanego chodzi o łuki o takim samym zwrocie). Graf, który na to pozwala, nazywany jest multigrafem^[35]. Uzyskuje się go np. przez zdefiniowanie ${\displaystyle E}$ lub ${\displaystyle A}$ jako multizbioru^[7].

Przykłady odmiennych sposobów definiowania grafu

Graf może być też określony jako niepusty zbiór wierzchołków i dana na nim relacja binarna ${\displaystyle R}$ taka, że dla dowolnych wierzchołków ${\displaystyle v}$ i ${\displaystyle u}$ ${\displaystyle vRu}$ zachodzi wtedy i tylko wtedy, gdy istnieje krawędź łącząca ${\displaystyle v}$ i ${\displaystyle u}$^[30]. Dla grafów nieskierowanych relacja ta jest symetryczna^[36] .

Graf nieskierowany można też definiować^[7] jako trójkę ${\displaystyle G=(V,E,\gamma ),}$ gdzie ${\displaystyle V}$ jest niepustym zbiorem, którego elementy nazywają się wierzchołkami, ${\displaystyle E}$ jest rodziną dwuelementowych podzbiorów zbioru wierzchołków ${\displaystyle V}$ zwanych krawędziami: ${\displaystyle E\subseteq \{\{u,v\}:u,v\in V,u\neq v\},}$ a ${\displaystyle \Upsilon }$ jest funkcją ze zbioru ${\displaystyle E}$ w zbiór ${\displaystyle \{u,v\}:u,v\in V(G)\}}$ wszystkich podzbiorów jedno- lub dwuelementowych zbioru ${\displaystyle V.}$ Wówczas jeżeli ${\displaystyle e}$ jest krawędzią grafu, to kończy się ona wierzchołkami ${\displaystyle u,v\in V,}$ gdy ${\displaystyle \gamma (e)=\{u,v\},}$ i jest pętlą wierzchołka ${\displaystyle v,}$ gdy ${\displaystyle \gamma (e)=\{v\}.}$

Graf skierowany określa się też jako trójkę ${\displaystyle G=(V,E,\gamma ),}$ gdzie zbiory ${\displaystyle V}$ i ${\displaystyle E}$ są zdefiniowane analogicznie do grafów nieskierowanych a ${\displaystyle \gamma }$ jest funkcją ze zbioru krawędzi w zbiór uporządkowanych par (kwadrat kartezjański, czyli iloczyn kartezjański zbioru ze sobą) wierzchołków – ${\displaystyle \gamma \colon E\to V\times V.}$ Jeśli ${\displaystyle e}$ jest krawędzią grafu ${\displaystyle (e\in A)}$ oraz ${\displaystyle \Upsilon (e)=(p,q),}$ to ${\displaystyle p}$ nazywane jest początkiem krawędzi ${\displaystyle e,}$ a ${\displaystyle q}$ – końcem krawędzi ${\displaystyle e}$ i mówi się, że ${\displaystyle e}$ biegnie od ${\displaystyle p}$ do ${\displaystyle q}$^[30].

Inne typy grafów

Grafy nieskończone

Przykład grafu nieskończonego – krata kwadratowa^[37]

Przykład grafu nieskończonego – krata trójkątna^[37]

Grafy nieskończone

Formalne definicje grafu nie wymagają, by zbiory krawędzi czy wierzchołków były skończone, jednak w literaturze źródłowej zazwyczaj przyjmuje się uproszczenie, że zbiory ${\displaystyle E(G)}$ oraz ${\displaystyle V(G)}$ są skończone^[30][38].

W przypadku nieskończonego zbioru wierzchołków przy skończonej ilości krawędzi otrzymuje się graf o nieskończonej ilości wierzchołków izolowanych. W przypadku skończonej ilości wierzchołków i nieskończonej ilości krawędzi otrzyma się graf o nieskończonej ilości pętli lub krawędzi wielokrotnych. W obu przypadkach są to grafy skończone. Graf nieskończony ${\displaystyle G}$ składa się z nieskończonego zbioru wierzchołków ${\displaystyle V(G)}$ oraz nieskończonej rodziny ${\displaystyle E(G)}$ krawędzi grafu. Gdy zarówno ${\displaystyle V(G),}$ jak i ${\displaystyle E(G)}$ są przeliczalne, graf ${\displaystyle G}$ nazywa się grafem przeliczalnym. Wiele pojęć z zakresu własności grafów (np. ścieżka^[37], planarność, spójność^[38]) można z powodzeniem rozszerzyć na grafy nieskończone. Do grafów nieskończonych należą m.in.:

• graf lokalnie skończony – graf nieskończony, którego każdy wierzchołek posiada skończony stopień,
• graf lokalnie przeliczalny – graf nieskończony, którego każdy wierzchołek ma przeliczalny stopień^[38].

Graf abstrakcyjny

Jeśli nazwać węzłami elementy niepustego zbioru ${\displaystyle P=\{p_{1},\dots ,p_{n_{p}}\},}$ to dla każdej pary węzłów ${\displaystyle \{p_{i},p_{j}\}}$ zachodzi ${\displaystyle \{p_{i},p_{j}\}\equiv \{p_{j},p_{i}\},}$ jeśli ${\displaystyle \{p_{i},p_{j}\}}$ są elementami iloczynu kartezjańskiego ${\displaystyle P\otimes P}$ (są wtedy nierozróżnialne). Gdy ${\displaystyle \{p_{i},p_{j}\}}$ są elementami zbioru ${\displaystyle P\times P,}$ wtedy wprowadza się między nimi rozróżnienie. Dodatkowo niech ${\displaystyle L=\{l_{1},\dots ,l_{n_{l}}\}}$ będzie zbiorem, który może być pusty, a którego elementy nazywane będą połączeniami. Abstrakcyjny graf (ukierunkowany lub nieukierunkowany) jest zadany strukturą matematyczną ${\displaystyle G(P,L,f)}$ ze zbiorami węzłów ${\displaystyle P,}$ połączeń ${\displaystyle L}$ oraz odwzorowaniem incydentnym ${\displaystyle f,}$ zdefiniowanym pomiędzy połączeniami ${\displaystyle l_{i}\in L,}$ oraz parami nierozróżnialnych węzłów ${\displaystyle \{p_{j},p_{k}\}\in P\otimes P}$ lub rozróżnialnych ${\displaystyle \{p_{j},p_{k}\}\in P\times P}$^[39] .

Graf geometryczny

Dla każdego grafu istnieje nieskończenie wiele^[40] przedstawiających go rysunków^[41] , gdyż klasyczne definicje grafów nie uwzględniają pojęć z zakresu geometrii, takich jak miara kątów, długości odcinków itp^[40]. Czasami jednak rozważane są w przypadku grafów własności stricte geometryczne (współrzędne geometryczne wierzchołków, tylko proste krawędzie, zmieszczenie się w pewnej przestrzeni itp.)^[40][42]. Grafy, rozpatrywane jako figury w przestrzeni (w której są one „zanurzone” i która nadaje im cechy charakterystyczne dla danej przestrzeni), nazywa się grafami geometrycznymi^[40][43]. Nadanie grafom właściwości geometrycznych może odbyć się, na przykład, poprzez wprowadzenie długości krawędzi jako spełniającej postulaty metryki dwuargumentowej funkcji ze zbioru krawędzi grafu w zbiór dodatnich liczb rzeczywistych^[44].

Pojęcia służące do opisu grafów

Wszystkie drogi w tym grafie są proste, nie ma cykli

Graf i jego drzewo spinające (po prawej stronie)^[45]

Pętla

Graf, posiadający siedem składowych, z których dwie są izolowanymi wierzchołkami^[46]

Graf o ścianach ${\displaystyle f_{1},f_{2},f_{3}}$ oraz ${\displaystyle f_{4}}$ – ściana ${\displaystyle f_{4}}$ jest ścianą nieskończoną^[47]

Alfabetyczna lista definicji

• Acentryczność wierzchołka grafu – maksymalna odległość wierzchołka do innych wierzchołków grafu^[48]  lub inaczej długość najdłuższej ścieżki prostej zaczynającej się w danym wierzchołku^[49] .
• Automorfizm grafu – wzajemnie jednoznaczne przekształcenie ${\displaystyle \varphi }$ zbioru wierzchołków grafu prostego w ten sam zbiór takie, że wierzchołki ${\displaystyle \varphi (v)}$ oraz ${\displaystyle \varphi (w)}$ są sąsiednie wtedy i tylko wtedy, gdy ${\displaystyle v}$ i ${\displaystyle w}$ są sąsiednie^[50].
• Centrum grafu – wierzchołek grafu spójnego taki, że największa z odległości od centrum do innych wierzchołków grafu jest najmniejsza^[51].
• Cykl – zamknięta droga prosta ${\displaystyle e_{a},e_{b},\dots ,e_{z},}$ taka że krawędź ${\displaystyle e_{z}}$ kończy się w początkowym wierzchołku drogi^[52].
• Droga – wyznaczona przez krawędzie trasa, polegająca na podróżowaniu od wierzchołka do wierzchołka po łączących je krawędziach^[52]. Jeżeli przez ${\displaystyle e_{i}}$ oznaczy się ${\displaystyle i}$-tą krawędź grafu, to droga może być jednoznacznie zapisana jako ${\displaystyle e_{a},e_{b},\dots ,e_{z}}$^[53][54].
• Droga prosta – droga niezawierająca dwóch tych samych krawędzi^[55].
• Długość drogi/ścieżki – liczba krawędzi/wierzchołków, tworzących daną drogę/ścieżkę^[56].
• Droga acykliczna – droga, niezawierająca cyklu^[52].
• Drzewo spinające grafu – spójny, acykliczny podgraf danego grafu, zawierający wszystkie jego wierzchołki^[53].
• Gęstość grafu – stosunek liczby krawędzi do największej możliwej liczby krawędzi^[57] . Używa się również określeń: graf gęsty, jeżeli ma on dużo krawędzi w stosunku do liczby wierzchołków, i podobnie graf rzadki, jeżeli ma on mało krawędzi w stosunku do liczby wierzchołków, przy czym znaczenie słów mało i dużo może zależeć od kontekstu^[58] .
• Klika – podzbiór wierzchołków danego grafu wraz z krawędziami je łączącymi, takich, że każde dwa wierzchołki tego podzbioru są sąsiadami^[59][60]  (czyli podgraf pełny^[61]).
• Kolorowanie grafu – nadanie każdemu wierzchołkowi koloru tak, by żadne sąsiadujące ze sobą wierzchołki nie były pokolorowane tym samym kolorem^[62].
• Krawędzie sąsiednie – krawędzie kończące się w jednym wierzchołku^[63]. W przypadku grafów skierowanych zazwyczaj wymagana jest zgodność kierunków krawędzi, tj. dwie krawędzie są sąsiednie, jeżeli odpowiednio kończą się i zaczynają w tym samym wierzchołku^[52].
• Krawędź/wierzchołek krytyczny – krawędź/wierzchołek, po usunięciu której/którego ze zbioru pokrywającego zmniejsza się indeks pokrycia krawędziowego/wierzchołkowego^[64].
• Liczba chromatyczna – najmniejsza liczba kolorów potrzebna do prawidłowego pokolorowania grafu