Graf (matematyka)

Szablon:Inne znaczenia Graf – podstawowy obiekt rozważań teorii grafówSzablon:OdnSzablon:Odn, struktura matematyczna służąca do przedstawiania i badania relacji między obiektamiSzablon:OdnSzablon:Odn. 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ówSzablon:Odn.

Wierzchołki grafu mogą być numerowane i czasem stanowią reprezentację jakichś obiektów, natomiast krawędzie mogą wówczas obrazować relacje między takimi obiektamiSzablon:Odn. Wierzchołki należące do krawędzi nazywane są jej końcamiSzablon:Odn. Krawędzie mogą mieć wyznaczony kierunek, a graf zawierający takie krawędzie nazywany jest grafem skierowanymSzablon:Odn lub orgrafemSzablon:Odn. 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)Szablon:Odn. 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)Szablon:Odn.

Za pierwszego teoretyka i badacza grafów uważa sięSzablon:Odn 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 pochodzeniaSzablon:Odn.

Zastosowanie grafów

Szablon:Galeria Za najstarszy przykład zastosowania grafów w rozwiązaniu zadanego problemu uznaje sięSzablon:Odn zagadnienie mostów królewieckich, opis którego opublikował w 1736 roku Leonhard EulerSzablon:Odn:

→ →

Grafy mogą służyć do praktycznych zastosowań (także z pomocą komputerów)Szablon:Odn w wielu różnorodnych problemachSzablon:OdnSzablon:Odn, np.: sieć dróg z wierzchołkami reprezentującymi skrzyżowania i krawędziami przedstawiającymi uliceSzablon:Odn, sieć pomieszczeń i korytarzy w budynkachSzablon:Odn, 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 GPSSzablon:Odn. 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ówSzablon:Odn. 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ńSzablon:Odn. 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 wykresuSzablon:Odn.

Drzewa grafowe przydatne są w praktycznej reprezentacji różnego rodzaju hierarchiiSzablon:Odn. Mistrzostwa sportowe czy drzewo genealogiczne mogą być w przejrzysty sposób opisane przez drzewa binarneSzablon:Odn. Do tworzenia kodów Huffmana można wykorzystać drzewa binarne z wagamiSzablon:Odn. Idea działania danego niedeterministycznego automatu skończonego może być w przejrzysty sposób pokazana przez odpowiedni grafSzablon:Odn.

Wzrasta również znaczenie i wykorzystanie teorii grafów w dziedzinach takich, jak chemia, lingwistyka, geografia, architektura i inneSzablon:Odn.

Definicje

Graf nieskierowany

Graf skierowany

Graf z wagamiSzablon:Odn

MultigrafSzablon:Odn

Różni autorzy stosują bardzo odmienne sposoby definiowania i oznaczania elementów grafuSzablon:OdnSzablon:Odn.

Graf

Jedną z definicji grafu jest: graf (nieskierowany) $G$ składa się z dwóch zbiorów: $V$ oraz $E,$ przy czym $V$ jest niepustym zbiorem, którego elementy nazywane są wierzchołkami, a $E$ jest rodziną dwuelementowych podzbiorów zbioru wierzchołków $V,$ zwanych krawędziami: $E\subseteq \{\{u,v\}:u,v\in V\}.$ Definicja ta nie wymaga, by $V$ i $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ńczonaSzablon:Odn.

Graf skierowany

Szablon:Osobny artykuł Graf skierowany lub inaczej digrafSzablon:Odn składa się z dwóch zbiorów – niepustego zbioru wierzchołków $V$ oraz rodziny $A$ par uporządkowanych elementów zbioru $V,$ zwanych krawędziami lub łukami grafu skierowanego. Kolejność wierzchołków w parze wyznacza kierunek krawędzi – w przypadku pary $v,u$ łuk biegnie z wierzchołka $v$ do wierzchołka $u$Szablon:Odn. Podobnie, jak w przypadku grafu nieskierowanego, definicja ta ma sens zarówno wtedy, gdy zbiory $V$ lub $A$ są skończone, jak i nieskończoneSzablon:Odn.

Graf mieszany

Szablon:Osobny artykuł Graf mieszany to uporządkowana trójka grafu $G=(V,E,A)$ gdzie zbiory $V,$ $E,$ $A$ są zdefiniowane jak wyżej, czyli zawiera jednocześnie krawędzie skierowane i nieskierowaneSzablon:Odn.

Grafy z wagami

Przez zdefiniowanie funkcji z $V,$ $E$ lub $A$ w pewien zbiór $X$ można przypisać krawędziom lub wierzchołkom etykiety, służące do przechowywania dodatkowych informacjiSzablon:Odn. Etykiety liczbowe są często nazywane wagamiSzablon:Odn, 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ę $\delta :E\to K$ taką, że dla każdej krawędzi $e\in E,$ $\delta (e)$ jest wagą danej krawędziSzablon:Odn.

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

