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:
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
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:
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:
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.