Grafy i sieci

Grafem zorientowanym nazywać będziemy parę $G=(V,A)$, gdzie $V$ jest dowolnym skończonym zbiorem niepustym, nazywanym zbiorem wierzchołków, zaś $A$ pewnym podzbiorem zbioru dwuelementowych par $(x,y)\in V^2$ takich, że $x \neq y$. $x$ jest wtedy początkiem zaś $y$ końcem łuku $e=(x,y)$. $x$ i $y$ nazywamy^8.3 końcami łuku $(x,y)$. Jeśli $(x,y)\in A$ to mówimy, że wierzchołki $x$ i $y$ są połączone w $G$. Łuk $(x,y)$ jest wtedy incydentny z wierzchołkami $x$ i $y$. Rzędem grafu $G$ nazywamy liczbę $\vert V\vert$, zaś rozmiarem $G$ liczbę $\vert A\vert$. Elementy zbioru $A$ nazywamy łukami.
Dla wierzchołka $x\in V$ przez $N_G^+(x)$ nazywamy zbiór tych wierzchołków $y$ dla których $(x,y)\in A$, zaś $N_G^-(x)=\{ y: (y,x) \in A\}$.
Graf zorientowany (będziemy, dla wygody, mówili czasami po prostu graf) ma bardzo prostą interpretację graficzną: elementy zbioru $V$ (a więc wierzchołki grafu) będziemy przedstawiali jako punkty płaszczyzny, zaś łuki jako zakończone strzałkami linie łaczące odpowiednie wierzchołki.

Przykład 8.1   Graf $G=(\{ v_1,v_2,v_3\},\{ e_1= (v_1,v_3), e_2= (v_3,v_1),e_3=(v_1,v_2),e_4=(v_3,v_2)\} )$ interpretujemy tak, jak to zostało przedstawione na rysunku 8.1.

Z tak jak powyżej zdefiniowanym grafem zorientowanym można skojarzyć wzajemnie jednoznacznie dwie macierze: macierz sąsiedztw i macierz incydencji.