Warianty definicji

W wielu zastosowaniach podstawowe definicje grafów nie są wystarczające, dlatego wprowadza się pewne modyfikacjeSzablon:Odn. 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 $\{v\}$Szablon:Odn albo użyć dwuelementowego multizbioru $\{v,v\}.$ W grafie skierowanym pętla jest naturalnie reprezentowana przez parę $v,v$Szablon:Odn.

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 multigrafemSzablon:Odn. Uzyskuje się go np. przez zdefiniowanie $E$ lub $A$ jako multizbioruSzablon:Odn.

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 $R$ taka, że dla dowolnych wierzchołków $v$ i $u$ $vRu$ zachodzi wtedy i tylko wtedy, gdy istnieje krawędź łącząca $v$ i $u$Szablon:Odn. Dla grafów nieskierowanych relacja ta jest symetrycznaSzablon:Odn.

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

Graf skierowany określa się też jako trójkę $G=(V,E,\gamma ),$ gdzie zbiory $V$ i $E$ są zdefiniowane analogicznie do grafów nieskierowanych a $\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 – $\gamma :E\to V\times V.$ Jeśli $e$ jest krawędzią grafu $(e\in A)$ oraz $\mathrm{{\rm Y}}(e)=(p,q),$ to $p$ nazywane jest początkiem krawędzi $e,$ a $q$ – końcem krawędzi $e$ i mówi się, że $e$ biegnie od $p$ do $q$Szablon:Odn.

Inne typy grafów

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 $E(G)$ oraz $V(G)$ są skończoneSzablon:OdnSzablon:Odn.

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 $G$ składa się z nieskończonego zbioru wierzchołków $V(G)$ oraz nieskończonej rodziny $E(G)$ krawędzi grafu. Gdy zarówno $V(G),$ jak i $E(G)$ są przeliczalne, graf $G$ nazywa się grafem przeliczalnym. Wiele pojęć z zakresu własności grafów (np. ścieżkaSzablon:Odn, planarność, spójnośćSzablon:Odn) 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ńSzablon:Odn.

Graf abstrakcyjny

Jeśli nazwać węzłami elementy niepustego zbioru $P=\{p_1,\dots ,p_{n_p}\},$ to dla każdej pary węzłów $\{p_i,p_j\}$ zachodzi $\{p_i,p_j\}\equiv \{p_j,p_i\},$ jeśli $\{p_i,p_j\}$ są elementami iloczynu kartezjańskiego $P\otimes P$ (są wtedy nierozróżnialne). Gdy $\{p_i,p_j\}$ są elementami zbioru $P\times P,$ wtedy wprowadza się między nimi rozróżnienie. Dodatkowo niech $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ą $G(P,L,f)$ ze zbiorami węzłów $P,$ połączeń $L$ oraz odwzorowaniem incydentnym $f,$ zdefiniowanym pomiędzy połączeniami $l_i\in L,$ oraz parami nierozróżnialnych węzłów $\{p_j,p_k\}\in P\otimes P$ lub rozróżnialnych $\{p_j,p_k\}\in P\times P$Szablon:Odn.

Graf geometryczny

Dla każdego grafu istnieje nieskończenie wieleSzablon:Odn przedstawiających go rysunkówSzablon:Odn, gdyż klasyczne definicje grafów nie uwzględniają pojęć z zakresu geometrii, takich jak miara kątów, długości odcinków itpSzablon:Odn. 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.)Szablon:OdnSzablon:Odn. 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 geometrycznymiSzablon:OdnSzablon:Odn. 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 rzeczywistychSzablon:Odn.

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)Szablon:Odn

Pętla

Graf, posiadający siedem składowych, z których dwie są izolowanymi wierzchołkamiSzablon:Odn

Graf o ścianach $f_1,f_2,f_3$ oraz $f_4$ – ściana $f_4$ jest ścianą nieskończonąSzablon:Odn

Alfabetyczna lista definicji

