Tekst źródłowy strony Graf (matematyka)

{{inne znaczenia|2=[[graf|inne znaczenia wyrazu „graf”]]}}
'''Graf''' – podstawowy obiekt rozważań [[teoria grafów|teorii grafów]]{{odn|Reinhard Diestel|s = 1}}{{odn|Adrian Horzyk}}, [[struktura matematyczna]] służąca do przedstawiania i badania relacji między obiektami{{odn|Ramsey Young, Brian Sandall}}{{odn|''Graphs and Networks''}}. W uproszczeniu graf to zbiór [[Wierzchołek (teoria grafów)|wierzchołków]], które mogą być połączone [[Krawędź grafu|krawędziami]] w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków{{odn|Robin J. Wilson|s=11}}.

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{{odn|Robin J. Wilson|s=12}}. Wierzchołki należące do krawędzi nazywane są jej końcami{{odn|Kenneth A. Ross, Charles R.B. Wright|s=147}}. Krawędzie mogą mieć wyznaczony kierunek, a graf zawierający takie krawędzie nazywany jest [[graf skierowany|grafem skierowanym]]{{odn|Kenneth A. Ross, Charles R.B. Wright|s=142}} lub orgrafem{{odn|Juliusz Lech Kulikowski|s=39}}. Krawędź grafu może posiadać [[Waga (matematyka)|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){{odn|Kenneth A. Ross, Charles R.B. Wright|s=373}}. 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){{odn|Robin J. Wilson|s=138}}.

Za pierwszego teoretyka i badacza grafów uważa się{{odn|Kenneth A. Ross, Charles R.B. Wright|s=140}} szwajcarskiego matematyka i fizyka [[Leonhard Euler|Leonarda Eulera]], który rozstrzygnął [[zagadnienie mostów królewieckich]]. Pierwsze użycie określenia „graf” przypisywane jest [[James Joseph Sylvester|Jamesowi Josephowi Sylvesterowi]] – matematykowi [[Wielka Brytania|angielskiego]] pochodzenia{{odn|Jonathan L. Gross, Jay Yellen|s=35}}.

== Zastosowanie grafów ==
{{Galeria
|Nazwa            = Zastosowanie grafów
|wielkość         = 200
|Plik:Binary tree fills.svg|Drzewo binarne
|Plik:NFASimpleExample.svg|Niedeterministyczny automat skończony
|Plik:Propan-Valenz-Winkel.svg|Graficzne przedstawienie cząsteczki [[propan]]u{{odn|Robin J. Wilson|s=17}}
}}
Za najstarszy przykład zastosowania grafów w rozwiązaniu zadanego problemu uznaje się{{odn|Kenneth A. Ross, Charles R.B. Wright|s=140}} [[zagadnienie mostów królewieckich]], opis którego opublikował w 1736 roku [[Leonhard Euler]]{{odn|Kenneth A. Ross, Charles R.B. Wright|s=340}}:

<span style="font-size: 300%;">
[[Plik:Konigsberg bridges.png|150px]] →
[[Plik:7 bridges.svg|150px]] →
[[Plik:Königsberg graph.png|150px]]
</span>

