Wyruszając w daleką podróż zabieramy ze sobą mapę samochodową. Głównymi elementami graficznymi zawartymi w mapie są punkty (małe kółka) symbolizujące miasta, oraz odcinki (lub łuki) obrazujące drogi pomiędzy nimi. Taka mapa jest z grubsza przedstawieniem rzeczywistości za pomocą grafu. Chcąc na przykład znaleźć drogę z Bydgoszczy do Krakowa, szukamy ciągu kolejno połączonych miast zaczynającego się w Bydgoszczy i kończącego się w Krakowie. Jest to nic innego, jak znalezienie odpowiedniej ścieżki w grafie połączeń między miastami.
Graf to para \( \mathbf{G}=( V,E ) \), gdzie:
(czasami zwanymi węzłami lub punktami grafu)
czyli jedno- i dwu-elementowych podzbiorów \( V \).
Graf prosty to para \( \mathbf{G}=( V,E ) \), gdzie:
czyli dwu-elementowych podzbiorów \( V \).
Graf ogólny (a.) oraz prosty (b.)
Uwaga
W grafie w odróżnieniu od grafu prostego dopuszczamy pętle oraz krawędzie wielokrotne. Wierzchołek nazywany jest czasem także węzłem, jak i punktem grafu. Krawędź łącząca \( v \) z \( w \) oznaczana będzie jako \( vw \). Jeśli istnieje krawędź \( vw \) to mówimy, że \( v \) i \( w \) są sąsiadami; oraz że krawędź \( vw \) jest incydentna do \( v \) (\( w \)). Ponadto, dla grafu \( \mathbf{G} \) symbolem \( {\sf V}\!(\mathbf{G}) \) będziemy oznaczać jego zbiór wierzchołków, zaś symbolem \( {\sf E}\!(\mathbf{G}) \) jego zbiór krawędzi. Czasem, dla odróżnienia grafu od grafu prostego, graf będziemy nazywać też grafem ogólnym.
Stopień wierzchołka \( v \) w grafie \( \mathbf{G} \) to liczba krawędzi incydentnych z \( v \). Stopień wierzchołka \( v \) oznaczany jest jako \( {\sf deg}\ v \).
Obserwacja 12.1
Jeśli \( \mathbf{G}=( V,E ) \) jest grafem ogólnym, to
\( \displaystyle\sum_{v\in V}{\sf deg}\ v=2\vert E \vert. \)
A zatem liczba wierzchołków o nieparzystym stopniu jest parzysta.
Dowód
Każda krawędź jest incydentna do dwóch wierzchołków. Zliczając krawędzie incydentne do kolejnych wierzchołków, a następnie sumując te wartości, każda krawędź \( vw \) zostanie zliczona dwa razy: raz przy rozpatrywaniu wierzchołka \( v \), a drugi raz przy \( w \).
Jeśli \( \mathbf{G} \) miałby nieparzyście wiele wierzchołków o nieparzystym stopniu to suma \( \displaystyle\sum_{v\in V}{\sf deg}\ v \) byłaby nieparzysta, wbrew temu, że jest liczbą parzystą \( 2\vert E \vert \).
Uwaga
Dla grafów \( \mathbf{G}=( V,E ) \), \( \mathbf{G}_1=( V_1,E_1 ) \), \( \mathbf{G}_2=( V_2,E_2 ) \) definiujemy następujące pojęcia:
\( \mathbf{G}/\theta=( V/\theta,\lbrace \lbrace v/\theta,w/\theta \rbrace:\lbrace v,w \rbrace\in E \rbrace ), \)
W dotychczasowej interpretacji grafów, jako mapy dróg zakładaliśmy, że istnienie drogi np. z Krakowa do Zakopanego, gwarantowało także możliwość powrotu po tej samej trasie. To oczywiście nie musi być zawsze prawdą, np. w miastach jest wiele dróg jednokierunkowych. Chcąc rozważać również takie jednokierunkowe trasy, tzn uwzględniać kierunek relacji między dwoma obiektami, będziemy mówić o grafach skierowanych.
Graf skierowany (lub inaczej digraf) to para \( \mathbf{D}=( V,E ) \), gdzie
Uwaga
Krawędź digrafu (czyli uporządkowaną parę) \( vw \) graficznie przedstawiamy jako strzałkę \( v\ \bullet\!\longrightarrow\!\bullet\ w \).
Graf szkieletowy digrafu \( \mathbf{D} \) to graf otrzymany z \( \mathbf{D} \) poprzez zaniedbanie (usunięcie) kierunku krawędzi, ale nie samych krawędzi.