• Acentryczność wierzchołka grafu – maksymalna odległość wierzchołka do innych wierzchołków grafuSzablon:Odn lub inaczej długość najdłuższej ścieżki prostej zaczynającej się w danym wierzchołkuSzablon:Odn.
• Automorfizm grafu – wzajemnie jednoznaczne przekształcenie $\phi$ zbioru wierzchołków grafu prostego w ten sam zbiór takie, że wierzchołki $\phi (v)$ oraz $\phi (w)$ są sąsiednie wtedy i tylko wtedy, gdy $v$ i $w$ są sąsiednieSzablon:Odn.
• Centrum grafu – wierzchołek grafu spójnego taki, że największa z odległości od centrum do innych wierzchołków grafu jest najmniejszaSzablon:Odn.
• Cykl – zamknięta droga prosta $e_a,e_b,\dots ,e_z,$ taka że krawędź $e_z$ kończy się w początkowym wierzchołku drogiSzablon:Odn.
• Droga – wyznaczona przez krawędzie trasa, polegająca na podróżowaniu od wierzchołka do wierzchołka po łączących je krawędziachSzablon:Odn. Jeżeli przez $e_i$ oznaczy się $i$-tą krawędź grafu, to droga może być jednoznacznie zapisana jako $e_a,e_b,\dots ,e_z$Szablon:OdnSzablon:Odn.
• Droga prosta – droga niezawierająca dwóch tych samych krawędziSzablon:Odn.
• Długość drogi/ścieżki – liczba krawędzi/wierzchołków, tworzących daną drogę/ścieżkęSzablon:Odn.
• Droga acykliczna – droga, niezawierająca cykluSzablon:Odn.
• Drzewo spinające grafu – spójny, acykliczny podgraf danego grafu, zawierający wszystkie jego wierzchołkiSzablon:Odn.
• Gęstość grafu – stosunek liczby krawędzi do największej możliwej liczby krawędziSzablon:Odn. 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 kontekstuSzablon:Odn.
• 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ąsiadamiSzablon:OdnSzablon:Odn (czyli podgraf pełnySzablon:Odn).
• Kolorowanie grafu – nadanie każdemu wierzchołkowi koloru tak, by żadne sąsiadujące ze sobą wierzchołki nie były pokolorowane tym samym koloremSzablon:Odn.
• Krawędzie sąsiednie – krawędzie kończące się w jednym wierzchołkuSzablon:Odn. 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łkuSzablon:Odn.
• 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łkowegoSzablon:Odn.
• Liczba chromatyczna – najmniejsza liczba kolorów potrzebna do prawidłowego pokolorowania grafuSzablon:Odn.
• Most – krawędź, po usunięciu której wzrasta liczba spójnych składowych grafuSzablon:Odn.
• Nadgraf grafu $H$ – taki graf, że $H$ jest jego podgrafemSzablon:Odn.
• Odległość – liczba krawędzi w najkrótszej ścieżce łączącej dane dwa wierzchołki.
• Pętla – krawędź zaczynająca i kończąca się w tym samym wierzchołkuSzablon:Odn.
• Podgraf grafu $H$ – graf $G$ uzyskany poprzez usunięcie części wierzchołków z $H,$ wraz z kończącymi się w nich krawędziamiSzablon:Odn.
• Rozmiar grafu $G$ – liczbę krawędzi grafu, oznaczonych $G$Szablon:Odn.
• Rząd grafu $G$ – liczba wierzchołków grafu, oznaczonych $G$Szablon:Odn.
• Graf r-regularny – graf, w którym każdy wierzchołek grafu jest stopnia $r$Szablon:Odn.
• Sąsiad – dwa wierzchołki są sąsiadami, jeśli istnieje krawędź pomiędzy nimiSzablon:Odn.
• Spójna składowa grafu $G$ – możliwie największy spójny podgraf grafu $G.$ Graf spójny ma jedną spójną składowąSzablon:Odn.
• Stopień wierzchołka $v$ – liczba kończących się w wierzchołku krawędziSzablon:Odn. Oznaczenie: $\mathrm{deg}(v)$Szablon:Odn. W przypadku grafów skierowanych mówi się o stopniach wejściowym i wyjściowym – $\mathrm{indeg}(v),$ $\mathrm{outdeg}(v)$Szablon:Odn
• Ściana – obszar zamknięty, wyznaczony przez krawędzie grafu (tzw. krawędzie tworzące ścianę)Szablon:Odn. Z pojęciem ściany ściśle powiązane jest twierdzenie EuleraSzablon:Odn. Za ścianę uważa się też nieskończony obszar znajdujący się na zewnątrz grafu (a więc każdy graf ma co najmniej jedną ścianę)Szablon:Odn.
• Ścieżka – intuicyjnie jest bardzo podobna do drogi, z tym, że jest wyznaczona przez wierzchołki, tj. można ją opisać poprzez ciąg wierzchołków $v_a,v_b,\dots ,v_z$Szablon:OdnSzablon:Odn.
• Ścieżka prosta – ścieżka wyznaczona tak, by żaden wierzchołek na trasie nie powtarzał sięSzablon:Odn.
• Ścieżka zamknięta – ścieżka $v_a,v_b,\dots ,v_z,v_a,$ czyli kończąca się w początkowym wierzchołkuSzablon:Odn.
• Usunięcie wierzchołka – wymazanie wierzchołka oraz wszystkich kończących się w nim krawędzi z danego grafuSzablon:Odn.
• Waga krawędzi – wartość przypisana każdej krawędzi. Często od grafu reprezentującego np. sieć połączeń komunikacyjnych oczekuje się nie tylko informacji o istniejącym połączeniu (krawędzi lub ścieżki), ale też np. o długości połączeniaSzablon:Odn. Graf taki można wykorzystać np. do wyznaczenia optymalnej ścieżki – w sensie przejechanych kilometrów trasy – lub ogólniej do rozwiązania problemu komiwojażera – wyznaczenia optymalnego rozłożenia kabli w sieciSzablon:Odn, koordynowania wysyłania plików metodą peer-to-peer itp.Szablon:Odn
• Wierzchołek izolowany – wierzchołek o stopniu $0,$ czyli niebędący końcem żadnej krawędziSzablon:Odn.
• Wierzchołek pokrywający krawędź – wierzchołek $v$ pokrywa krawędź $e,$ jeżeli $e$ kończy się w $v.$ W analogiczny sposób definiuje się krawędź pokrywającą dany wierzchołek – krawędź $e$ kryje wierzchołek $v,$ gdy się w nim kończy. Minimalny pokrywający podzbiór krawędzi/wierzchołków – możliwie najmniejszy podzbiór krawędzi/wierzchołków grafu taki, że pokrywają one wszystkie wierzchołki/krawędzie danego grafu. Liczność minimalnego zbioru pokrywającego krawędzi/wierzchołków nazywa się indeksem pokrycia wierzchołkowego/krawędziowego. Wszystkie podzbiory o tej liczności i własności nazywa się pokryciem minimalnym.
• Wierzchołek rozcinający – wierzchołek, po usunięciu którego zwiększa się liczba spójnych składowych grafuSzablon:Odn. Nazywany przegubem tworzy tzw. wąskie gardło grafu, tj. istnieją w grafie dwa wierzchołki takie, że każda łącząca je droga musi przejść przez wierzchołek rozcinającySzablon:Odn.

