Definicje w teorii grafów są różne. Poniżej przedstawiono niektóre z bardziej podstawowych sposobów definiowania grafów i związanych z nimi struktur matematycznych.
GraphEdit
Graf (czasami nazywany grafem nieskierowanym dla odróżnienia od grafu skierowanego, lub grafem prostym dla odróżnienia od multigrafu) to para G = (V, E), gdzie V jest zbiorem, którego elementy nazywane są wierzchołkami (singular: vertex), a E jest zbiorem sparowanych wierzchołków, których elementy nazywane są krawędziami (czasami linkami lub liniami).
Wierzchołki x i y krawędzi {x, y} nazywamy punktami końcowymi krawędzi. Mówi się, że krawędź łączy x i y i jest incydentna na x i y. Wierzchołek może nie należeć do żadnej krawędzi, wtedy nie jest połączony z żadnym innym wierzchołkiem.
Multigraf jest uogólnieniem, które pozwala wielu krawędziom mieć tę samą parę wierzchołków. W niektórych tekstach multigrafy są po prostu nazywane grafami.
Czasami grafy mogą zawierać pętle, czyli krawędzie, które łączą wierzchołek z samym sobą. Aby dopuścić pętle, powyższa definicja musi zostać zmieniona poprzez zdefiniowanie krawędzi jako multizbiorów dwóch wierzchołków zamiast dwóch zbiorów. Takie uogólnione grafy nazywamy grafami z pętlami lub po prostu grafami, gdy z kontekstu wynika, że pętle są dozwolone.
Generalnie, zbiór wierzchołków V ma być skończony; implikuje to, że zbiór krawędzi jest również skończony. Grafy nieskończone są czasami rozważane, ale są częściej postrzegane jako szczególny rodzaj relacji binarnej, ponieważ większość wyników dotyczących grafów skończonych nie rozszerza się na przypadek nieskończony, lub wymaga raczej innego dowodu.
Graf pusty to graf, który ma pusty zbiór wierzchołków (i tym samym pusty zbiór krawędzi). Porządek grafu to liczba jego wierzchołków |V|. Rozmiar grafu to liczba jego krawędzi |E|. Jednak w niektórych kontekstach, np. do wyrażania złożoności obliczeniowej algorytmów, rozmiar to |V| + |E| (w przeciwnym razie graf niepusty mógłby mieć rozmiar 0). Stopień lub walencja wierzchołka to liczba krawędzi, które do niego przylegają; w przypadku grafów z pętlami, pętla jest liczona podwójnie.
W grafie rzędu n maksymalny stopień każdego wierzchołka wynosi n – 1 (lub n, jeśli dozwolone są pętle), a maksymalna liczba krawędzi wynosi n(n – 1)/2 (lub n(n + 1)/2, jeśli dozwolone są pętle).
Krawędzie grafu definiują symetryczną relację na wierzchołkach, zwaną relacją przyległości. W szczególności, dwa wierzchołki x i y są sąsiadujące, jeśli {x, y} jest krawędzią. Graf może być w pełni określony przez jego macierz adjacency A, która jest macierzą n × n {{displaystyle n}}.
macierz kwadratowa, gdzie Aij określa liczbę połączeń z wierzchołka i do wierzchołka j. Dla grafu prostego A i j ∈ { 0 , 1 } {displaystyle A_{ij}}
, oznaczające odpowiednio rozłączenie lub połączenie, natomiast A i i = 0 {displaystyle A_{ii}=0}
(czyli krawędź nie może zaczynać się i kończyć w tym samym wierzchołku). Grafy z samopętlami będą charakteryzowały się pewnymi lub wszystkimi A i i {{displaystyle A_{ii}}
być równe dodatniej liczbie całkowitej, a multigrafy (z wieloma krawędziami między wierzchołkami) będą się charakteryzować tym, że niektóre lub wszystkie A i j {displaystyle A_{ij}}
jest równa dodatniej liczbie całkowitej. Grafy nieskierowane będą miały symetryczną macierz adjacencji ( A i j = A j i {{displaystyle A_{ij}=A_{ji}}).
).
Graf skierowanyEdit
Graf skierowany lub digraf jest grafem, w którym krawędzie mają orientacje.
W jednym ograniczonym, ale bardzo powszechnym znaczeniu tego terminu, graf skierowany jest parą G = ( V , E ) {{displaystyle G=(V,E)}
składający się z:
- V {displaystyle V}
, zbiór wierzchołków (zwanych też węzłami lub punktami);
- E ⊆ { ( x , y ) ∣ ( x , y ) ∈ V 2 i x ≠ y } {{displaystyle E}subseteq \{(x,y)\mid (x,y)\ w V^{2}};{textrm {and}};x \neq y}}
, zbiór krawędzi (zwanych również krawędziami skierowanymi, połączeniami skierowanymi, liniami skierowanymi, strzałkami lub łukami), które są uporządkowanymi parami wierzchołków (to znaczy, że krawędź jest związana z dwoma różnymi wierzchołkami).
Aby uniknąć niejednoznaczności, tego typu obiekt można nazwać właśnie grafem prostym skierowanym.
W krawędzi ( x , y ) {przykład (x,y)}
skierowana od x {{displaystyle x}
do y {{displaystyle y}
, wierzchołki x {displaystyle x}
i y {displaystyle y}
nazywane są punktami końcowymi krawędzi, x {displaystyle x}
ogonem krawędzi, a y {displaystyle y}
głowa krawędzi. Mówi się, że krawędź łączy x {displaystyle x}
i y {displaystyle y}
i być zdarzenie na x {displaystyle x}
i na y {displaystyle y}
. Wierzchołek może istnieć w grafie i nie należeć do krawędzi. Krawędź ( y , x ) {displaystyle (y,x)}
nazywamy krawędzią odwróconą z ( x , y ) {displaystyle (x,y)}
. Wielokrotne krawędzie, niedozwolone w powyższej definicji, to dwie lub więcej krawędzi mających zarówno ten sam ogon, jak i tę samą głowę.
W jednym z bardziej ogólnych znaczeń tego terminu, dopuszczającym wiele krawędzi, graf skierowany jest uporządkowaną trójką G = ( V , E , ϕ ) {{displaystyle G=(V,E,ϕ )}
składający się z:
- V {{displaystyle V}
, zbiór wierzchołków (zwanych również węzłami lub punktami);
- E {displaystyle E}
, zbiór krawędzi (zwanych też krawędziami skierowanymi, linkami skierowanymi, liniami skierowanymi, strzałkami lub łukami);
- ϕ : E → { ( x , y ) ∣ ( x , y ) ∈ V 2 i x ≠ y } {displaystyle \\phi :E\to \{(x,y)\mid (x,y)\ w V^{2}};{textrm {i}};x \neq y}}.
, funkcja incydencji odwzorowująca każdą krawędź na uporządkowaną parę wierzchołków (to znaczy, że krawędź jest związana z dwoma różnymi wierzchołkami).
Aby uniknąć niejednoznaczności, tego typu obiekt można nazwać właśnie multigrafem skierowanym.
Pętla to krawędź, która łączy wierzchołek z samą sobą. Grafy skierowane zdefiniowane w dwóch powyższych definicjach nie mogą mieć pętli, ponieważ pętla łącząca wierzchołek x {{displaystyle x}
do samej siebie jest krawędzią (dla skierowanego grafu prostego) lub jest incydentna na (dla skierowanego multigrafu) ( x , x ) {{displaystyle (x,x)}
która nie jest w { ( x , y ) ∣ ( x , y ) ∈ V 2 i x ≠ y } {{displaystyle \{(x,y)\ w V^{2}};{textrm {and}};x \neq y}}.
. Tak więc, aby umożliwić pętle, definicje muszą zostać rozszerzone. Dla skierowanych grafów prostych, definicja E {{displaystyle E}
należy zmodyfikować do E ⊆ { ( x , y ) ∣ ( x , y ) ∈ V 2 } {{displaystyle E ⊆ {(x,y)∣ ( x,y)∈ V 2 }}.
. Dla multigrafów skierowanych, definicja ϕ {displaystyle \\\\\\i }
powinna zostać zmodyfikowana do ϕ : E → { ( x , y ) ∣ ( x , y ) ∈ V 2 } { {displaystyle \phi :E \to \{(x,y)\mid (x,y)\ w V^{2}}.
. Aby uniknąć niejednoznaczności, tego typu obiekty można nazwać właśnie skierowanym grafem prostym dopuszczającym pętle i skierowanym multigrafem dopuszczającym pętle (lub kołczanem) odpowiednio.
Krawędzie skierowanego grafu prostego zezwalającego na pętle G {\i0}
jest relacją jednorodną ~ na wierzchołkach G {{displaystyle G}}
która jest nazywana relacją adjacency G {displaystyle G}.
. W szczególności, dla każdej krawędzi ( x , y ) {displaystyle (x,y)}
, jej punktów końcowych x {{displaystyle x}
i y {{displaystyle y}
mówi się, że są sąsiadujące ze sobą, co oznacza się jako x {displaystyle x}
~ y {displaystyle y}
.
Wykres mieszanyEdit
Graf mieszany to graf, w którym niektóre krawędzie mogą być skierowane, a niektóre nieskierowane. Jest to trójka uporządkowana G = (V, E, A) dla grafu mieszanego prostego oraz G = (V, E, A, ϕE, ϕA) dla multigrafu mieszanego z V, E (krawędzie nieskierowane), A (krawędzie skierowane), ϕE i ϕA zdefiniowanymi jak wyżej. Grafy skierowany i nieskierowany są przypadkami szczególnymi.
Ważony grafEdit
Ważony graf lub sieć to graf, w którym do każdej krawędzi przypisana jest liczba (waga). Takie wagi mogą reprezentować np. koszty, długości lub pojemności, w zależności od rozpatrywanego problemu. Takie grafy pojawiają się w wielu kontekstach, na przykład w problemach najkrótszej ścieżki, takich jak problem podróżującego komiwojażera.