Informatyka MIMUW

Metody algebraiczne w teorii grafów

Graf regularny stopnia $r$ to graf, w którym wszystkie wierzchołki mają stopień $r$.
Graf taki nazywany jest także $r$-regularnym.

Maksymalny stopień wierzchołka w grafie $\mathbf{G}$, oznaczany przez $\Delta( \mathbf{G} )$ to

$\Delta( \mathbf{G} ):=\max\lbrace {\sf deg}\ v:\ v\in{\sf V}\!(G) \rbrace.$

Macierz sąsiedztwa ${\sf A}( \mathbf{G} )$ grafu prostego $\mathbf{G}=( \lbrace v_1,\ldots,v_n \rbrace,E )$ to zero-jedynkowa macierz $\langle a_{ij} \rangle$ rozmiaru $n\times n$, gdzie

$a_{ij}= \left \{ \begin{array} {l} 1, & \textrm{jeżeli}\ v_i v_j\in E, \\ 0, & \textrm{w przeciwnym wypadku.} \end{array} \right.$

Uwaga

Macierz sąsiedztwa grafu nieskierowanego jest symetryczna.

Przykład

Na rysunku Graf prosty przedstawiono graf prosty $\mathbf{G}_0$ o wierzchołkach $v_0,\ldots,v_5$ oraz graf skierowany $\mathbf{G}_1$ o wierzchołkach $u_1,\ldots,u_5$. Macierze sąsiędztwa grafów $\mathbf{G}_0$ oraz $\mathbf{G}_1$ wyglądają następująco:

${\sf A}( \mathbf{G}_0 )=\left[ \begin{array} {ccccc} 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 \end{array} \right],\quad {\sf A}( \mathbf{G}_1 )=\left[ \begin{array} {ccccc} 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right ].$

Domknięcie przechodnie grafu skierowanego $\mathbf{G}$, to graf ${\sf TC}( \mathbf{G} )$ taki, że:

• ${\sf V}\!({\sf TC}( \mathbf{G} ))={\sf V}\!(\mathbf{G})$, oraz
• $( v,w )\in{\sf E}\!({\sf TC}( \mathbf{G} ))$

wtedy i tylko wtedy, gdy w grafie $\mathbf{G}$ istnieje skierowana marszruta z $v$ do $w$.

Twierdzenie 15.1

Niech $\mathbf{G}=( \lbrace v_1,\ldots,v_n \rbrace,E )$ będzie grafem skierowanym. Wtedy liczba skierowanych marszrut z $v_i$ do $v_j$ jest dana elementem $a_{ij}$ macierzy:

$\langle a_{ij} \rangle ={\sf A}( \mathbf{G} )^1+{\sf A}( \mathbf{G} )^2+\ldots+{\sf A}( \mathbf{G} )^{( n-1 )}.$

Dowód

Wystarczy pokazać, że

(*) $\langle a'_{ij} \rangle ={\sf A}( \mathbf{G} )^k$ jest macierzą, w której $a'_{ij}$ jest liczbą skierowanych marszrut z $v_i$ do $v_j$ o długości $k$.

Dowód własności (*) przeprowadzimy indukcją względem $k$. Macierz ${\sf A}( \mathbf{G} )^1$ jest macierzą sąsiedztwa, co natychmiast daje (*) dla $k=1$. Niech teraz $k>1$. Oczywiście

${\sf A}( \mathbf{G} )^k = {\sf A}( \mathbf{G} )^{k-1}\cdot{\sf A}( \mathbf{G} ).$

Jeśli więc $\langle a_{ij} \rangle ={\sf A}( \mathbf{G} )$, $\langle a'_{ij} \rangle ={\sf A}( \mathbf{G} )^k$, oraz $\langle a''_{ij} \rangle ={\sf A}( \mathbf{G} )^{k-1}$, to

$a'_{ij}=a''_{i1}a_{1j}+\ldots+a''_{in}a_{nj}.$

Wartość $a''_{il}$ to liczba wszystkich skierowanych marszrut z $v_i$ do $v_l$ o długości $k-1$. Tak więc iloczyn $a''_{il}a_{lj}$ jest równy liczbie wszystkich skierowanych $k$-elementowych marszrut mających postać $v_i\to\ldots\to v_l\to v_j$, czyli takich skierowanych marszrut z $v_i$ do $v_j$ o $k$ elementach, których przedostatni wierzchołek to $v_l$. Sumując te wartości po wszystkich $l$, czyli dopuszczając dowolny wierzchołek $v_l$ jako przedostatni, otrzymujemy liczbę wszystkich $k$-elementowych skierowanych marszrut z $v_i$ do $v_j$. To kończy dowód (*), a zatem i całego twierdzenia.

Graf $\mathbf{G}_2$ (a) oraz jego przechodnie domknięcie $\mathbf{G}_3={\sf TC}( \mathbf{G}_2 )$ (b)

Przykład

Grafy $\mathbf{G}_2=( \lbrace u_1,\ldots,u_5 \rbrace,E )$ i $\mathbf{G}_3=( \lbrace u_1,\ldots,u_5 \rbrace,E' )$ zostały przedstawione na animacji.

Macierz sąsiedztwa grafu $\mathbf{G}_2$ to

${\sf A}( \mathbf{G}_2 )= \left[ \begin{array} {ccccc} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right]$

Ponadto

$\sum_{i=1}^{4}{{\sf A}( \mathbf{G}_2 )^i}=\left[ \begin{array} {ccccc} 1 & 3 & 0 & 2 & 3 \\ 2 & 3 & 0 & 3 & 5 \\ 4 & 5 & 0 & 4 & 7 \\ 3 & 5 & 0 & 3 & 6 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right].$

W macierzy $\langle a'_{ij} \rangle =\sum_{i=1}^{4}{{\sf A}( \mathbf{G}_2 )^i}$ wartość $a'_{ij}$ mówi o liczbie różnych skierowanych marszrut z wierzchołka $v_i$ do $v_j$ o długości co najwyżej $4$. Dla przykładu $a_{34}=4$ i rzeczywiście $u_3\to u_4$, $u_3\to u_4\to u_2\to u_4$, $u_3\to u_1\to u_2\to u_4$, i $u_3\to u_4\to u_1\to u_2\to u_4$ są wszystkimi skierowanymi marszrutami jakie można znaleźć w grafie $\mathbf{G}_2$ prowadzące z wierzchołka $v_3$ do $v_4$ o długości co najwyżej $4$. Z kolei macierz sąsiedztwa dla przechodniego domknięcia grafu $\mathbf{G}_2$ to

${\sf A}( {\sf TC}( \mathbf{G}_2 ) )=\left[ \begin{array} {ccccc} 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right ].$

Warto zaobserwować oczywisty fakt, że macierz ${\sf A}( {\sf TC}( \mathbf{G}_2 ) )$ można równie dobrze uzyskać z macierzy $\sum_{i=1}^{4}{{\sf A}( \mathbf{G}_2 )^i}$ przez zamianę każdej niezerowej wartości na $1$ oraz wyzerowanie przekątnej.

Wniosek 15.2

Dla grafu $\mathbf{G}$ o wierzchołkach $v_1,\ldots,v_n$ i macierzy $\langle a_{ij} \rangle ={\sf A}( \mathbf{G} )^1+{\sf A}( \mathbf{G} )^2+\ldots+{\sf A}( \mathbf{G} )^{( n-1 )}$, jeśli tylko $i\neq j$, to

$a_{ij}>0\quad \textrm{wtedy i tylko wtedy, gdy}\quad ( v_i,v_j )\in{\sf E}\!({\sf TC}( \mathbf{G} )).$

Macierz incydencji ${\sf B}( \mathbf{G} )$ grafu $\mathbf{G}=( \lbrace v_1,\ldots,v_n \rbrace,\lbrace e_1,\ldots,e_m \rbrace )$ to zero-jedynkowa macierz $\langle b_{ij} \rangle$ rozmiaru $n\times m$, gdzie

$b_{ij}=\left \{ \begin{array} {l} 1, & \textrm{jeśli wierzchołek}\ v_i\ \textrm{jest incydentny z krawędzią}\ e_j, \\ 0, & \textrm{w przeciwnym wypadku.} \end{array} \right.$

Zorientowana macierz incydencji ${\sf C}( \mathbf{G} )$ grafu prostego to macierz $\langle c_{ij} \rangle$, rozmiaru $n\times m$, otrzymana z macierzy incydencji ${\sf B}( \mathbf{G} )$ poprzez zastąpienie w każdej kolumnie jednej z dwu jedynek przez $-1$(minus jeden).

Przykład

Dla grafu $\mathbf{G}_4=( \lbrace v_1,\ldots,v_5 \rbrace,\lbrace e_1,\ldots,e_7 \rbrace )$ przedstawionego na rysunku Graf prosty G4 macierz incydencji oraz zorientowana macierz incydencji, to odpowiednio:

${\sf B}( \mathbf{G}_4 )=\left[ \begin{array} {ccccccc} 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 \end{array} \right],\quad$
${\sf C}( \mathbf{G}_4 )=\left[ \begin{array} {ccccccc} -1 & 0 & 1 & -1 & 0 & 0 & 0 \\ 1 & -1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & -1 & 0 & 0 & 0 & -1 \\ 0 & 0 & 0 & 1 & -1 & -1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 \end{array} \right].$

Obserwacja 15.3

• Dla macierzy incydencji $\langle b_{ij} \rangle$ oraz zorientowanej macierzy incydencji $\langle c_{ij} \rangle ={\sf C}( \mathbf{G} )$ zachodzi $b_{ij} = \vert c_{ij} \vert\quad\textrm{dla}\ i=1,\ldots,n\ \textrm{oraz}\ j=1,\ldots,m.$
• W zorientowanej macierzy incydencji $\langle c_{ij} \rangle$ mamy: $c_{1j}+\ldots+c_{nj}=0\quad\textrm{dla}\ j=1,\ldots,m.$

Macierz stopni ${\sf D}( \mathbf{G} )$ grafu prostego $\mathbf{G}=( \lbrace v_1,\ldots,v_n \rbrace,E )$ to diagonalna macierz $\langle d_{ij} \rangle$ rozmiaru $n\times n$, gdzie

$d_{ij}=\left \{ \begin{array} {l} {\sf deg}\ v_i, & \textrm{jeżeli}\ i=j, \\ 0, & \textrm{w przeciwnym wypadku.} \end{array} \right.$

Przykład

Dla grafu $\mathbf{G}_4$ przedstawionego na rysunku Graf prosty G4 odpowiednia macierz stopni to

${\sf D}( \mathbf{G}_4 )=\left[ \begin{array} {ccccc} 3 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 4 & 0 \\ 0 & 0 & 0 & 0 & 2 \end{array} \right ].$

Twierdzenie 15.4

Jeśli $\mathbf{G}=( V,E )$ jest grafem prostym, to

${\sf B}( \mathbf{G} )\cdot {\sf B}( \mathbf{G} )^T= {\sf D}( \mathbf{G} )+ {\sf A}( \mathbf{G} ),$

gdzie ${\sf B}( \mathbf{G} )^T$ jest macierzą transponowaną macierzy ${\sf B}( \mathbf{G} )$.

Przykład

Policzmy macierze opisane w Twierdzeniu 15.4 dla grafu $\mathbf{G}_4$ z rysunku Graf prosty G4. Tak więc

$\begin{align*} {\sf B}( \mathbf{G}_4 )\cdot{\sf B}( \mathbf{G}_4 )^T & = & \left[ \begin{array} {ccccccc} 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 \end{array} \right ]\cdot \left[ \begin{array} {ccccccc} 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 \end{array} \right ] \\ & = & \left[ \begin{array} {ccccc} 3 & 1 & 1 & 1 & 0 \\ 1 & 3 & 0 & 1 & 1 \\ 1 & 0 & 2 & 1 & 0 \\ 1 & 1 & 1 & 4 & 1 \\ 0 & 1 & 0 & 1 & 2 \end{array} \right]\ =\ {\sf D}( \mathbf{G}_4 )+ {\sf A}( \mathbf{G}_4 ). \end{align*}$

Dowód [Twierdzenia 15.4]

Niech $m_{ij}$ będzie elementem w $i$-tym wierszu oraz w $j$-tej kolumnie macierzy $M={\sf B}( \mathbf{G} )\cdot {\sf B}( \mathbf{G} )^T$. Z definicji $M$ wynika, że

$m_{ij}=b_{i1}\cdot b_{j1}+\ldots+b_{i\vert E \vert}\cdot b_{j\vert E \vert}.$

Rozważmy dwa przypadki:

• $i\neq j$. Wtedy $b_{ik}\cdot b_{jk}=1$ jest równoważne temu, że krawędź $e_k$ łączy wierzchołek $v_i$ z $v_j$. Tak więc $m_{ij}=1$ wtedy i tylko wtedy, gdy $v_i$ sąsiaduje z $v_j$.
• $i=j$. Wtedy $b_{ik}\cdot b_{jk}=1$ jest równoważne temu, że krawędź $e_k$ jest incydentna z $v_i$. Sumując wartości $b_{ik}\cdot b_{ik}$ dla $k=1,\ldots,\vert E \vert$ uzyskujemy liczbę krawędzi incydentnych do $v_i$, czyli stopień ${\sf deg}\ v_i$.

Twierdzenie 15.5

Niech $\mathbf{G}$ będzie grafem skierowanym o $n$ wierzchołkach, a macierz $M$ o rozmiarach $( n-1 )\times( n-1 )$, będzie minorem (podmacierzą) zorientowanej macierzy incydencji ${\sf C}( \mathbf{G} )$, w którym kolumny odpowiadają krawędziom z pewnego podzbioru ${\sf E}\!(M)$ zbioru ${\sf E}\!(\mathbf{G})$. Wtedy

$\mathbf{H}=( {\sf V}\!(\mathbf{G}),{\sf E}\!(M) )\ $jest drzewem wtedy i tylko wtedy, gdy $M$ jest nieosobliwa.

Dowód

Niech $w$ będzie wierzchołkiem odpowiadającym jedynemu wierszowi pominiętemu w minorze $M$.

Niech $\mathbf{H}=( {\sf V}\!(\mathbf{G}),{\sf E}\!(M) )$ będzie drzewem. Dla pokazania, że wtedy macierz $M$ jest nieosobliwa, dokonamy takiej permutacji wierszy i kolumn macierzy $M$, by uzyskana w ten sposób macierz $M'=\langle m'_{ij} \rangle$ była trójkątna i miała wyłącznie niezerowe elementy na przekątnej. Zostanie to uzyskane przez takie ponumerowanie wierzchołków i krawędzi grafu $\mathbf{H}$, by w nowej macierzy

$m'_{ij}\neq0$ wtedy i tylko wtedy, gdy wierzchołek $v_i$ jest incydentny z $e_j$.

Przypomnijmy, że odległość pomiędzy dwoma wierzchołkami $x$ i $y$ w grafie to liczność najkrótszej ścieżki od $x$ do $y$. Ponumerujmy wierzchołki z ${\sf V}\!(\mathbf{G})$ w taki sposób, że jeśli $v_i$ jest bliżej wierzchołka $w$, niż $v_j$ to $i\leq j$. Numeracji takich może być wiele, ale dla nas nie ma znaczenia, którą z nich wybierzemy i ustalimy dla dalszej części dowodu. Zauważmy jedynie, że w każdej takiej numeracji wierzchołek $w$ znajduje się na początku. Ponieważ graf $\mathbf{H}$ jest drzewem, to między wierzchołkiem $w$ i dowolnym $v_i$ istnieje dokładnie jedna ścieżka. Oznaczmy ją przez $P_i=w\to v_{k_1}\to\ldots\to v_{k_s}\to v_i$. Oczywiście, dla $i\neq j$ ostanie krawędzie w ścieżkach $P_i$ i $P_j$ są różne. Tę ostatnią krawędź ścieżki $P_i$ oznaczmy, tak jak na rysunku, indeksem $i$, czyli $e_i=v_{k_s}v_i$.

Ponieważ w drzewie $\mathbf{H}$ jest dokładnie $n-1$ krawędzi, przypisanie wierzchołkowi $v_i$ krawędzi $e_i$ jest bijekcją między ${\sf V}\!(\mathbf{G})-\lbrace w \rbrace$ a ${\sf E}\!(\mathbf{H})$. W kolumnie $j_0$ macierzy $M$, odpowiadającej krawędzi $e_{j_0}=v_{j_1}v_{j_0}$, są jedynie dwa niezerowe elementy - jeden leży w wierszu $j_0$, odpowiadającemu wierzchołkowi $v_{j_0}$, a drugi w wierszu $j_1$. Skoro krawędź $e_{j_0}$ ma ten sam numer co wierzchołek $v_{j_0}$, wierzchołek $v_{j_1}$ musi leżeć na ścieżce z $w$ do $v_{j_0}$. Tym samym $v_{j_1}$ jest bliżej $w$ niż $v_{j_0}$, a zatem $j_1 < j_0$. Macierz $M'$ jest więc macierzą trójkątną górną z niezerową przekątną, co kończy dowód.

Załóżmy teraz, że $\mathbf{H}$ nie jest drzewem. Ponieważ $\mathbf{H}$ ma jedynie $n-1$ krawędzi, to zależność miedzy liczbą wierzchołków, krawędzi i składowych spójnych daje, że $\mathbf{H}$ ma co najmniej $2$ składowe. Niech wierzchołki $v_{i_1},\ldots,v_{i_l}$ tworzą składową, w której nie występuje $w$. Jeżeli, w $i_p$-tym wierszu i $r$-tej kolumnie macierzy $M$ jest niezerowy element $x=\pm1$, to wierzchołek $v_{i_p}$ jest incydentny z krawędzią $e_r =v_{i_p}v_{i_s}$. Wierzchołek $v_{i_s}$ będący drugim końcem krawędzi $e_r$ leży oczywiście w tej samej składowej co $v_{i_p}$, a zatem macierz $M$ ma liczbę $-x$ w $r$-tej kolumnie i w $i_s$-tym wierszu. Sumując teraz wiersze macierzy $M$ o indeksach $i_1,\ldots,i_l$ otrzymujemy wektor zerowy. To oczywiście oznacza, że macierz $M$ jest osobliwa.

Wniosek 15.6

W spójnym grafie prostym $\mathbf{G}$ o $n$ wierzchołkach rząd macierzy ${\sf C}( \mathbf{G} )$ wynosi $n-1$.

Wielomian charakterystyczny grafu $\mathbf{G}$ to wielomian charakterystyczny macierzy sąsiedztwa ${\sf A}( \mathbf{G} )$.

Permanent grafu $\mathbf{G}$ to permanent macierzy ${\sf A}( \mathbf{G} )$, czyli

${\sf per}\ {\sf A}( \mathbf{G} ) = \sum_{\sigma}{a_{1,\sigma(1)}\cdot a_{2,\sigma(2)}\cdot\ldots\cdot a_{n,\sigma(n)}},$

gdzie suma $\sum_{\sigma}$ rozciąga się po wszystkich permutacjach $\sigma$, zaś $a_{ij}$ oznacza element macierzy ${\sf A}( \mathbf{G} )$.

Wyznacznik grafu $\mathbf{G}$ to wyznacznik macierzy ${\sf A}( \mathbf{G} )$, czyli

${\sf det}\ {\sf A}( \mathbf{G} ) = \sum_{\sigma}(-1)^{\mbox{\sf sgn}(\sigma)}{a_{1,\sigma(1)}\cdot a_{2,\sigma(2)}\cdot\ldots\cdot a_{n,\sigma(n)}}.$

Skojarzenie niedoskonałe (a) i doskonałe (b)

Algebraiczne pojęcie permanentu macierzy okazuje się użytecznym przy badaniu skojarzeń w grafie. Rozważaliśmy już skojarzenia w grafach dwudzielnych.

Skojarzenie w grafie $\mathbf{G}=( V,E )$ to taki podzbiór $M\subseteq E$, że żadne jego dwie krawędzie nie są incydentne z tym samym wierzchołkiem.

Skojarzenie doskonałe to skojarzenie wykorzystujące wszystkie wierzchołki grafu.

Twierdzenie 15.7

Prosty graf dwudzielny $\mathbf{G}=( V_1\cup V_2,E )$ ma skojarzenie doskonałe wtedy i tylko wtedy, gdy $\mathbf{G}$ ma niezerowy permanent.

Dowód

Niech $\langle a_{ij} \rangle ={\sf A}( \mathbf{G} )$. Dowód ma dwa etapy. Najpierw pokażemy, że:

1. Permanent grafu $\mathbf{G}$ jest niezerowy wtedy i tylko wtedy, gdy istnieje permutacja $\rho_{0}$ liczb $1,\ldots,n$ taka, że $a_{i\rho_{0}( i )}=1$ dla $i=1,\ldots,n$.

Istotnie, każdy składnik sumy dającej permanent grafu $\mathbf{G}$

${\sf per}\ {\sf A}( \mathbf{G} ) = \sum_{\sigma}{a_{1,\sigma(1)}\cdot a_{2,\sigma(2)}\cdot\ldots\cdot a_{n,\sigma(n)}}.$

jest zawsze nieujemny. A zatem cała suma będzie dodatnia wtedy i tylko wtedy, gdy choć jeden jej składnik będzie niezerowy. To z kolei jest równoważne temu, że dla choć jednej permutacji $\rho_{0}$ zachodzi

$a_{i\rho_{0}( i )}=1$

dla wszystkich $i=1,\ldots,n$.

2. Graf $\mathbf{G}$ ma doskonałe skojarzenie $M\subseteq E$ wtedy i tylko wtedy, gdy istnieje permutacja $\rho_{0}$ liczb $1,\ldots,n$ taka, że $a_{i\rho_{0}( i )}=1$ dla $i=1,\ldots,n$.

Istotnie, w skojarzeniu doskonałym każdy wierzchołek jest incydentny z dokładnie jedną krawędzią. A zatem skojarzenie $M$ wyznacza permutację $\rho_{0}$ poprzez

$\rho_{0}( i )=j\quad\textrm{wtedy i tylko wtedy, gdy }\quad v_i v_j\in M.$

Nadto $a_{i\rho_{0}( i )}=1$ dla wszystkich $i=1,\ldots,n$.

Z drugiej strony, jeśli $( i_1,\ldots,i_k )$ jest cyklem permutacji $\rho_{0}$, tzn.

$\rho_{0}( i_1 )=i_2,\quad \rho_{0}( i_2 )=i_3,\quad \ldots,\quad \rho_{0}( i_{k-1} )=i_k,\quad \rho_{0}( i_k )=i_1,$

to założona równość $a_{i\rho_{0}( i )}=1$ mówi, że cyklowi temu odpowiada cykl $v_{i_1}\to v_{i_2}\to \ldots \to v_{i_k}\to v_{i_1}$ w grafie $\mathbf{G}$. Oczywiście w grafie dwudzielnym cykl taki musi mieć parzystą liczbę wierzchołków, tak więc zbiór krawędzi

$\lbrace v_{i_1}v_{i_2}, v_{i_3}v_{i_4},\ldots, v_{i_{k-1}}v_{i_k} \rbrace$

tworzy doskonałe skojarzenie zbioru wierzchołków $\lbrace v_{i_1}, v_{i_2}, v_{i_3},\ldots v_{i_{k-1}},v_{i_k} \rbrace$. Po zsumowaniu skojarzeń odpowidającym wszystkim cyklom permutacji $\rho_{0}$ otrzymamy skojarzenie doskonałe w grafie $\mathbf{G}$.

Skojarzenie doskonałe w grafie $\mathbf{G}_5$

{{przyklad||| Rozważmy graf $\mathbf{G}_5=( \lbrace v_1,v_2,v_3,v_4,v_5,v_6 \rbrace,E )$ przedstawiony na rysunku Graf G5.

Macierz sąsiedztwa ${\sf A}( \mathbf{G}_5 )$ to

${\sf A}( \mathbf{G}_5 )=\left[ \begin{array} {cccccc} 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \end{array} \right ].$

Permanent ${\sf per}\ \mathbf{G}_5 = 1$, tak więc istnieje skojarzenie doskonałe $M$. Jedno z takich skojarzeń, przedstawione na rysunku Skojarzenie doskonałe w grafie G5, odpowiada wyróżnionym elementom macierzy:

${\sf A}( \mathbf{G}_5 )=\left[ \begin{array} {cccccc} 0 & 0 & 0 & 1 & \mathbf{\underline{1}} & 0 \\ 0 & 0 & 0 & \mathbf{\underline{1}} & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & \mathbf{\underline{1}} \\ 1 & \mathbf{\underline{1}} & 1 & 0 & 0 & 0 \\ \mathbf{\underline{1}} & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & \mathbf{\underline{1}} & 0 & 0 & 0 \end{array} \right ].$

Przy badaniu kolorowań grafów przydatne okazuje się inne pojęcie algebraiczne.

Wartość własna grafu $\mathbf{G}$ to wartość własna macierzy sąsiedztwa ${\sf A}( \mathbf{G} )$.

Obserwacja 15.8

Macierz sąsiedztwa ${\sf A}( \mathbf{G} )$ jest rzeczywista i symetryczna, zatem wszystkie jej wartości własne są rzeczywiste i istnieje baza ortogonalna złożona z jej wektorów własnych.

Dla grafu prostego $\mathbf{G}$ przyjmujemy oznaczenia:

• $\lambda_{max}\!( \mathbf{G} )$ na maksymalną wartość własną macierzy ${\sf A}( \mathbf{G} )$,
• $\lambda_{min}\!( \mathbf{G} )$ na minimalną wartość własną macierzy ${\sf A}( \mathbf{G} )$.

Obserwacja 15.9

Wartości własne grafu $\mathbf{G}$ są, co do wartości bezwzględnej, nie większe niż maksymalny stopień wierzchołków grafu $\mathbf{G}$, tzn.

$\vert \lambda_{max}\!( \mathbf{G} ) \vert\leq\Delta( \mathbf{G} ).$

Dowód

Niech $\vert \mathbf{G} \vert=n$ oraz $x=\langle x_1,\ldots,x_n \rangle$ będzie niezerowym wektorem własnym macierzy ${\sf A}( \mathbf{G} )=\langle a_{ij} \rangle$ o wartości własnej $\lambda_{max}\!( \mathbf{G} )$. Bez straty ogólności można założyć, że $\vert x_k \vert=\max_{i=1,\ldots, n}{\vert x_i \vert}=1$. Oszacowanie modułu $k$-tej współrzędnej wektora ${\sf A}( \mathbf{G} )\cdot x=\lambda_{max}\!( \mathbf{G} )\cdot x$ daje nierówność:

$\begin{align*} \vert \lambda_{max}\!( \mathbf{G} ) \vert & =\vert \lambda_{max}\!( \mathbf{G} )x_k \vert \\ & =\vert a_{k1}x_1+\ldots+a_{kn}x_n \vert \\ & \leq & a_{k1}\vert x_1 \vert+\ldots+a_{kn}\vert x_n \vert \\ & \leq a_{k1}+\ldots+a_{kn} \\ & ={\sf deg}\ x_k\ \leq\ \Delta( \mathbf{G} ). \end{align*}$

Dowód następnych dwu obserwacji pozostawiamy jako ćwicznia 4 i 6.

Obserwacja 15.10

W grafie prostym $\mathbf{G}$ mamy $\lambda_{max}\!( \mathbf{G} )=\Delta( \mathbf{G} )$ wtedy i tylko wtedy, gdy któraś spójna składowa grafu $\mathbf{G}$ jest grafem regularnym stopnia $\Delta( \mathbf{G} )$.

Obserwacja 15.11

W spójnym grafie prostym $\mathbf{G}$ liczba $-\Delta( \mathbf{G} )$ jest wartością własną macierzy ${\sf A}( \mathbf{G} )$ wtedy i tylko wtedy, gdy $\mathbf{G}$ jest regularnym grafem dwudzielnym stopnia $\Delta( \mathbf{G} )$.

Twierdzenie 15.12 [wzór Hoffman'a]

W grafie regularnym $\mathbf{G}$ stopnia $r$ zachodzi

$\alpha( \mathbf{G} )\leq\frac{\vert {\sf V}\!(\mathbf{G}) \vert\cdot\lambda_{min}\!( \mathbf{G} )}{\lambda_{min}\!( \mathbf{G} )-r},$

gdzie $\alpha( \mathbf{G} )$ oznacza największy możliwy rozmiar indukowanej antykliki w grafie $\mathbf{G}$.

Dowód

Niech $n=\vert {\sf V}\!(\mathbf{G}) \vert$ oraz

$U:={\sf A}( \mathbf{G} )-\lambda_{min}\!( \mathbf{G} )\cdot I - ( r-\lambda_{min}\!( \mathbf{G} ) )\cdot n^{-1}\cdot J,$

gdzie $I$ jest macierzą diagonalną rozmiaru $n\times n$, która na przekątnej ma jedynki, a $J$ jest macierzą rozmiaru $n\times n$ w całości wypełnioną jedynkami. Ponadto niech wektor $x=\langle x_i \rangle$ będzie funkcją charakterystyczną najliczniejszego zbioru niezależnego $X\subseteq{\sf V}\!(\mathbf{G})$takiego, że $\mathbf{G}|_X$ jest antykliką. Oznacza to, że

$x_i=\left \{ \begin{array} {l} 1, & \textrm{jeśli}\ v_i\in X, \\ 0, & \textrm{w przeciwnym wypadku.} \end{array} \right.$

Wtedy $y={\sf A}( \mathbf{G} )\cdot x$ jest funkcją charakterystyczną zbioru sąsiadów wierzchołków w $X$, czyli

$y_i=\left \{ \begin{array} {l} 1, & \textrm{jeśli}\ v_i\notin X, \\ 0, & \textrm{w przeciwnym wypadku.} \end{array} \right.$

To z kolei daje, że

$x^T\cdot{\sf A}( \mathbf{G} )\cdot x=x^T\cdot y=0$

i w konsekwencji

$x^T\cdot U\cdot x=-\lambda_{min}\!( \mathbf{G} )\cdot\vert x \vert - ( r-\lambda_{min}\!( \mathbf{G} ) )\cdot n^{-1}\cdot\vert x \vert^2.$

Uzasadnimy teraz, że $x^T\cdot U\cdot x\geq0$. Dla $j=[1,1,\ldots,1]^T$ mamy:

$U\cdot j \ =\ r\cdot j-\lambda_{min}\!( \mathbf{G} )\cdot j - ( r-\lambda_{min}\!( \mathbf{G} ) )\cdot j\ =\ 0.$

Z kolej każdy inny wektor własny $z$ macierzy ${\sf A}( \mathbf{G} )$ o wartości własnej $\lambda$, który jest prostopadły do $j$ spełnia

$U\cdot z\ =\ ( \lambda-\lambda_{min}\!( \mathbf{G} ) )\cdot z,$

przy czym oczywiście $\lambda-\lambda_{min}\!( \mathbf{G} )\geq0$. Oznacza to, że wszystkie wartości własne macierzy $U$ są nieujemne. Niech więc $u_1,\ldots,u_n$ będzie ortogonalną bazą złożoną z wektorów własnych macierzy $U$, a $\lambda_1,\ldots,\lambda_n$ będą odpowiadającymi im wartościami własnymi. Niech ponadto $x=b_1\cdot u_1+\ldots+b_n\cdot u_n$ będzie rozkładem wektora $x$ w tej bazie. Wtedy:

$\begin{align*} x^T\cdot U\cdot x & = x^T\cdot( b_1\cdot\lambda_1\cdot u_1+\ldots+b_n\cdot\lambda_n\cdot u_n ) \\ & = b_1^2\cdot\lambda_1+\ldots+b_n^2\cdot\lambda_n\ \geq\ 0. \end{align*}$

W konsekwencji

$0\leq-\lambda_{min}\!( \mathbf{G} )\cdot\vert x \vert - ( r-\lambda_{min}\!( \mathbf{G} ) )\cdot n^{-1}\cdot\vert x \vert^2.$

Ponieważ $\vert x \vert=\alpha( \mathbf{G} )$ a $n=\vert {\sf V}\!(\mathbf{G}) \vert$, to ta ostatnia jest innym zapisem dowodzonej nierówności.

Wniosek 15.13

W regularnym grafie $\mathbf{G}$ zachodzi

$\chi\!( \mathbf{G} )\geq 1-\frac{\lambda_{max}\!( \mathbf{G} )}{\lambda_{min}\!( \mathbf{G} )}.$

Dowód

Ponieważ podział zbioru wierzchołków ${\sf V}\!(\mathbf{G})$ na rozłączne podzbiory $V_1,\ldots,V_k$ indukujące antykliki, jest równoważny z kolorowaniem grafu $\mathbf{G}$ przy użyciu $k$ kolorów, to

$\vert {\sf V}\!(\mathbf{G}) \vert \leq \chi\!( \mathbf{G} )\cdot \alpha( \mathbf{G} ).$

Jeśli teraz $r$ jest stopniem regularności grafu $\mathbf{G}$ to Twierdzenie 15.12 daje więc

$\chi\!( \mathbf{G} )\geq \frac{\lambda_{min}\!( \mathbf{G} )-r}{\lambda_{min}\!( \mathbf{G} )}.$

Ponieważ graf $\mathbf{G}$ jest $r$-regularny, to na mocy Obserwacji 15.10 mamy $r=\lambda_{max}\!( \mathbf{G} )$, co pozwala zakończyć dowód.