Oznaczenia formalne

Często dla danego grafu $G$ stosuje się skrócone oznaczenia oparte na alfabecie greckim oraz łacińskimSzablon:OdnSzablon:Odn:

• $n$ lub $V(G)$ – liczba wierzchołków $G$Szablon:OdnSzablon:Odn,
• $m$ lub $E(G)$ – liczba krawędzi $G$Szablon:OdnSzablon:Odn,
• $\delta (G)$ – najmniejszy stopień wierzchołka w $G$Szablon:Odn,
• $\mathrm{\Delta }(G)$ – największy stopień wierzchołka w $G$Szablon:Odn,
• $\chi (G)$ – liczba chromatyczna $G$Szablon:Odn,
• ${\chi }^{\prime }(G)$ – indeks chromatyczny $G$Szablon:Odn,
• $k$ – liczba spójnych składowych $G$Szablon:Odn.

Przykład dla grafu nieskierowanego $G$

Graf nieskierowany

• $V(G)=\{v_1,v_2,v_3,v_4,v_5,v_6\}$
• $E(G)=\{\{v_1,v_2\},\{v_1,v_5\},\{v_5,v_4\},\{v_4,v_6\},$

$\{v_4,v_3\},\{v_3,v_2\},\{v_2,v_5\}\}$

Przykładową ścieżką prostą może być $v_6,v_4,v_5,v_1,$ a cyklem – $v_5,v_4,v_3,v_2,v_5.$ Stopnie wierzchołków są następujące:

• $\mathrm{deg}(v_1)=2$
• $\mathrm{deg}(v_2)=3$
• $\mathrm{deg}(v_3)=2$
• $\mathrm{deg}(v_4)=3$
• $\mathrm{deg}(v_5)=3$
• $\mathrm{deg}(v_6)=1$

Krawędź $\{v_1,v_5\}$ jest sąsiednia z $\{v_5,v_2\},$ ale nie jest z $\{v_2,v_3\}.$ Graf $G$ ma trzy ściany – zewnętrzną oraz dwie wyznaczone odpowiednio przez ścieżki np. $v_2,v_3,v_4,v_5$ i $v_1,v_5,v_2.$ Graf $G$ jest spójny, czyli ma jedną spójną składową. Natomiast podgraf grafu $G$ składający się z wierzchołków $v_1,v_2,v_5,v_6$ i incydentnych z nimi krawędziami ma dwie spójne składowe – cykl $v_1,v_2,v_5,v_1$ i wierzchołek izolowany $v_6.$

Izomorfizm i homeomorfizm grafów