Grafy mogą służyć do praktycznych zastosowań (także z pomocą komputerów){{odn|Robin J. Wilson|s = 7}} w wielu różnorodnych problemach{{odn|Kenneth A. Ross, Charles R.B. Wright|s=142}}{{odn|Bohdan Korzan|s = 9}}, np.: sieć dróg z wierzchołkami reprezentującymi skrzyżowania i krawędziami przedstawiającymi ulice{{odn|Kenneth A. Ross, Charles R.B. Wright|s=142}}, sieć pomieszczeń i korytarzy w budynkach{{odn|Kenneth A. Ross, Charles R.B. Wright|s=352}}, dzięki czemu możliwe jest komputerowe wynajdywanie najlepszej drogi ze swojego obecnego położenia do pożądanego celu. [[Algorytm]]y grafowe stanowią istotną część programów obsługujących urządzenia [[Global Positioning System|GPS]]{{odn|Robert Kowalczyk|s = 2}}. System [[Sztuczna inteligencja|sztucznej inteligencji]] w niektórych [[Gra komputerowa|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{{odn|Robert Kowalczyk|s=2–3}}. Przedstawienie w formie grafów sieci komputerowych pozwala na stworzenie oprogramowania usprawniającego [[Trasowanie (telekomunikacja)|trasowanie]] w [[Internet|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ń{{odn|Robert Kowalczyk|s = 3}}. Za pomocą związanych z grafami pojęć można opisywać też m.in. rysunki [[Talia grafu|obwodów]], schematy blokowe, ponieważ przedstawiają one połączenia lub relacje, zachodzące między różnymi fragmentami [[wykres]]u{{odn|Kenneth A. Ross, Charles R.B. Wright|s=142}}.

[[Drzewo (matematyka)|Drzewa grafowe]] przydatne są w praktycznej reprezentacji różnego rodzaju hierarchii{{odn|Kenneth A. Ross, Charles R.B. Wright|s=361}}. Mistrzostwa sportowe czy [[drzewo genealogiczne]] mogą być w przejrzysty sposób opisane przez [[drzewo binarne|drzewa binarne]]{{odn|Robert Kowalczyk|s = 2}}. Do tworzenia [[Kodowanie Huffmana|kodów Huffmana]] można wykorzystać drzewa binarne z wagami{{odn|Thomas Cormen|s=385}}. Idea działania danego [[Niedeterministyczny automat skończony|niedeterministycznego automatu skończonego]] może być w przejrzysty sposób pokazana przez odpowiedni graf{{odn|Thomas Cormen|s=968}}.

Wzrasta również znaczenie i wykorzystanie teorii grafów w dziedzinach takich, jak chemia, lingwistyka, geografia, architektura i inne{{odn|Robin J. Wilson|s = 7}}.

== Definicje ==
[[Plik:Undirected graph no background.svg|thumb|200px|Graf nieskierowany]]
[[Plik:Directed graph no background.svg|thumb|200px|Graf skierowany]]
[[Plik:Graph weights.svg|thumb|200px|Graf z wagami{{odn|Kenneth A. Ross, Charles R.B. Wright|s=386}}]]
[[Plik:Multi graph.svg|thumb|200px|Multigraf{{odn|Kenneth A. Ross, Charles R.B. Wright|s=148}}]]
Różni autorzy stosują bardzo odmienne sposoby definiowania i oznaczania elementów grafu{{odn|Kenneth A. Ross, Charles R.B. Wright|s=147}}{{odn|Robin J. Wilson|s=20}}.

=== Graf ===
Jedną z definicji grafu jest: graf (nieskierowany) <math>G</math> składa się z dwóch zbiorów: <math>V</math> oraz <math>E,</math> przy czym <math>V</math> jest niepustym [[zbiór|zbiorem]], którego elementy nazywane są wierzchołkami, a <math>E</math> jest [[rodzina zbiorów|rodziną]] dwuelementowych podzbiorów zbioru wierzchołków <math>V,</math> zwanych krawędziami<ref>{{Encyklopedia PWN | tytuł = Graf | id = 3907380 | data dostępu = 2021-07-22}}</ref>: <math>E\subseteq \{\{u,v\} : u,v \in V\}.</math> Definicja ta nie wymaga, by <math>V</math> i <math>E</math> 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{{odn|Kenneth A. Ross, Charles R.B. Wright|s=147}}.

=== Graf skierowany ===
{{Osobny artykuł|Graf skierowany}}
Graf skierowany lub inaczej digraf{{odn|Kenneth A. Ross, Charles R.B. Wright|s=142}} składa się z dwóch zbiorów – niepustego zbioru wierzchołków <math>V</math> oraz rodziny <math>A</math> [[Para uporządkowana|par uporządkowanych]] elementów zbioru <math>V,</math> zwanych krawędziami lub łukami grafu skierowanego. Kolejność wierzchołków w parze wyznacza kierunek krawędzi – w przypadku pary <math>v,u</math> łuk biegnie z wierzchołka <math>v</math> do wierzchołka <math>u</math>{{odn|Robin J. Wilson|s=135}}. Podobnie, jak w przypadku grafu nieskierowanego, definicja ta ma sens zarówno wtedy, gdy zbiory <math>V</math> lub <math>A</math> są skończone, jak i nieskończone{{odn|Kenneth A. Ross, Charles R.B. Wright|s=143}}.

=== Graf mieszany ===
{{Osobny artykuł|Graf mieszany}}
Graf mieszany to uporządkowana trójka grafu <math>G = (V,E,A)</math> gdzie zbiory <math>V,</math> <math>E,</math> <math>A</math> są zdefiniowane jak wyżej, czyli zawiera jednocześnie krawędzie skierowane i nieskierowane{{odn|Matthias Beck|s = 1}}.

=== Grafy z wagami ===
Przez zdefiniowanie funkcji z <math>V,</math> <math>E</math> lub <math>A</math> w pewien zbiór <math>X</math> można przypisać krawędziom lub wierzchołkom etykiety, służące do przechowywania dodatkowych informacji{{odn|Peter Fletcher|s=463}}. Etykiety liczbowe są często nazywane wagami{{odn|Robin J. Wilson|s=57}}, 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ę <math>\delta\colon E \to K</math> taką, że dla każdej krawędzi <math>e \in E,</math> <math>\delta (e)</math> jest wagą danej krawędzi{{odn|Robin J. Wilson|s=138}}.

Grafem ważonym wierzchołkowo nazywa się graf <math>G_\omega := (V,E,\omega),</math> w którym <math>\omega\colon V \to \mathbb{N}</math> jest funkcją przypisującą każdemu wierzchołkowi pewną [[Liczby naturalne|liczbę naturalną]] nazywaną wagą wierzchołka. Graf taki oznacza się przez <math>G_\omega</math> (lub po prostu <math>G,</math> a to, że jest ważony wynika z kontekstu), natomiast wagę wierzchołka <math>v</math> oznacza się przez <math>\omega(v)</math>{{odn|Rafał Witkowski|s = 3}}.

=== Warianty definicji ===
W wielu zastosowaniach podstawowe definicje grafów nie są wystarczające, dlatego wprowadza się pewne modyfikacje{{odn|Kenneth A. Ross, Charles R.B. Wright|s=147}}. 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 <math>\{v\}</math>{{odn|Robin J. Wilson|s=20}} albo użyć dwuelementowego [[multizbiór|multizbioru]] <math>\{v,v\}.</math> W grafie skierowanym pętla jest naturalnie reprezentowana przez parę <math>v,v</math>{{odn|Kenneth A. Ross, Charles R.B. Wright|s=147}}.

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 [[multigraf]]em{{odn|Kenneth A. Ross, Charles R.B. Wright|s=144}}. Uzyskuje się go np. przez zdefiniowanie <math>E</math> lub <math>A</math> jako multizbioru{{odn|Kenneth A. Ross, Charles R.B. Wright|s=147}}.

; 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 (matematyka)|relacja binarna]] <math>R</math> taka, że dla dowolnych wierzchołków <math>v</math> i <math>u</math> <math>vRu</math> zachodzi wtedy i tylko wtedy, gdy istnieje krawędź łącząca <math>v</math> i <math>u</math>{{odn|Kenneth A. Ross, Charles R.B. Wright|s=143}}. Dla grafów nieskierowanych relacja ta jest [[Relacja symetryczna|symetryczna]]{{odn|Grażyna Mirkowska}}.

Graf nieskierowany można też definiować{{odn|Kenneth A. Ross, Charles R.B. Wright|s=147}} jako trójkę <math>G=(V,E,\gamma),</math> gdzie <math>V</math> jest niepustym [[zbiór|zbiorem]], którego elementy nazywają się wierzchołkami, <math>E</math> jest [[rodzina zbiorów|rodziną]] dwuelementowych podzbiorów zbioru wierzchołków <math>V</math> zwanych krawędziami: <math>E\subseteq \{\{u,v\} : u,v \in V,u \neq v\},</math> a <math>\Upsilon</math> jest funkcją ze zbioru <math>E</math> w zbiór <math>\{u, v\}: u, v \in V(G)\}</math> wszystkich podzbiorów jedno- lub dwuelementowych zbioru <math>V.</math> Wówczas jeżeli <math>e</math> jest krawędzią grafu, to kończy się ona wierzchołkami <math>u,v\in V,</math> gdy <math>\gamma(e)=\{u,v\},</math> i jest pętlą wierzchołka <math>v,</math> gdy <math>\gamma(e)=\{v\}.</math>

Graf skierowany określa się też jako trójkę <math>G=(V,E,\gamma),</math> gdzie zbiory <math>V</math> i <math>E</math> są zdefiniowane analogicznie do grafów nieskierowanych a <math>\gamma</math> 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 – <math>\gamma\colon E \to V\times V.</math> Jeśli <math>e</math> jest krawędzią grafu <math>(e \in A)</math> oraz <math>\Upsilon(e) = (p, q),</math> to <math>p</math> nazywane jest początkiem krawędzi <math>e,</math> a <math>q</math> – końcem krawędzi <math>e</math> i mówi się, że <math>e</math> biegnie od <math>p</math> do <math>q</math>{{odn|Kenneth A. Ross, Charles R.B. Wright|s=143}}.

== Inne typy grafów ==
{{Galeria
|Nazwa            = Grafy nieskończone
|wielkość         = 200
|Plik:Square grid graph.svg|Przykład grafu nieskończonego – krata kwadratowa{{odn|Robin J. Wilson|s=106}}
|Plik:Triangular grid graph.svg|Przykład grafu nieskończonego – krata trójkątna{{odn|Robin J. Wilson|s=106}}
}}

=== 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 <math>E(G)</math> oraz <math>V(G)</math> są skończone{{odn|Kenneth A. Ross, Charles R.B. Wright|s=143}}{{odn|Robin J. Wilson|s=105}}.

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 <math>G</math> składa się z nieskończonego zbioru wierzchołków <math>V(G)</math> oraz nieskończonej rodziny <math>E(G)</math> krawędzi grafu. Gdy zarówno <math>V(G),</math> jak i <math>E(G)</math> są [[Zbiór przeliczalny|przeliczalne]], graf <math>G</math> nazywa się grafem przeliczalnym. Wiele pojęć z zakresu własności grafów (np. ścieżka{{odn|Robin J. Wilson|s=106}}, planarność, spójność{{odn|Robin J. Wilson|s=105}}) 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ń{{odn|Robin J. Wilson|s=105}}.

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

=== Graf geometryczny ===
Dla każdego grafu istnieje nieskończenie wiele{{odn|Juliusz Lech Kulikowski|s=71}} przedstawiających go rysunków{{odn|''Teoria grafów''}}, gdyż klasyczne definicje grafów nie uwzględniają pojęć z zakresu geometrii, takich jak miara kątów, długości odcinków itp{{odn|Juliusz Lech Kulikowski|s=71}}. 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.){{odn|Juliusz Lech Kulikowski|s=71}}{{odn|Elżbieta Lewandowicz|s=269}}. 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{{odn|Juliusz Lech Kulikowski|s=71}}{{odn|Elżbieta Lewandowicz|s=271}}. 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 [[Przestrzeń metryczna|metryki]] dwuargumentowej funkcji ze zbioru krawędzi grafu w zbiór dodatnich liczb rzeczywistych{{odn|Juliusz Lech Kulikowski|s=72}}.

== Pojęcia służące do opisu grafów ==
[[Plik:Graph theory tree.svg|thumb|200px|Wszystkie drogi w tym grafie są proste, nie ma cykli]]
[[Plik:Graph spanning tree.svg|thumb|200px|Graf i jego drzewo spinające (po prawej stronie){{odn|Robin J. Wilson|s=65}}]]
[[Plik:Graph single node.svg|thumb|200px|Pętla]]
[[Plik:Piggy graph.svg|thumb|200px|Graf, posiadający siedem składowych, z których dwie są izolowanymi wierzchołkami{{odn|Kenneth A. Ross, Charles R.B. Wright|s=342}}]]
[[Plik:Graph walls.svg|thumb|200px|Graf o ścianach <math>f_1, f_2, f_3</math> oraz <math>f_4</math> – ściana <math>f_4</math> jest ścianą nieskończoną{{odn|Robin J. Wilson|s=89}}]]

