Trasy, ścieżki, drogi
Trasą w grafie $G$ nazywamy skończony ciąg krawędzi postaci:
$$v_{0} v_{1},v_{1} v_{2},\ldots,v_{m-1} v_{m}$$
w którym każde dwie kolejne krawędzie są albo sąsiednie, albo identyczne. W innych oznaczeniach trasy typu:
$$v_0 \to v_1 \to v_2 \to \ldots \to v_m$$
wyrazami ciągu są wierzchołki. $v_0$ nazywamy wierzchołkiem początkowym trasy, a $v_m$ wierzchołkiem końcowym trasy. Możemy również powiedzieć, że jest to trasa od wierzchołka $v_0$ do wierzchołka $v_m$. Długością trasy nazywamy liczbą krawędzi na trasie.
Ścieżką nazywamy trasę, w której wszystkie krawędzie są różne. Jeśli na ścieżce różne są też wszyskie wierzchołki (z wyjątkiem równości $v_0=v_m$), to ścieżkę tę nazwiemy drogą. Droga lub ścieżka są zamknięte, jeśli $v_0=v_m$. Cyklem nazywamy ścieżkę zamkniętą zawierającą co najmniej jedną krawędź, dlatego też każda pętla lub para krawędzi wielokrotnych jest cyklem.
Warto również wspomnieć o kilku twierdzeniach związanych z omawianym tematem:
- Jeśli graf $G$ jest grafem dwudzielnym, to każdy cykl ma długość parzystą.
- Jeśli graf $G$ jest spójnym grafem, prostym to jego liczba krawędzi $m$ musi być zawarta między $m-1$ a $m(m-1)/2$.
- Jeśli graf prosty $G$ ma $n$ wierzchołków oraz $k$ składowych, to liczba $m$ jego krawędzi spełnia nierówności $$n-k \le m \le \frac{(n-k)(n-k+1)}{2}$$.
- Każdy graf prosty który ma $n$ wierzchołków i liczba $m$ jego krawędzi spełnia nierówność $$\frac{(n-1)(n-2)}{2} \lt m$$ jest spójny.
Grafy eulerowskie
Graf spójny $G$ jest grafem eulerowskim, jeśli istnieje zamknięta ścieżka zawierająca każdą krawędź grafu $G$, wtedy cyklem Eulera nazywamy właśnie taką ścieżkę. Pomimo tego, że wymagamy od cyklu aby przechodził przez dany wierzchołek najwyżej raz, tak w przypadku cyklu Eulera ze względu na zbyt częte użycie nazwy "cykl Eulera" postanowino uczynić pewien wyjątek (w innych źródłach spotykana jest nazwa "ścieżka Eulera", która oznacza to samo). Graf $G$ nazwiemy grafem półeulerowskim, jeśli nie posiada cyklu Eulera, a istnieje ścieżka zawierająca każdą krawędź grafu $G$. W grafie półeulerowskim każda ścieżka Eulera musi zaczynać się w jednym wierzchołku nieparzystego stopnia, a kończyć się na drugim wierzchołku również nieparzystego stopnia.
Istnieje kilka warunków koniecznych do tego by dany graf był grafem eulerowskim, półeulerowskim lub zawierał cykl.
- Graf $G$ zawiera cykl, jeśli każdy wierzchołek grafu $G$ ma stopień równy co najmniej $2$.
- Graf spójny $G$ jest grafem eulerowskim wtedy i tylko wtedy, gdy stopień każdego wierzchołka grafu $G$ jest liczbą parzystą (Euler, 1736 - rozwiązanie problemu mostów królewieckich).
- Graf spójny jest grafem eulerowskim wtedy i tylko wtedy, gdy jego zbiór krawędzi można podzielić na rozłączne cykle.
- Graf spójny jest grafem półeulerowskim wtedy i tylko wtedy, gdy ma dokładnie dwa wierzchołki stponia nieparzystego.
Grafy hamiltonowskie
Graf spójny $G$ jest hamiltonowski, jeśli istnieje zamknięta ścieżka przechodząca przez każdy wierzchołek tylko jeden raz i zawierająca wszystkie wierzchołki grafu $G$. Taką ścieżkę nazywamy cyklem Hamiltona, który nie będzie cyklem tylko w przypadku gdy graf $G$ jest grafem pustym $N_1$. Wynika to z faktu mówiącego o tym, iż cykl musi zawierać co najmniej jedną krawędź. Graf $G$ który nie jest grafem hamiltonowkim, nazywamy półhamiltonowskim, jeśli istnieje droga przechodząca przez każdy wierzchołek dokładnie jeden raz.
Pomimo istnienia kilku warunków koniecznych do tego, by dany graf był eulerowski, tak istninie podobnych dla grafów hamiltonowskih jest prawdopodobnie największą tajemnicą teorii grafów. Udało się jednak wyprowadzić kilka, szczególnie istotnych twierdzeń. Autorami najsłynniejszych są Gabriel Andrew Dirac i Øystein Ore.
- Jeśli graf prosty $G$ ma $n$ wierzchołków (gdzie $n \ge 3$) oraz: $$ \deg(v) + \deg(w) \ge n $$ dla każdej pary wierzchołków niesąsiednich v i w, to graf jest hamiltonowski (Ore, 1960).
- Jeśli w grafie prostym $G$, który ma $n$ wierzchołków (gdzie $n \ge 3$), a $$\deg(v) \ge \frac{n}{2}$$ dla każdego wierzchołka $v$, to graf $G$ jest hamiltonowski (G. A. Dirac, 1952).
- Jeśli graf prosty o $n$ wierzchołkach ma co najmniej $m$ krawędzi, gdzie: $$ m = \frac{(n-1)(n-2)}{2} + 2 $$ to jest hamiltonowski (Twierdzenie o liczbie krawędzi).