Przykład dwóch grafów izomorficznychSzablon:Odn

Przykład dwóch grafów homeomorficznychSzablon:Odn

Szablon:Osobny artykuł Graficzna reprezentacja grafów (w postaci kropek i łączących je krzywych) jest tylko sposobem przedstawienia relacji zachodzących między wierzchołkami. Dla każdego grafu istnieje nieskończenie wieleSzablon:Odn przedstawiających go jednoznacznie wykresów, rysunkówSzablon:Odn. Właściwości grafów są niezależne od sposobu numerowania wierzchołków, kolejności ich rysowania itp. Grafy różniące się tylko sposobem ich przedstawienia lub indeksami nadanymi wierzchołkom nazywają się izomorficznymiSzablon:Odn.

Dwa grafy są homeomorficzne, jeśli z jednego grafu można otrzymać drugi, zastępując wybrane krawędzie łańcuchami prostymi lub łańcuchy proste pojedynczymi krawędziamiSzablon:Odn.

Klasy grafów

Szablon:Galeria Grafy można podzielić ze względu na różne własności, zazwyczaj zachowane w obrębie izomorfizmów danego grafuSzablon:OdnSzablon:Odn. Niektóre klasy grafów to:

• drzewo – spójny graf acyklicznySzablon:Odn,
• graf acykliczny – graf niezawierający żadnej drogi zamkniętejSzablon:Odn,
• graf cykliczny – regularny graf spójny, którego każdy wierzchołek jest stopnia drugiegoSzablon:Odn,
• graf dwudzielny – graf, którego wierzchołki mogą być podzielone na dwa zbiory, tak by w obrębie jednego zbioru żaden wierzchołek nie był połączony z innymSzablon:Odn,
• graf dwudzielny pełny – graf dwudzielny taki, że każdy wierzchołek z jednego zbioru jest połączony krawędzią z każdym wierzchołkiem ze zbioru drugiego. Pełny graf dwudzielny o $n_1+n_2$ wierzchołkach oznacza się $K_{n_1,n_2}$Szablon:Odn,
• graf eulerowski – graf, posiadający drogę prostą, przechodzącą przez każdą krawędźSzablon:Odn; niebędącym grafem eulereowskim jest graf półeulerowski, w którym istnieje droga, zawierająca każdą krawędź danego grafu,
• graf genusu $g$ – graf, który można narysować bez przecięć (czyli w formie grafu płaskiego) na powierzchni genusu $g,$ ale nie można narysować go bez przecięć na powierzchni genusu $g-1$Szablon:Odn.
• graf hamiltonowski – graf, posiadający ścieżkę prostą, przechodzącą przez każdy wierzchołekSzablon:Odn,
• graf k-dzielny – graf, którego zbiór wierzchołków można podzielić na $k$ parami rozłącznych podzbiorów takich, że żadne dwa węzły, należące do tego samego zbioru, nie są połączone krawędziąSzablon:Odn,
• graf k-dzielny pełny – graf, którego zbiór wierzchołków dzieli się na $k$ niepołączonych między sobą podzbiorów wierzchołków, oraz każdy wierzchołek $v_i$ z $j$-tego przedziału $v_i$ jest połączony z każdym wierzchołkiem z każdego z przedziałów poza $j$Szablon:Odn,
• graf k-spójny – graf, posiadający $k$ spójnych składowychSzablon:Odn,
• graf komórkowy – graf płaski, którego wszystkie ściany są utworzone przez drogi zamknięte tej samej długościSzablon:Odn,
• graf krytyczny – graf, którego każdy wierzchołek/krawędź jest krytyczny/krytycznaSzablon:Odn,
• graf kubiczny – specjalne określenie dla grafów regularnych stopnia $3$Szablon:Odn,
• graf liniowy – graf, otrzymany poprzez usunięcie jednej krawędzi z grafu cyklicznegoSzablon:Odn,
• graf pełny – graf, którego każdy wierzchołek jest połączony bezpośrednio krawędzią z każdym innymSzablon:Odn; graf pełny o $n$ wierzchołkach oznacza się $K_n$Szablon:OdnSzablon:Odn,
• graf planarny – graf, dla którego istnieje graf izomorficzny i który można przedstawić na płaszczyźnie tak, by żadne krawędzie się nie przecinałySzablon:Odn. Kazimierz Kuratowski udowodnił, że grafy pełne $K_5$ i $K_{3,3}$ są nieplanarne oraz że każdy inny graf nieplanarny musi posiadać podgraf homeomorficzny z którymś z tych grafówSzablon:Odn,
• graf platoński – grafy, utworzone z krawędzi i wierzchołków wielościanów foremnychSzablon:Odn,
• graf płaski – izomorficzne przedstawienie grafu takie, że żadne dwie krawędzie się nie przecinająSzablon:Odn,
• graf podstawowy grafu skierowanego – niemal ten sam, co graf płaski, ale nieskierowany, bo bez zwrotów na krawędziachSzablon:Odn,
• graf prosty – graf, niezawierający pętli ani krawędzi wielokrotnychSzablon:Odn, nazywany jest multigrafemSzablon:Odn; z reguły zdanie „$G$ jest grafem” oznacza w domyśle, że $G$ jest grafem prostymSzablon:Odn,
• graf przedziałowy – graf, utworzony ze zbioru odcinków na prostej poprzez przypisanie każdemu odcinkowi wierzchołka i połączenie krawędziami wierzchołków, których odcinki się nakładająSzablon:Odn,
• graf pusty – graf, nieposiadający krawędziSzablon:Odn,
• graf r-regularny – graf, którego każdy wierzchołek jest stopnia $r$Szablon:Odn,
• graf samodopełniający – graf prosty izomorficzny ze swoim własnym dopełnieniem,
• graf spójny – graf, w którym dla każdego wierzchołka istnieje droga do każdego innego wierzchołkaSzablon:Odn,
• graf toroidalny – graf genusu $1$Szablon:Odn,
• k-kostka – regularny graf dwudzielny, którego wierzchołki odpowiadają ciągom $(a_1,a_2,\dots ,a_k),$ że $\mathrm{\forall }i\in <1,k>a_i=0\vee a_i=1,$ i którego wierzchołki połączone są krawędzią wtedy i tylko wtedy, gdy różnią się jednym wyrazem odpowiadającego im ciąguSzablon:Odn,
• koło – graf o $n$ wierzchołkach, utworzony z grafu cyklicznego o $n-1$ wierzchołkach poprzez połączenie nowego wierzchołka z każdym wierzchołkiem w grafie cyklicznymSzablon:Odn,
• las – niespójny graf acyklicznySzablon:Odn,
• turniej – graf skierowany, w którym każde dwa wierzchołki łączy dokładnie jedna krawędźSzablon:Odn.