=== Alfabetyczna lista definicji ===
* '''Acentryczność wierzchołka grafu''' – maksymalna odległość wierzchołka do innych wierzchołków grafu{{odn|Małgorzata Kuchta}} lub inaczej długość najdłuższej ścieżki prostej zaczynającej się w danym wierzchołku{{odn|Jérémie Bouttier}}.
* '''Automorfizm grafu''' – [[Funkcja wzajemnie jednoznaczna|wzajemnie jednoznaczne]] przekształcenie <math>\varphi</math> zbioru wierzchołków grafu prostego w ten sam zbiór takie, że wierzchołki <math>\varphi(v)</math> oraz <math>\varphi(w)</math> są sąsiednie wtedy i tylko wtedy, gdy <math>v</math> i <math>w</math> są sąsiednie{{odn|Robin J. Wilson|s=34–35}}.
* '''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{{odn|Robin J. Wilson|s=67}}.
* '''[[Cykl (teoria grafów)|Cykl]]''' – zamknięta droga prosta <math>e_a,e_b,\dots,e_z,</math> taka że krawędź <math>e_z</math> kończy się w początkowym wierzchołku drogi{{odn|Kenneth A. Ross, Charles R.B. Wright|s=146}}.
* '''[[Droga (teoria grafów)|Droga]]''' – wyznaczona przez krawędzie trasa, polegająca na podróżowaniu od wierzchołka do wierzchołka po łączących je krawędziach{{odn|Kenneth A. Ross, Charles R.B. Wright|s=146}}. Jeżeli przez <math>e_i</math> oznaczy się <math>i</math>-tą krawędź grafu, to droga może być jednoznacznie zapisana jako <math>e_a,e_b,\dots,e_z</math>{{odn|Robin J. Wilson|s=145}}{{odn|Marek Majewski, ''Teoria grafów i jej zastosowania''|s=13–19}}.
* '''Droga prosta''' – droga niezawierająca dwóch tych samych krawędzi{{odn|Kenneth A. Ross, Charles R.B. Wright|s=328}}.
* '''Długość drogi/ścieżki''' – liczba krawędzi/wierzchołków, tworzących daną drogę/ścieżkę{{odn|Kenneth A. Ross, Charles R.B. Wright|s=145}}.
* '''Droga acykliczna''' – droga, niezawierająca cyklu{{odn|Kenneth A. Ross, Charles R.B. Wright|s=146}}.
* '''[[Drzewo rozpinające|Drzewo spinające grafu]]''' – spójny, acykliczny podgraf danego grafu, zawierający wszystkie jego wierzchołki{{odn|Robin J. Wilson|s=145}}.
* '''Gęstość grafu''' – stosunek liczby krawędzi do największej możliwej liczby krawędzi{{odn|Graph Theory}}. 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{{odn|Agnieszka Rybarczyk}}.
* '''[[klika (teoria grafów)|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{{odn|Juliusz Lech Kulikowski|s=264}}{{odn|Jakub Wróblewski}} (czyli podgraf pełny{{odn|Dariusz Dereniowski|s=11}}).
* '''[[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{{odn|Robin J. Wilson|s=110}}.
* '''[[Graf (matematyka)|Krawędzie sąsiednie]]''' – krawędzie kończące się w jednym wierzchołku{{odn|Kenneth A. Ross, Charles R.B. Wright|s=150}}. 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{{odn|Kenneth A. Ross, Charles R.B. Wright|s=146}}.
* '''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{{odn|Kenneth A. Ross, Charles R.B. Wright|s=496}}.
* '''Liczba chromatyczna''' – najmniejsza liczba kolorów potrzebna do prawidłowego pokolorowania grafu{{odn|Robin J. Wilson|s=110}}.
* '''[[Most (teoria grafów)|Most]]''' – krawędź, po usunięciu której wzrasta liczba spójnych składowych grafu{{odn|Robin J. Wilson|s=44}}.
* '''Nadgraf grafu''' <math>H</math> – taki graf, że <math>H</math> jest jego [[podgraf]]em{{odn|Paweł Wal}}.
* '''[[Odległość (teoria grafów)|Odległość]]''' – liczba krawędzi w najkrótszej ścieżce łączącej dane dwa wierzchołki.
* '''[[Pętla (teoria grafów)|Pętla]]''' – krawędź zaczynająca i kończąca się w tym samym wierzchołku{{odn|Kenneth A. Ross, Charles R.B. Wright|s=147}}.
* '''[[Podgraf|Podgraf grafu]]''' <math>H</math> – graf <math>G</math> uzyskany poprzez usunięcie części wierzchołków z <math>H,</math> wraz z kończącymi się w nich krawędziami{{odn|Kenneth A. Ross, Charles R.B. Wright|s=327}}.
* '''Rozmiar grafu''' <math>G</math> – liczbę krawędzi grafu, oznaczonych <math>G</math>{{odn|Jerzy Wałaszek, ''Podstawowe pojęcia dotyczące grafów''}}.
* '''Rząd grafu''' <math>G</math> – liczba wierzchołków grafu, oznaczonych <math>G</math>{{odn|Jerzy Wałaszek, ''Podstawowe pojęcia dotyczące grafów''}}.
* '''[[Graf regularny|Graf r-regularny]]''' – graf, w którym każdy wierzchołek grafu jest stopnia <math>r</math>{{odn|Kenneth A. Ross, Charles R.B. Wright|s=334}}.
* '''Sąsiad''' – dwa wierzchołki są sąsiadami, jeśli istnieje krawędź pomiędzy nimi{{odn|Kenneth A. Ross, Charles R.B. Wright|s=146}}.
* '''[[Spójna składowa grafu|Spójna składowa grafu <math>G</math>]]''' – możliwie największy spójny podgraf grafu <math>G.</math> Graf spójny ma jedną spójną składową{{odn|Kenneth A. Ross, Charles R.B. Wright|s=342}}.
* '''[[Stopień wierzchołka]]''' <math>v</math> – liczba kończących się w wierzchołku krawędzi{{odn|Kenneth A. Ross, Charles R.B. Wright|s=333}}. Oznaczenie: <math>\deg(v)</math>{{odn|Kenneth A. Ross, Charles R.B. Wright|s=333}}. W przypadku grafów skierowanych mówi się o stopniach wejściowym i wyjściowym – <math>\operatorname{indeg}(v),</math> <math>\operatorname{outdeg}(v)</math>{{odn|Kenneth A. Ross, Charles R.B. Wright|s=483}}
* '''[[Graf (matematyka)|Ściana]]''' – obszar zamknięty, wyznaczony przez krawędzie grafu (tzw. krawędzie tworzące ścianę){{odn|Robin J. Wilson|s=89}}. Z pojęciem ściany ściśle powiązane jest [[Graf eulerowski|twierdzenie Eulera]]{{odn|Robin J. Wilson|s=90}}. 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ę){{odn|Robin J. Wilson|s=89}}.
* '''[[Ścieżka (teoria grafów)|Ś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 <math>v_a,v_b,\dots,v_z</math>{{odn|Kenneth A. Ross, Charles R.B. Wright|s=145}}{{odn|Jolanta Koszelew|s = 1}}.
* '''Ścieżka prosta''' – ścieżka wyznaczona tak, by żaden wierzchołek na trasie nie powtarzał się{{odn|Jolanta Koszelew|s = 2}}.
* '''Ścieżka zamknięta''' – ścieżka <math>v_a,v_b,\dots,v_z,v_a,</math> czyli kończąca się w początkowym wierzchołku{{odn|Kenneth A. Ross, Charles R.B. Wright|s=327}}.
* '''Usunięcie wierzchołka''' – wymazanie wierzchołka oraz wszystkich kończących się w nim krawędzi z danego grafu{{odn|Izolda Gorgol|s = 2}}.
* '''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łączenia{{odn|Kenneth A. Ross, Charles R.B. Wright|s=373}}. Graf taki można wykorzystać np. do wyznaczenia optymalnej ścieżki – w sensie przejechanych kilometrów trasy – lub ogólniej do rozwiązania [[Problem komiwojażera|problemu komiwojażera]] – wyznaczenia optymalnego rozłożenia kabli w sieci{{odn|Bohdan Korzan|s = 9}}, koordynowania wysyłania plików metodą [[peer-to-peer]] itp.{{odn|Adrian Horzyk}}
* '''[[Wierzchołek izolowany]]''' – wierzchołek o stopniu <math>0,</math> czyli niebędący końcem żadnej krawędzi{{odn|Robin J. Wilson|s=24}}.
* '''Wierzchołek pokrywający krawędź''' – wierzchołek <math>v</math> pokrywa krawędź <math>e,</math> jeżeli <math>e</math> kończy się w <math>v.</math> W analogiczny sposób definiuje się '''krawędź pokrywającą dany wierzchołek''' – krawędź <math>e</math> kryje wierzchołek <math>v,</math> 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.
* '''[[Punkt artykulacji|Wierzchołek rozcinający]]''' – wierzchołek, po usunięciu którego zwiększa się liczba spójnych składowych grafu{{odn|Robin J. Wilson|s=45}}. 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ący{{odn|Konstanty Junosza-Szaniawski}}.

=== Oznaczenia formalne ===
Często dla danego grafu <math>G</math> stosuje się skrócone oznaczenia oparte na [[Alfabet grecki|alfabecie greckim]] oraz [[Alfabet łaciński|łacińskim]]{{odn|Kenneth A. Ross, Charles R.B. Wright|s = wykaz oznaczeń}}{{odn|Robin J. Wilson|s = 9}}:
* <math>n</math> lub <math>V(G)</math> – liczba wierzchołków <math>G</math>{{odn|Kenneth A. Ross, Charles R.B. Wright|s=142}}{{odn|Robin J. Wilson|s = 9}},
* <math>m</math> lub <math>E(G)</math> – liczba krawędzi <math>G</math>{{odn|Kenneth A. Ross, Charles R.B. Wright|s=143}}{{odn|Robin J. Wilson|s = 9}},
* <math>\delta (G)</math> – najmniejszy stopień wierzchołka w <math>G</math>{{odn|''Stopień wierzchołka''}},
* <math>\Delta (G)</math> – największy stopień wierzchołka w <math>G</math>{{odn|Robin J. Wilson|s = 9}},
* <math>\chi (G)</math> – liczba chromatyczna <math>G</math>{{odn|Robin J. Wilson|s=10}},
* <math>\chi' (G)</math> – indeks chromatyczny <math>G</math>{{odn|Robin J. Wilson|s=10}},
* <math>k</math> – liczba spójnych składowych <math>G</math>{{odn|Robin J. Wilson|s = 9}}.

; Przykład dla grafu nieskierowanego <math>G</math>
[[Plik:6n-graf v nodes.svg|thumb|200px|Graf nieskierowany]]
* <math>V(G) = \{v_1, v_2, v_3, v_4, v_5, v_6\}</math>
* <math>E(G) = \{\{v_1, v_2\}, \{v_1, v_5\}, \{v_5, v_4\}, \{v_4, v_6\},</math>
:: <math>\{v_4, v_3\}, \{v_3, v_2\}, \{v_2, v_5\}\}</math>

Przykładową ścieżką prostą może być <math>v_6,v_4,v_5,v_1,</math> a cyklem – <math>v_5,v_4,v_3,v_2,v_5.</math> Stopnie wierzchołków są następujące:
* <math>\deg(v_1) = 2</math>
* <math>\deg(v_2) = 3</math>
* <math>\deg(v_3) = 2</math>
* <math>\deg(v_4) = 3</math>
* <math>\deg(v_5) = 3</math>
* <math>\deg(v_6) = 1</math>

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

=== Izomorfizm i homeomorfizm grafów ===
[[Plik:Graph isomorphism 2.svg|thumb|200px|Przykład dwóch grafów izomorficznych{{odn|Kenneth A. Ross, Charles R.B. Wright|s=333}}]]
[[Plik:Homeomorphic graphs.svg|thumb|200px|Przykład dwóch grafów homeomorficznych{{odn|Robin J. Wilson|s=85}}]]
{{Osobny artykuł|Izomorfizm grafów|Homeomorfizm grafów}}
Graficzna reprezentacja grafów (w postaci kropek i łączących je krzywych) jest tylko sposobem przedstawienia [[Relacja (matematyka)|relacji]] zachodzących między wierzchołkami. Dla każdego grafu istnieje nieskończenie wiele{{odn|Juliusz Lech Kulikowski|s=71}} przedstawiających go jednoznacznie wykresów, rysunków{{odn|''Teoria grafów''}}. 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ę izomorficznymi{{odn|Robin J. Wilson|s=21}}.

Dwa grafy są [[Homeomorfizm|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ędziami{{odn|Robin J. Wilson|s=84}}.

=== Klasy grafów ===
{{Galeria
|Nazwa            = Klasy grafów
|wielkość         = 200
|Plik:Cyclic graph.svg|Graf cykliczny{{odn|Robin J. Wilson|s=30}}
|Plik:Q3 graph.svg|3-kostka{{odn|Robin J. Wilson|s=33}}
|Plik:Line graph6.svg|Graf liniowy{{odn|Robin J. Wilson|s=30}}
|Plik:K4 graph.svg|Dwie graficzne reprezentacje grafu <math>K_4</math> z przecinającymi się liniami (u góry) i w formie grafu płaskiego (u dołu){{odn|Juliusz Lech Kulikowski|s=221}}
|Plik:Circle graph.svg|Koło{{odn|Robin J. Wilson|s=30}}
}}
Grafy można podzielić ze względu na różne własności, zazwyczaj zachowane w obrębie izomorfizmów danego grafu{{odn|Adrian Horzyk}}{{odn|''Teoria grafów''}}. Niektóre [[Klasa grafów|klasy grafów]] to:
* '''[[Drzewo (matematyka)|drzewo]]''' – spójny graf acykliczny{{odn|Kenneth A. Ross, Charles R.B. Wright|s=352}},
* '''[[graf acykliczny]]''' – graf niezawierający żadnej drogi zamkniętej{{odn|Thomas Cormen|s=115}},
* '''graf cykliczny''' – regularny graf spójny, którego każdy wierzchołek jest stopnia drugiego{{odn|Robin J. Wilson|s=30}},
* '''[[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 innym{{odn|Kenneth A. Ross, Charles R.B. Wright|s=378}},
* '''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 <math>n_1 + n_2</math> wierzchołkach oznacza się <math>K_{n_1,n_2}</math>{{odn|Kenneth A. Ross, Charles R.B. Wright|s=378}},
* '''[[graf eulerowski]]''' – graf, posiadający drogę prostą, przechodzącą przez każdą krawędź{{odn|Robin J. Wilson|s=14}}; niebędącym grafem eulereowskim jest '''graf półeulerowski''', w którym istnieje droga, zawierająca każdą krawędź danego grafu,
* '''graf genusu''' <math>g</math> – graf, który można narysować bez przecięć (czyli w formie grafu płaskiego) na powierzchni [[genus]]u <math>g,</math> ale nie można narysować go bez przecięć na powierzchni genusu <math>g-1</math>{{odn|Robin J. Wilson|s=95–96}}.
* '''[[graf hamiltonowski]]''' – graf, posiadający ścieżkę prostą, przechodzącą przez każdy wierzchołek{{odn|Robin J. Wilson|s=14}},
* '''[[graf k-dzielny]]''' – graf, którego zbiór wierzchołków można podzielić na <math>k</math> parami rozłącznych podzbiorów takich, że żadne dwa węzły, należące do tego samego zbioru, nie są połączone krawędzią{{odn|''Pojęcia wstępne teorii grafów''|s = 9}},
* '''graf k-dzielny pełny''' – graf, którego zbiór wierzchołków dzieli się na <math>k</math> niepołączonych między sobą podzbiorów wierzchołków, oraz każdy wierzchołek <math>v_i</math> z <math>j</math>-tego przedziału <math>v_i</math> jest połączony z każdym wierzchołkiem z każdego z przedziałów poza <math>j</math>{{odn|''Pojęcia wstępne teorii grafów''|s = 9}},
* '''[[graf k-spójny]]''' – graf, posiadający <math>k</math> spójnych składowych{{odn|Andrzej Ruciński}},
* '''[[graf komórkowy]]''' – graf płaski, którego wszystkie ściany są utworzone przez drogi zamknięte tej samej długości{{odn|Juliusz Lech Kulikowski|s=223}},
* '''graf krytyczny''' – graf, którego każdy wierzchołek/krawędź jest krytyczny/krytyczna{{odn|Konstanty Junosza-Szaniawski}},
* '''[[graf kubiczny]]''' – specjalne określenie dla grafów regularnych stopnia <math>3</math>{{odn|Robin J. Wilson|s=31}},
* '''graf liniowy''' – graf, otrzymany poprzez usunięcie jednej krawędzi z grafu cyklicznego{{odn|Robin J. Wilson|s=30}},
* '''[[graf pełny]]''' – graf, którego każdy wierzchołek jest połączony bezpośrednio krawędzią z każdym innym{{odn|Kenneth A. Ross, Charles R.B. Wright|s=278}}; graf pełny o <math>n</math> wierzchołkach oznacza się <math>K_n</math>{{odn|Robin J. Wilson|s=30}}{{odn|Kenneth A. Ross, Charles R.B. Wright|s=334}},
* '''[[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ły{{odn|Robin J. Wilson|s=15}}. [[Kazimierz Kuratowski]] udowodnił, że grafy pełne <math>K_5</math> i <math>K_{3,3}</math> są nieplanarne oraz że każdy inny graf nieplanarny musi posiadać podgraf homeomorficzny z którymś z tych grafów{{odn|Robin J. Wilson|s=85}},
* '''[[graf platoński]]''' – grafy, utworzone z krawędzi i wierzchołków [[Wielościan foremny|wielościanów foremnych]]{{odn|Andrzej Łachwa|s=20}},
* '''[[graf płaski]]''' – izomorficzne przedstawienie grafu takie, że żadne dwie krawędzie się nie przecinają{{odn|Robin J. Wilson|s=82}},
* '''[[Graf pierwotny|graf podstawowy grafu skierowanego]]''' – niemal ten sam, co graf płaski, ale nieskierowany, bo bez zwrotów na krawędziach{{odn|Wojciech Palacz|s = 2}},
* '''[[graf prosty]]''' – graf, niezawierający pętli ani krawędzi wielokrotnych{{odn|Robin J. Wilson|s=13}}, nazywany jest multigrafem{{odn|Kenneth A. Ross, Charles R.B. Wright|s=278}}; z reguły zdanie „<math>G</math> jest grafem” oznacza w domyśle, że <math>G</math> jest grafem prostym{{odn|Kenneth A. Ross, Charles R.B. Wright|s=147}},
* '''[[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ą{{odn|''Grafy cięciwowe, grafy przedziałowe, grafy dwudzielne''}},
* '''graf pusty''' – graf, nieposiadający krawędzi{{odn|Robin J. Wilson|s=29}},
* '''[[Graf regularny|graf r-regularny]]''' – graf, którego każdy wierzchołek jest stopnia <math>r</math>{{odn|Kenneth A. Ross, Charles R.B. Wright|s=334}},
* '''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łka{{odn|Kenneth A. Ross, Charles R.B. Wright|s=342}},
* '''graf toroidalny''' – graf genusu <math>1</math>{{odn|Robin J. Wilson|s=95–96}},
* '''[[Kostka (teoria grafów)|k-kostka]]''' – regularny graf dwudzielny, którego wierzchołki odpowiadają ciągom <math>(a_1,a_2,\dots,a_k),</math> że <math>\forall i \in <1,k>a_i = 0 \lor a_i = 1,</math> i którego wierzchołki połączone są krawędzią wtedy i tylko wtedy, gdy różnią się jednym wyrazem odpowiadającego im ciągu{{odn|Robin J. Wilson|s=33}},
* '''[[Koło (teoria grafów)|koło]]''' – graf o <math>n</math> wierzchołkach, utworzony z grafu cyklicznego o <math>n-1</math> wierzchołkach poprzez połączenie nowego wierzchołka z każdym wierzchołkiem w grafie cyklicznym{{odn|Robin J. Wilson|s=30}},
* '''[[las (matematyka)|las]]''' – niespójny graf acykliczny{{odn|Kenneth A. Ross, Charles R.B. Wright|s=358}},
* '''[[Turniej (matematyka)|turniej]]''' – graf skierowany, w którym każde dwa wierzchołki łączy dokładnie jedna krawędź{{odn|Kenneth A. Ross, Charles R.B. Wright|s=488}}.

== Operacje na grafach ==
{{Galeria
|Nazwa            = Grafy krawędziowe
|wielkość         = 200
|Plik:Line graph construction 1.svg|G-1
|Plik:Line graph construction 2.svg|G-2
|Plik:Line graph construction 3.svg|G-3
|Plik:Line graph construction 4.svg|G-4
}}
[[Plik:Dual graphs.svg|thumb|200px|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 dualny{{odn|William Kocay, Daniel Neilson, Ryan Szypowski}}]]

=== Operacje binarne ===
; Suma grafów
<math>G_1 \cup G_2 = (V_1 \cup V_2,E_1 \cup E_2)</math> – jeżeli dane są dwa grafy <math>G_1=(V_1,E_1)</math> oraz <math>G_2=(V_2,E_2),</math> to ich sumą jest graf, którego zbiór wierzchołków i krawędzi tworzą wszystkie wierzchołki i krawędzie tych grafów{{odn|Robin J. Wilson|s=22}}.

; Przecięcie grafów
Przecięcie grafów <math>G_1 \cap G_2 = (V_1 \cap V_2,E_1 \cap E_2)</math>{{odn|Andrzej Łachwa|s = 6}} jest definiowane analogicznie do sumy. Jeżeli dane są dwa grafy <math>G_1=(V_1,E_1)</math> i <math>G_2=(V_2,E_2),</math> to ich przecięciem jest graf, którego wierzchołki i krawędzie wchodzą w skład obu tych grafów{{odn|Andrzej Wiśniewski}}.

; Zespolenie grafów
<math>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\})</math> – zespoleniem grafów <math>G_1=(V_1,E_1)</math> i <math>G_2=(V_2,E_2)</math> nazywa się graf, w którym z każdego wierzchołka <math>G_1</math> poprowadzono krawędzie do każdego wierzchołka <math>G_2</math>{{odn|Marek Majewski, ''Własności grafów''|s=5–7}}.

=== Operacje unarne ===
; Graf krawędziowy
[[Graf krawędziowy]] grafu prostego <math>G</math> to graf, który dla każdej krawędzi z <math>G</math> ma wierzchołek połączony z wierzchołkami reprezentującymi pozostałe krawędzie sąsiadujące ze sobą w <math>G</math>{{odn|Robin J. Wilson|s=34}}. Etapy konstrukcji grafu krawędziowego <math>L_G{:}</math>
# Jeśli każdej krawędzi <math>e_i</math> grafu <math>G</math> przypisać jednoznacznie węzeł <math>v_i</math> grafu <math>L_G,</math> to
# Dwa węzły grafu <math>L_G</math> <math>v_i</math> oraz <math>v_j</math> da się połączyć krawędzią wtedy i tylko wtedy, gdy odpowiednie krawędzie <math>e_i</math> oraz <math>e_j</math> w grafie <math>G</math> są do siebie przyległe, tj. kończą się w jednym wierzchołku{{odn|Juliusz Lech Kulikowski|s=201–202}}.

; Dopełnienie grafu
[[Dopełnienie grafu|Dopełnieniem grafu]] <math>G</math> nazywa się graf <math>\overline{G},</math> w którym dwa wierzchołki są sąsiednie wtedy i tylko wtedy, gdy nie były sąsiednie w <math>G.</math> 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ściowym{{odn|Robin J. Wilson|s=33}}.

; Graf dualny
[[Graf dualny]] grafu <math>G</math> – graf, którego wierzchołki odpowiadają ścianom w <math>G.</math> Wierzchołki te są połączone, jeżeli odpowiednie ściany w <math>G</math> są sąsiednie{{odn|Robin J. Wilson|s=99}}.

; Domknięcie przechodnie
[[Domknięcie przechodnie]] dowolnych wierzchołków grafu <math>G</math> następuje wtedy i tylko wtedy, gdy pomiędzy wierzchołkami grafu, posiadającego te same wierzchołki co <math>G,</math> istnieje droga{{odn|Marcin Żurawski|s=46}}.

== Algorytmy grafowe ==
Poprzez pojęcie algorytmu grafowego rozumie się zazwyczaj algorytmy rozwiązujące problemy przedstawione przy użyciu pojęcia grafu{{odn|Adrian Horzyk}}{{odn|Kazimierz Jakubczyk|s=147}}.
{{Zobacz kategorię|Algorytmy grafowe}}

=== Przeszukiwanie grafu ===
{{Osobny artykuł|Przeszukiwanie grafu}}
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 informacji{{odn|Kazimierz Jakubczyk|s=154, 157}}. 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 grafowego{{odn|Thomas Cormen|s=526}}. Najczęściej używane metody przeszukiwania grafów:

; Przeszukiwanie wszerz
[[Przeszukiwanie wszerz]] polega na odwiedzeniu wszystkich wierzchołków, osiągalnych z danego wierzchołka{{odn|Łukasz Kowalik|s = 2}}.

; 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ł odwiedzony{{odn|Kenneth A. Ross, Charles R.B. Wright|s=427}}.

== Sposoby prezentacji grafów ==
Każdy graf może być jednoznacznie prezentowany na wiele sposobów. Dla percepcji człowieka najwygodniejszy jest rysunek grafu{{odn|Witold Lipski, Tomasz Czajka|s=74}}, pozostałe sposoby prezentacji wykorzystywane są w [[komputer]]ach{{odn|Kenneth A. Ross, Charles R.B. Wright|s=144}}{{odn|Robin J. Wilson|s=26}}. 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 <math>v</math> i <math>u</math> jest krawędź{{odn|Thomas Cormen|s=526–527}}. W przypadku grafów rzadkich listy sąsiedztwa okazują się wystarczająco szybkie by zrezygnować z pamięciożernych tablic{{odn|Thomas Cormen|s=527}}. Sposobami prezentacji grafów są: rysunek, macierze sąsiedztwa, listy sąsiedztwa{{odn|Thomas Cormen|s=526}} i macierze incydencji{{odn|Robin J. Wilson|s=27}}.

=== Rysunek grafu ===
Jednym ze sposobów prezentacji grafu jest rysunek grafu, ukazujący wierzchołki i łączące je krawędzie{{odn|Kenneth A. Ross, Charles R.B. Wright|s=144}}. Wierzchołki oznaczane są zazwyczaj kropkami{{odn|Kenneth A. Ross, Charles R.B. Wright|s=143}} lub kołami{{odn|Juliusz Lech Kulikowski|s=39}}, niekiedy zawierającymi indeksy bądź inne dodatkowe informacje{{odn|Adrian Horzyk}}{{odn|Juliusz Lech Kulikowski|s=40}}. Krawędzie prezentowane są krzywymi{{odn|Robin J. Wilson|s=12}} bądź prostymi{{odn|Robin J. Wilson|s=11}}, w przypadku krawędzi ważonych waga umieszczona jest bezpośrednio nad krawędzią{{odn|Kenneth A. Ross, Charles R.B. Wright|s=491}}.

{{Cytat
 |treść = Rysunkiem grafu <math>G</math> jest wykres składający się z punktów odpowiadających wierzchołkom zbioru <math>G</math> i łuków czy odcinków odpowiadających krawędziom, tak, że jeśli <math>\Upsilon(e) = (u,v),</math> to łuk dla krawędzi <math>e</math> łączy punkty oznaczone literami <math>u</math> i <math>v.</math>
 |autor = 
 |źródło = Kenneth A. Ross, Charles R.B. Wright: ''Matematyka dyskretna''.
 |styl = box środek
 |szerokość = 80%
}}

=== Macierz sąsiedztwa ===
{{Osobny artykuł|Macierz sąsiedztwa}}
Jedną ze [[struktura danych|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 <math>V(G)</math> na <math>V(G),</math> wyraz, leżący z <math>i</math>-tego wiersza i <math>j</math>-tej kolumny, zawiera wartość będącą liczbą krawędzi łączących <math>i</math>-ty i <math>j</math>-ty wierzchołek. W przypadku grafów prostych wyrazami w macierzy będą wartości [[Algebra Boole’a|boole’owskie]] – jest krawędź, bądź nie ma krawędzi{{odn|Kenneth A. Ross, Charles R.B. Wright|s=669}}. Macierz sąsiedztwa pozwala na prezentację grafów, zawierających krawędzie wielokrotne oraz [[pętla (teoria grafów)|pętle własne]]. Aby dowiedzieć się, ile krawędzi łączy wierzchołki <math>v_i\ i\ v_j,</math> wystarczy sprawdzić wartość komórki <math>A[i,j]</math>{{odn|Jerzy Wałaszek, ''Teoria grafów dla początkujących''}}. Tak zaimplementowana komputerowa struktura danych gwarantuje, że operacje sprawdzenia, czy <math>(v_i, v_j) \in E(G),</math> 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]] <math>O(n^2)</math>{{odn|Kazimierz Jakubczyk|s=153}}) oraz fakt, że czas potrzebny do przejrzenia zbioru krawędzi jest proporcjonalny do kwadratu liczby wierzchołków ([[złożoność obliczeniowa]] wynosi <math>O(n^2)</math>), zamiast do liczby krawędzi{{odn|Jerzy Wałaszek, ''Teoria grafów dla początkujących''}}.
{| class="wikitable" width=40%
|+ Przykład macierzy sąsiedztwa dla grafu nieskierowanego
|-
! Macierz sąsiedztwa
! Rys.
|-
|width=50%|
<math>A=\left[ \begin{matrix}
0 & 1 & 0 & 1\\
1 & 0 & 1 & 2\\
0 & 1 & 0 & 1\\
1 & 2 & 1 & 0
\end{matrix}\right]</math>
| [[Plik:Graph002.svg|thumb|center|200px|Graf odpowiadający macierzy sąsiedztwa{{odn|Robin J. Wilson|s=26}}. 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ę [[lista|listy jednokierunkowe]] oraz jednowymiarową [[Tablica (informatyka)|tablicę]] [[wskaźnik (typ danych)|wskaźników]] o rozmiarze <math>V(G),</math> gdzie <math>i</math>-ty element tablicy jest wskaźnikiem do początku listy przechowującej sąsiadów <math>i</math>-tego wierzchołka{{odn|Kazimierz Jakubczyk|s=152}}. W odróżnieniu od macierzy sąsiedztwa lista sąsiedztwa wymaga ilości pamięci proporcjonalnej do liczby krawędzi{{odn|Kazimierz Jakubczyk|s=153}}, 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 <math>\{v_i, v_j\} \in E(G)</math> wymaga czasu proporcjonalnego do mniejszego ze [[stopień wierzchołka|stopni wierzchołków]], a np. usunięcie krawędzi – do większego z nich{{odn|Thomas Cormen|s=528}}{{odn|Witold Lipski, Tomasz Czajka|s=77}}.
{| class="wikitable" width=40%
|+ Przykład listy sąsiedztwa
|-
! Lista sąsiedztwa
! Rys.
|-
|width=50%|
<math>u \to v,y</math><br />
<math>v \to u,w,y</math><br />
<math>w \to v,x,y</math><br />
<math>x \to w,y</math><br />
<math>y \to u, v, w, x</math>
| [[Plik:Graph00001.svg|thumb|center|200px|Graf, odpowiadający liście sąsiedztwa{{odn|Robin J. Wilson|s=26}}]]
|}

=== Macierz incydencji ===
[[Macierz incydencji]] <math>M</math> wymiaru <math>V(G)</math> na <math>E(G)</math> zawiera informacje takie, że <math>M_{i,j}=1</math> tylko, gdy <math>j</math>-ta krawędź kończy się w <math>i</math>-tym wierzchołku (czyli jest z nim incydentna){{odn|Robin J. Wilson|s=27}}. W przeciwnym wypadku <math>M_{i,j}=0</math>{{odn|Robin J. Wilson|s=27}}. 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ąco{{odn|Robin J. Wilson|s=26}}:
{| class="wikitable" width=40%
|+ Przykład macierzy incydencji
|-
! Macierz incydencji
! Rys.
|-
|width=50%|
<math>M=\left[ \begin{matrix}
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{matrix}\right]</math>
| [[Plik:Graph002.svg|thumb|center|200px|Graf odpowiadający macierzy incydencji]]
|}

== Uogólnienia ==
[[Plik:Hipergraf H1.svg|thumb|200px|Przykładowy hipergraf]]
; Hipergrafy
[[Hipergraf]] jest strukturą podobną do grafu{{odn|Thomas Cormen|s=116}}, z tą różnicą, że jego krawędź może łączyć więcej niż dwa wierzchołki{{odn|Bohdan Korzan|s=21–22}}.

; Grafy w teorii modeli
W [[teoria modeli|teorii modeli]] graf jest szczególnym przypadkiem struktury matematycznej{{odn|Anuj Dawar}}.

; Grafy a matroidy
[[Matroid]]y mogą być rozważane jako uogólnienie pojęcia grafu{{odn|Thomas Cormen|s=392}}, a pojęcia grafowe rozważane w odniesieniu do pojęć teorii matroidów mogą być przedstawione w prostszy sposób{{odn|Robin J. Wilson|s=186}}. Niech dany będzie dowolny graf <math>G = (V,E).</math> Zbiór <math>E</math> 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 lasy{{odn|Zofia Miechowicz}}.

{{clear}}

== Zobacz też ==
{{Literatura}}

== Przypisy ==
{{Przypisy}}

== Bibliografia ==
{{Układ wielokolumnowy |szerokość=28em <!-- od 14 do 110 --> |liczba=2 |
* {{Cytuj |url = https://orion.math.iastate.edu/myoung/papers/weakMG.pdf |tytuł = On Weak Chromatic Polynomials of Mixed Graphs |autor = Beck i in, Matthias |opublikowany = Iowa State University of Science and Technology |odn = {{odn/id|Matthias Beck}} |data dostępu = 2014-05-03 |archiwum = https://web.archive.org/web/20140503165935/https://orion.math.iastate.edu/myoung/papers/weakMG.pdf |zarchiwizowano = 2014-05-03}}
* {{Cytuj |url = http://arxiv.org/pdf/cond-mat/0303272v1.pdf |tytuł = Geodesic Distance in Planar Graphs |autor = Jérémie Bouttier |opublikowany = Cornell University Library |odn = {{odn/id|Jérémie Bouttier}}}}
* {{Cytuj książkę |nazwisko = Cormen i in |imię = Thomas |tytuł = Wprowadzenie do algorytmów |miejsce = Warszawa |rok = 2013 |isbn = 978-83-01-16911-4 |odn = {{odn/id|Thomas Cormen}}}}
* {{Cytuj |url = http://www.cl.cam.ac.uk/~ad260/talks/beroun1.pdf |tytuł = Finite Model Theory and Graph Isomorphism |autor = Anuj Dawar |opublikowany = Computer Laboratory University of Cambridge |odn = {{odn/id|Anuj Dawar}}}}
* {{Cytuj |url = http://kaims.pl/~deren/ag/wyklady/01_wprowadzenie.pdf |tytuł = Algorytmy Grafowe – wprowadzenie |autor = [[Dariusz Dereniowski]] |opublikowany = Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej |odn = {{odn/id|Dariusz Dereniowski}}}}
* {{Cytuj książkę |nazwisko = Diestel |imię = Reinhard |tytuł = Graph Theory |url = http://diestel-graph-theory.com/index.html |miejsce = Nowy Jork |rok = 2000 |isbn = 0-387-95014-1 |odn = {{odn/id|Reinhard Diestel}}}}
* {{Cytuj książkę |nazwisko = Fletcher |imię = Peter |nazwisko2 = Hoyle |imię2 = Hughes |nazwisko3 = Patty |imię3 = C. Wayne |tytuł = Foundations of Discrete Mathematics |miejsce = Boston |rok = 1991 |isbn = 0-53492-373-9 |odn = {{odn/id|Peter Fletcher}}}}
* {{Cytuj |url = http://antenor.pol.lublin.pl/users/gorgol/wstep-druk.pdf |tytuł = Pojęcia wstępne teorii grafów |autor = Izolda Gorgol |opublikowany = Zakład Systemów Informatycznych Politechniki Lubelskiej |odn = {{odn/id|Izolda Gorgol}}}}
* {{Cytuj |url = http://www.stanford.edu/class/archive/cs/cs106a/cs106a.1124/lectures/23/Slides.pdf |tytuł = Graphs and Networks |opublikowany = Stanford University |odn = {{odn/id|''Graphs and Networks''}}}}
* {{Cytuj |url = http://dyskretna.tcs.uj.edu.pl/docs/dyskretna-13-Grafy-dwudzielne-przedzialowe-i-cieciwowe.pdf |tytuł = Grafy cięciwowe, grafy przedziałowe, grafy dwudzielne |opublikowany = Zespół Katedr i Zakładów Informatyki Matematycznej Uniwersytetu Jagiellońskiego |odn = {{odn/id|''Grafy cięciwowe, grafy przedziałowe, grafy dwudzielne''}} |data dostępu = 2014-04-30 |archiwum = https://web.archive.org/web/20140502005927/http://dyskretna.tcs.uj.edu.pl/docs/dyskretna-13-Grafy-dwudzielne-przedzialowe-i-cieciwowe.pdf |zarchiwizowano = 2014-05-02}}
* {{Cytuj |url = http://webwhompers.com/graph-theory.html |tytuł = Graph Theory |opublikowany = Webwhompers |odn = {{odn/id|Graph Theory}} |data dostępu = 2014-04-30 |archiwum = https://web.archive.org/web/20140502001819/http://webwhompers.com/graph-theory.html |zarchiwizowano = 2014-05-02}}
* {{Cytuj książkę |nazwisko = Gross |imię = Jonathan L. |nazwisko2 = Yellen |imię2 = Jay |tytuł = Handbook of graph theory |miejsce = Warszawa |rok = 2004 |isbn = 978-1-58488-090-5 |odn = {{odn/id|Jonathan L. Gross, Jay Yellen}}}}
* {{Cytuj |url = http://home.agh.edu.pl/~horzyk/lectures/pi/ahdydpiwykl9.html |tytuł = Podstawy informatyki – grafy |autor = Adrian Horzyk |opublikowany = Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie |odn = {{odn/id|Adrian Horzyk}}}}
* {{Cytuj |url = http://web.archive.org/web/20120131111540/http://www.kaj.pr.radom.pl:80/docs/asd-r4.pdf |tytuł = Algorytmy grafowe |autor = Kazimierz Jakubczyk |opublikowany = Kazimierz Jakubczyk |odn = {{odn/id|Kazimierz Jakubczyk}}}}
* {{Cytuj |url = http://www.mini.pw.edu.pl/~szaniaws/www/?download=md_skrypt.pdf |tytuł = Teoria grafów |autor = Konstanty Junosza-Szaniawski |opublikowany = Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej |odn = {{odn/id|Konstanty Junosza-Szaniawski}}}}
* {{Cytuj |url = http://fatcat.ftj.agh.edu.pl/~kaprzyk/Geomkomp/geomkomp/node16.html |tytuł = Grafy abstrakcyjne i geometryczne |autor = Stanisław Kaprzyk |opublikowany = Wykłady z dyskretnej geometrii komputerowej |odn = {{odn/id|Stanisław Kaprzyk}} |data dostępu = 2014-04-27 |archiwum = https://web.archive.org/web/20140427160754/http://fatcat.ftj.agh.edu.pl/~kaprzyk/Geomkomp/geomkomp/node16.html |zarchiwizowano = 2014-04-27}}
* {{Cytuj książkę |nazwisko = Korzan |imię = Bohdan |tytuł = Grafy, hipergrafy i sieci |miejsce = Warszawa |rok = 1980 |odn = {{odn/id|Bohdan Korzan}}}}
* {{Cytuj |url = http://www.asdpb.republika.pl/gis1.pdf |tytuł = Podstawowe pojęcia dotyczące grafów |autor = Jolanta Koszelew |opublikowany = Algorytmy i struktury danych |odn = {{odn/id|Jolanta Koszelew}} |data dostępu = 2014-05-01 |archiwum = https://web.archive.org/web/20160109001141/http://www.asdpb.republika.pl/gis1.pdf |zarchiwizowano = 2016-01-09}}
* {{Cytuj |url = http://math.uni.lodz.pl/~kowalcr/65-66-67.pdf |tytuł = Grafy i metody ich przeszukiwania. Zastosowania |autor = Robert Kowalczyk |opublikowany = ydział Matematyki i Informatyki Uniwersytetu Łódzkiego |odn = {{odn/id|Robert Kowalczyk}} |data dostępu = 2014-05-01 |archiwum = https://web.archive.org/web/20140502031925/http://math.uni.lodz.pl/~kowalcr/65-66-67.pdf |zarchiwizowano = 2014-05-02}}
* {{Cytuj |url = http://www.mimuw.edu.pl/~kowalik/asd/2003/wyklady/w-grafy.pdf |tytuł = Algorytmy grafowe |autor = Łukasz Kowalik |opublikowany = Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego |odn = {{odn/id|Łukasz Kowalik}}}}
* {{Cytuj |url = http://prac.im.pwr.wroc.pl/~kuchta/grafy3_2014.pdf |tytuł = Teoria grafów |autor = Malgorzata Kuchta |opublikowany = Instytut Matematyki i Informatyki Politechniki Wrocławskiej |odn = {{odn/id|Małgorzata Kuchta}} |data dostępu = 2014-04-30 |archiwum = https://web.archive.org/web/20140502005354/http://prac.im.pwr.wroc.pl/~kuchta/grafy3_2014.pdf |zarchiwizowano = 2014-05-02}}
* {{Cytuj |url = http://yadda.icm.edu.pl/yadda/element/bwmeta1.element.baztech-643dcb54-ecd3-4992-ba91-daaab3f0b81f/c/Lewandowicz.pdf |tytuł = Drzewa grafowe w analizach dostępności |autor = Elżbieta Lewandowicz |opublikowany = CeON – Centrum Otwartej Nauki |odn = {{odn/id|Elżbieta Lewandowicz}}}}
* {{Cytuj książkę |nazwisko = Lipski |imię = Witold |nazwisko2 = Czajka |imię2 = Tomasz |tytuł = Kombinatoryka dla programistów |rok = 2004 |miejsce = Warszawa |isbn = 83-204-2968-4 |odn = {{odn/id|Witold Lipski, Tomasz Czajka}}}}
* {{Cytuj |url = http://zpgk.fais.uj.edu.pl/c/document_library/get_file?uuid=c1404da0-2c95-4d9f-8395-f38a58dfecfe&groupId=2349539 |tytuł = Matematyka dyskretna |autor = Andrzej Łachwa |opublikowany = Zakład Projektowania i Grafiki Komputerowej Uniwersytetu Jagiellońskiego |odn = {{odn/id|Andrzej Łachwa}}}}
* {{Cytuj |url = http://math.uni.lodz.pl/~marmaj/Files/grafyLic.pdf |tytuł = Teoria grafów i jej zastosowania |autor = Marek Majewski |opublikowany = Wydział Matematyki i Informatyki Uniwersytetu Łódzkiego |odn = {{odn/id|Marek Majewski, ''Teoria grafów i jej zastosowania''}}}}
* {{Cytuj |url = http://math.uni.lodz.pl/~marmaj/TGiS_W/tgis3.pdf |tytuł = Własności grafów |autor = Marek Majewski |opublikowany = Wydział Matematyki i Informatyki Uniwersytetu Łódzkiego |odn = {{odn/id|Marek Majewski, ''Własności grafów''}} |data dostępu = 2014-04-30 |archiwum = https://web.archive.org/web/20140502004533/http://math.uni.lodz.pl/~marmaj/TGiS_W/tgis3.pdf |zarchiwizowano = 2014-05-02}}
* {{Cytuj |url = http://www.msn.ap.siedlce.pl/smp/msn/51/a_zosia.pdf |tytuł = Kiedy zachłanność popłaca? |autor = Zofia Miechowicz |opublikowany = Ośrodek Kultury Matematycznej – Szkoła Matematyki Poglądowej |odn = {{odn/id|Zofia Miechowicz}} |data dostępu = 2014-04-27 |archiwum = https://web.archive.org/web/20140427195805/http://www.msn.ap.siedlce.pl/smp/msn/51/a_zosia.pdf |zarchiwizowano = 2014-04-27}}
* {{Cytuj |url = http://www.int.pjwstk.edu.pl/mad/index18.html |tytuł = Algorytmy grafowe |autor = Grażyna Mirkowska |opublikowany = Polsko-Japońska Wyższa Szkoła Technik Komputerowych |odn = {{odn/id|Grażyna Mirkowska}}}}
* {{Cytuj |url = http://users.uj.edu.pl/~palacz/edu/201011-AiSD2/wyklad08.pdf |tytuł = Algorytmy i struktury danych 2 |autor = Wojciech Palacz |opublikowany = Zakład Projektowania i Grafiki Komputerowej Uniwersytetu Jagiellońskiego |odn = {{odn/id|Wojciech Palacz}} |data dostępu = 2014-05-01 |archiwum = https://web.archive.org/web/20140502003714/http://users.uj.edu.pl/~palacz/edu/201011-AiSD2/wyklad08.pdf |zarchiwizowano = 2014-05-02}}
* {{Cytuj |url = http://matmauksw.ovh.org/dyskretna/MAD-w02.pdf |tytuł = Pojęcia wstępne teorii grafów |opublikowany = V rok Wydziału Matematyczno-Przyrodniczego Uniwersytetu Kardynała Stefana Wyszyńskiego |odn = {{odn/id|''Pojęcia wstępne teorii grafów''}} |data dostępu = 2014-05-01 |archiwum = https://web.archive.org/web/20140502004938/http://matmauksw.ovh.org/dyskretna/MAD-w02.pdf |zarchiwizowano = 2014-05-02}}
* {{Cytuj książkę |nazwisko = Ross |imię = Kenneth A. |nazwisko2 = Wright |imię2 = Charles R.B. |tytuł = Matematyka dyskretna |miejsce = Warszawa |rok = 2005 |isbn = 83-0114-380-0 |odn = {{odn/id|Kenneth A. Ross, Charles R.B. Wright}}}}
* {{Cytuj |url = http://www.combinatorialmath.ca/g&g/articles/torus.pdf |tytuł = Drawing Graphs on the Torus |autor = William Kocay, Daniel Neilson, Ryan Szypowski |opublikowany = University of Manitoba |odn = {{odn/id|William Kocay, Daniel Neilson, Ryan Szypowski}} |data dostępu = 2021-06-05 |archiwum = https://web.archive.org/web/20170829015125/http://www.combinatorialmath.ca/g%26g/articles/torus.pdf |zarchiwizowano = 2017-08-29}}
* {{Cytuj książkę |nazwisko = Kulikowski |imię = Juliusz Lech |tytuł = Zarys teorii grafów. Zastosowanie w technice |miejsce = Warszawa |rok = 1986 |isbn = 83-0105-277-5 |odn = {{odn/id|Juliusz Lech Kulikowski}}}}
* {{Cytuj stronę |url = http://www.staff.amu.edu.pl/~rucinski/tgr430/wiosna09/w5.pdf |tytuł = ''Teoria grafów 2 (TGR 430) – wiosna 2009'', Cz. 4, ''2-spójność, 3-spójność'' |autor = Andrzej Ruciński |opublikowany = Zakład Matematyki Dyskretnej Uniwersytetu im. Adama Mickiewicza |odn = {{odn/id|Andrzej Ruciński}}}}
* {{Cytuj |url = http://www.cs.put.poznan.pl/arybarczyk/GrafReprezentacje.htm |tytuł = ALG – Reprezentacje grafów |autor = Agnieszka Rybarczyk |opublikowany = Instytut Informatyki Politechniki Poznańskiej |odn = {{odn/id|Agnieszka Rybarczyk}}}}
* {{Cytuj |url = http://www.mini.pw.edu.pl/MiNIwyklady/grafy/def-stopien.html |tytuł = Stopień wierzchołka |opublikowany = Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej |odn = {{odn/id|''Stopień wierzchołka''}}}}
* {{Cytuj |url = http://www.mini.pw.edu.pl/MiNIwyklady/grafy/grafy.html |tytuł = Teoria grafów |opublikowany = Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej |odn = {{odn/id|''Teoria grafów''}}}}
* {{Cytuj |url = http://paweljw.eu/pub/dyskretna.pdf |tytuł = Matematyka dyskretna |autor = Paweł Wal |opublikowany = Paweł J. Wal |odn = {{odn/id|Paweł Wal}} |data dostępu = 2014-04-30 |archiwum = https://web.archive.org/web/20140501235918/http://paweljw.eu/pub/dyskretna.pdf |zarchiwizowano = 2014-05-01}}
* {{Cytuj |url = http://edu.i-lo.tarnow.pl/inf/alg/001_search/0123.php |tytuł = Podstawowe pojęcia dotyczące grafów |autor = Jerzy Wałaszek |opublikowany = I Liceum Ogólnokształcące im. Kazimierza Brodzińskiego w Tarnowie |odn = {{odn/id|Jerzy Wałaszek, ''Podstawowe pojęcia dotyczące grafów''}} |data dostępu = 2014-05-01 |archiwum = https://web.archive.org/web/20140502005549/http://edu.i-lo.tarnow.pl/inf/alg/001_search/0123.php |zarchiwizowano = 2014-05-02}}
* {{Cytuj |url = http://edu.i-lo.tarnow.pl/inf/utils/001_2008/0600.php |tytuł = Teoria grafów dla początkujących. Reprezentacja grafów w pamięci komputera |autor = Jerzy Wałaszek |opublikowany = I Liceum Ogólnokształcące im. Kazimierza Brodzińskiego w Tarnowie |odn = {{odn/id|Jerzy Wałaszek, ''Teoria grafów dla początkujących''}} |data dostępu = 2014-05-01 |archiwum = https://web.archive.org/web/20140502005551/http://edu.i-lo.tarnow.pl/inf/utils/001_2008/0600.php |zarchiwizowano = 2014-05-02}}
* {{Cytuj książkę |nazwisko = Wilson |imię = Robin J. |tytuł = Wprowadzenie do teorii grafów |miejsce = Warszawa |rok = 1998 |isbn = 83-0112-641-8 |odn = {{odn/id|Robin J. Wilson}}}}
* {{Cytuj |url = http://www.staff.amu.edu.pl/~awisniew/logika_1/02.Dzialania%20na%20zbiorach.pdf |tytuł = Logika I. Materiały do wykładu dla studentów kognitywistyki. Wykład 2. Działania na zbiorach |autor = Andrzej Wiśniewski |opublikowany = Zakład Matematyki Dyskretnej Uniwersytetu im. Adama Mickiewicza |odn = {{odn/id|Andrzej Wiśniewski}} |data dostępu = 2014-05-01 |archiwum = https://web.archive.org/web/20140502001606/http://www.staff.amu.edu.pl/~awisniew/logika_1/02.Dzialania%20na%20zbiorach.pdf |zarchiwizowano = 2014-05-02}}
* {{Cytuj |url = http://www.staff.amu.edu.pl/~rmiw/en/multikolorowanie.pdf |tytuł = Multikolorowanie grafów |autor = Rafał Witkowski |opublikowany = X Międzynarodowe Warsztaty Młodych Matematyków |data = 2007 |odn = {{odn/id|Rafał Witkowski}} |data dostępu = 2015-11-18 |archiwum = https://web.archive.org/web/20151119092534/http://www.staff.amu.edu.pl/~rmiw/en/multikolorowanie.pdf |zarchiwizowano = 2015-11-19}}
* {{Cytuj |url = http://www.jakubw.pl/zajecia/nai/NAI_07.pdf |tytuł = Problemy optymalizacyjne – zastosowania |autor = Jakub Wróblewski |opublikowany = Jakub Wróblewski |odn = {{odn/id|Jakub Wróblewski}}}}
* {{Cytuj |url = http://www.teachengineering.org/view_lesson.php?url=collection/uno_/lessons/uno_graphtheory/uno_graphtheory_lesson01.xml |tytuł = Graph Theory in Drama |autor = Ramsey Young, Brian Sandall |opublikowany = University of Colorado |odn = {{odn/id|Ramsey Young, Brian Sandall}} |data dostępu = 2021-06-05 |archiwum = https://web.archive.org/web/20160406030512/https://www.teachengineering.org/view_lesson.php?url=collection%2Funo_%2Flessons%2Funo_graphtheory%2Funo_graphtheory_lesson01.xml |zarchiwizowano = 2016-04-06}}
* {{Cytuj |url = http://zuraw.iostrow.com/documents/students/materialy/matd_wyk7.pdf |tytuł = Grafy |autor = Marcin Żurawski |opublikowany = Marcin Żurawski |odn = {{odn/id|Marcin Żurawski}}}}
}}

== Linki zewnętrzne ==
{{Commonscat|Graphs (graph theory)}}
{{wikisłownik|graf}}
* {{Cytuj |url = https://primes.utm.edu/graph/ |tytuł = Graph theory tutorial |autor = Chris K. Caldwell |opublikowany = The University of Tennessee}}
* {{Cytuj |url = http://students.ceid.upatras.gr/~papagel/project/contents.htm |tytuł = Algorithms. Tutoring web page}} – Aplety obrazujące niektóre algorytmy teorii grafów.
* {{Cytuj |url = http://www.mpi-inf.mpg.de/~lkowalik/phd.pdf |tytuł = Algorytmiczne problemy ścieżkowe w grafach planarnych. Rozprawa doktorska |autor = Łukasz Kowalik |opublikowany = Max Planck Institut Informatik |data dostępu = 2014-05-01 |archiwum = https://web.archive.org/web/20110813035255/http://www.mpi-inf.mpg.de/~lkowalik/phd.pdf |zarchiwizowano = 2011-08-13}}

{{Relacje matematyczne}}
{{Wielościany}}
{{Teoria grafów}}

{{Kontrola autorytatywna}}

[[Kategoria:Grafy| ]]