Macierz sąsiedztw grafu zorientowanego

Niech $G=(V,A)$ będzie pewnym grafem zorientowanym o $n$ wierzchołkach $\{ v_1,...,v_n\}$. Wtedy macierz $T \in {\bf R}^{n\times n}=(a_{ij})_{i,j=1,...,n}$ zdefiniowaną wzorami

$$s_{ij}= \left\{ \begin{array}{lr} 1 & \mbox{jeśli } (v_i... ... 0 & \mbox{jeśli } (v_i,v_j) \notin A \end{array} \right.$$

Dla grafu z rysunku 8.1 macierz sąsiedztw jest postaci

$$T = \left[ \begin{array}{rrr} 0 & 1& 1 \\ 0 & 0 & 0 \\ 1 & 1 & 0 \end{array} \right]$$

Zauważmy, że skoro założyliśmy, że dla dowolnego łuku $(x,y)$ zachodzi $x \neq y$, macierz sąsiedztw ma same zera na przekątnej głównej.