Operacje na grafach

Grafy dualne. Rysunek tłumaczy, jak zrobić graf dualny do grafu planarnego. Dla grafu nieplanarnego należy znaleźć dwuwymiarową przestrzeń (osadzoną w wielowymiarze), w której ten graf jest planarny, np. K5 nie można bez przecięć narysować na kuli, ale da się na torusie i tam można znaleźć jego graf dualnySzablon:Odn

Operacje binarne

Suma grafów

$G_1\cup G_2=(V_1\cup V_2,E_1\cup E_2)$ – jeżeli dane są dwa grafy $G_1=(V_1,E_1)$ oraz $G_2=(V_2,E_2),$ to ich sumą jest graf, którego zbiór wierzchołków i krawędzi tworzą wszystkie wierzchołki i krawędzie tych grafówSzablon:Odn.

Przecięcie grafów

Przecięcie grafów $G_1\cap G_2=(V_1\cap V_2,E_1\cap E_2)$Szablon:Odn jest definiowane analogicznie do sumy. Jeżeli dane są dwa grafy $G_1=(V_1,E_1)$ i $G_2=(V_2,E_2),$ to ich przecięciem jest graf, którego wierzchołki i krawędzie wchodzą w skład obu tych grafówSzablon:Odn.

Zespolenie grafów

$G_1+G_2=(V_1\cup V_2,E_1\cup E_2\cup \{\{v_1,v_2\}:v_1\in V_1,v_2\in V_2\})$ – zespoleniem grafów $G_1=(V_1,E_1)$ i $G_2=(V_2,E_2)$ nazywa się graf, w którym z każdego wierzchołka $G_1$ poprowadzono krawędzie do każdego wierzchołka $G_2$Szablon:Odn.

Operacje unarne

Graf krawędziowy

Graf krawędziowy grafu prostego $G$ to graf, który dla każdej krawędzi z $G$ ma wierzchołek połączony z wierzchołkami reprezentującymi pozostałe krawędzie sąsiadujące ze sobą w $G$Szablon:Odn. Etapy konstrukcji grafu krawędziowego $L_G:$

1. Jeśli każdej krawędzi $e_i$ grafu $G$ przypisać jednoznacznie węzeł $v_i$ grafu $L_G,$ to
2. Dwa węzły grafu $L_G$ $v_i$ oraz $v_j$ da się połączyć krawędzią wtedy i tylko wtedy, gdy odpowiednie krawędzie $e_i$ oraz $e_j$ w grafie $G$ są do siebie przyległe, tj. kończą się w jednym wierzchołkuSzablon:Odn.

