Macierz incydencji

Macierzą incydencji grafu zorientowanego $G=(V,A)$ o zbiorze wierzchołków $V=\{ v_1,...,v_n\}$ i zbiorze łuków $A=\{ e_1,..., e_m\}$, nazywamy macierz $N=(b_{ij})_{ \begin{array}{c} i=1,...,n\\ j=1,...,m \end{array}}$ taką, że

$$b_{ij}= \left\{ \begin{array}{rl} 1 & \mbox{jeśli } v_i \... ...mbox{ i } e_j \mbox{ nie są incydentne} \end{array} \right.$$

Przykład 8.1   Dla grafu z rysunku 8.1 macierzą incydencji jest

$$N= \left[ \begin{array}{rrrr} 1 & -1 & 1 & 0 \\ 0 & 0 & -1 & -1 \\ -1 & 1 & 0 & 1 \end{array} \right]$$

Wobec tego co wiemy z podrozdziału o macierzach totalnie unimodularnych (wniosek ) ważne będą konsekwencje poniższego twierdzenia.

Twierdzenie 8.1   Macierz incydencji grafu zorientowanego jest totalnie unimodularna.

Dowód. Wykorzystamy twierdzenie . Zauważmy, że w macierzy incydencji dowolnego grafu zorientowanego każdej kolumnie odpowiada pewien łuk grafu i są w niej dwa wyrazy różne od zera: $-1$ i $1$ w wierszach odpowiadających początkowi i końcowi łuku. Wystarczy więc przyjąć jako zbiory $W_1$ i $W_2$ występujące w założeniach twierdzenia zbiór wszystkich wierszy macierzy incydencji grafu i zbiór pusty.