Metody algebraiczne w teorii grafów

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.