Dopełnienie grafu

Dopełnieniem grafu $G$ nazywa się graf $\bar{G},$ w którym dwa wierzchołki są sąsiednie wtedy i tylko wtedy, gdy nie były sąsiednie w $G.$ Inaczej mówiąc, w dopełnieniu dwa wierzchołki są połączone krawędzią wtedy, gdy nie były połączone w grafie wyjściowymSzablon:Odn.

Graf dualny

Graf dualny grafu $G$ – graf, którego wierzchołki odpowiadają ścianom w $G.$ Wierzchołki te są połączone, jeżeli odpowiednie ściany w $G$ są sąsiednieSzablon:Odn.

Domknięcie przechodnie

Domknięcie przechodnie dowolnych wierzchołków grafu $G$ następuje wtedy i tylko wtedy, gdy pomiędzy wierzchołkami grafu, posiadającego te same wierzchołki co $G,$ istnieje drogaSzablon:Odn.

Algorytmy grafowe

Poprzez pojęcie algorytmu grafowego rozumie się zazwyczaj algorytmy rozwiązujące problemy przedstawione przy użyciu pojęcia grafuSzablon:OdnSzablon:Odn. Szablon:Zobacz kategorię

Przeszukiwanie grafu

Szablon:Osobny artykuł Przez przeszukiwanie lub przechodzenie grafu rozumie się ciąg czynności, polegających na odwiedzeniu w jakiś usystematyzowany sposób wszystkich wierzchołków grafu w celu zebrania potrzebnych informacjiSzablon:Odn. Często podczas przejścia grafu rozwiązuje się już jakiś problem, ale przeważnie jest to tylko wstęp do wykonania właściwego algorytmu grafowegoSzablon:Odn. Najczęściej używane metody przeszukiwania grafów:

Przeszukiwanie wszerz

Przeszukiwanie wszerz polega na odwiedzeniu wszystkich wierzchołków, osiągalnych z danego wierzchołkaSzablon:Odn.

Przeszukiwanie w głąb

Przeszukiwanie w głąb polega na badaniu wszystkich krawędzi, wychodzących z podanego wierzchołka. Po zbadaniu wszystkich krawędzi wychodzących z danego wierzchołka algorytm powraca do wierzchołka, z którego dany wierzchołek został odwiedzonySzablon:Odn.

Sposoby prezentacji grafów

Każdy graf może być jednoznacznie prezentowany na wiele sposobów. Dla percepcji człowieka najwygodniejszy jest rysunek grafuSzablon:Odn, pozostałe sposoby prezentacji wykorzystywane są w komputerachSzablon:OdnSzablon:Odn. Każda z tych prezentacji ma swoje wady i zalety, generalnie ograniczające są dwa warunki – ilość pamięci przeznaczonej na prezentację i jej możliwości szybkiego odpowiadania na pytania, czy między wierzchołkami $v$ i $u$ jest krawędźSzablon:Odn. W przypadku grafów rzadkich listy sąsiedztwa okazują się wystarczająco szybkie by zrezygnować z pamięciożernych tablicSzablon:Odn. Sposobami prezentacji grafów są: rysunek, macierze sąsiedztwa, listy sąsiedztwaSzablon:Odn i macierze incydencjiSzablon:Odn.

Rysunek grafu

Jednym ze sposobów prezentacji grafu jest rysunek grafu, ukazujący wierzchołki i łączące je krawędzieSzablon:Odn. Wierzchołki oznaczane są zazwyczaj kropkamiSzablon:Odn lub kołamiSzablon:Odn, niekiedy zawierającymi indeksy bądź inne dodatkowe informacjeSzablon:OdnSzablon:Odn. Krawędzie prezentowane są krzywymiSzablon:Odn bądź prostymiSzablon:Odn, w przypadku krawędzi ważonych waga umieszczona jest bezpośrednio nad krawędziąSzablon:Odn.

Macierz sąsiedztwa

Szablon:Osobny artykuł Jedną ze struktur danych, umożliwiających przedstawienie skomplikowanego grafu lub jego przechowywanie w pamięci komputera, jest macierz sąsiedztwa, zawierająca dane na temat połączeń między wierzchołkami. Macierz jest rozmiaru $V(G)$ na $V(G),$ wyraz, leżący z $i$-tego wiersza i $j$-tej kolumny, zawiera wartość będącą liczbą krawędzi łączących $i$-ty i $j$-ty wierzchołek. W przypadku grafów prostych wyrazami w macierzy będą wartości boole’owskie – jest krawędź, bądź nie ma krawędziSzablon:Odn. Macierz sąsiedztwa pozwala na prezentację grafów, zawierających krawędzie wielokrotne oraz pętle własne. Aby dowiedzieć się, ile krawędzi łączy wierzchołki $v_{i}i{v}_j,$ wystarczy sprawdzić wartość komórki $A[i,j]$Szablon:Odn. Tak zaimplementowana komputerowa struktura danych gwarantuje, że operacje sprawdzenia, czy $(v_i,v_j)\in E(G),$ dodania oraz usunięcia krawędzi odbywają się w stałym czasie. Do jej wad należy duża ilość potrzebnej pamięci (asymptotyczne tempo wzrostu $O(n^2)$Szablon:Odn) oraz fakt, że czas potrzebny do przejrzenia zbioru krawędzi jest proporcjonalny do kwadratu liczby wierzchołków (złożoność obliczeniowa wynosi $O(n^2)$), zamiast do liczby krawędziSzablon:Odn.

Przykład macierzy sąsiedztwa dla grafu nieskierowanego

Macierz sąsiedztwa	Rys.
$A=\left[\begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 2\\ 0& 1& 0& 1\\ 1& 2& 1& 0\end{array}\right]$	Graf odpowiadający macierzy sąsiedztwaSzablon:Odn. Brązowe cyfry oznaczają numer krawędzi

Lista sąsiedztwa

Drugą popularną reprezentacją grafu są tzw. listy sąsiedztwa – dla każdego wierzchołka zapamiętywana jest lista sąsiadujących z nim wierzchołków. W implementacji tej metody stosuje się listy jednokierunkowe oraz jednowymiarową tablicę wskaźników o rozmiarze $V(G),$ gdzie $i$-ty element tablicy jest wskaźnikiem do początku listy przechowującej sąsiadów $i$-tego wierzchołkaSzablon:Odn. W odróżnieniu od macierzy sąsiedztwa lista sąsiedztwa wymaga ilości pamięci proporcjonalnej do liczby krawędziSzablon:Odn, także przejrzenie całego zbioru krawędzi jest proporcjonalne do jego rozmiaru. W stosunku do macierzy sąsiedztwa większą złożoność mają jednak operacje elementarne – sprawdzenie, czy $\{v_i,v_j\}\in E(G)$ wymaga czasu proporcjonalnego do mniejszego ze stopni wierzchołków, a np. usunięcie krawędzi – do większego z nichSzablon:OdnSzablon:Odn.

Przykład listy sąsiedztwa

Lista sąsiedztwa	Rys.
$u\to v,y$ $v\to u,w,y$ $w\to v,x,y$ $x\to w,y$ $y\to u,v,w,x$	Graf, odpowiadający liście sąsiedztwaSzablon:Odn

Macierz incydencji

Macierz incydencji $M$ wymiaru $V(G)$ na $E(G)$ zawiera informacje takie, że $M_{i,j}=1$ tylko, gdy $j$-ta krawędź kończy się w $i$-tym wierzchołku (czyli jest z nim incydentna)Szablon:Odn. W przeciwnym wypadku $M_{i,j}=0$Szablon:Odn. Jeśli oznaczyć krawędzie przykładowego grafu tak jak na jego rysunku, to macierz incydencji o kolumnach odpowiadającym krawędziom i wierszach odpowiadającym wierzchołkom może wyglądać następującoSzablon:Odn:

Przykład macierzy incydencji

Macierz incydencji	Rys.
$M=\left[\begin{array}{cccccc}1& 0& 0& 1& 0& 0\\ 1& 1& 0& 0& 1& 1\\ 0& 1& 1& 0& 0& 0\\ 0& 0& 1& 1& 1& 1\end{array}\right]$	Graf odpowiadający macierzy incydencji

Uogólnienia

Przykładowy hipergraf

Hipergrafy

Hipergraf jest strukturą podobną do grafuSzablon:Odn, z tą różnicą, że jego krawędź może łączyć więcej niż dwa wierzchołkiSzablon:Odn.

Grafy w teorii modeli

W teorii modeli graf jest szczególnym przypadkiem struktury matematycznejSzablon:Odn.

Grafy a matroidy

Matroidy mogą być rozważane jako uogólnienie pojęcia grafuSzablon:Odn, a pojęcia grafowe rozważane w odniesieniu do pojęć teorii matroidów mogą być przedstawione w prostszy sposóbSzablon:Odn. Niech dany będzie dowolny graf $G=(V,E).$ Zbiór $E$ krawędzi grafu można rozważać jako nośnik matroidu. Zbiorami niezależnymi będą te jego podzbiory, które nie zawierają cyklu, tj. drzewa oraz lasySzablon:Odn.

Linki zewnętrzne

• Szablon:Cytuj
• Szablon:Cytuj – Aplety obrazujące niektóre algorytmy teorii grafów.
• Szablon:Cytuj