Matematyka dyskretna 1/Wykład 15: Metody algebraiczne w teorii grafów

From Studia Informatyczne

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\left( \mathbf{G} \right) to
\Delta\left( \mathbf{G} \right):=\max\left\lbrace {\sf deg}\ v:\ v\in{\sf V}\!\left(G\right) \right\rbrace.

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


a_{ij}= \left\lbrace \begin{array} {ll} 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.



Graf prosty \mathbf{G}_0 i graf skierowany \mathbf{G}_1

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}\left( \mathbf{G}_0 \right)=\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}\left( \mathbf{G}_1 \right)=\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}\left( \mathbf{G} \right) taki, że:

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

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

Twierdzenie 15.1

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


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


Dowód

Wystarczy pokazać, że

(*) \left\langle a'_{ij} \right\rangle ={\sf A}\left( \mathbf{G} \right)^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}\left( \mathbf{G} \right)^1 jest macierzą sąsiedztwa, co natychmiast daje (*) dla k=1. Niech teraz k>1. Oczywiście


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


Jeśli więc \left\langle a_{ij} \right\rangle ={\sf A}\left( \mathbf{G} \right), \left\langle a'_{ij} \right\rangle ={\sf A}\left( \mathbf{G} \right)^k, oraz \left\langle a''_{ij} \right\rangle ={\sf A}\left( \mathbf{G} \right)^{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.

image:End_of_proof.gif



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

Przykład

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

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


{\sf A}\left( \mathbf{G}_2 \right)= \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}\left( \mathbf{G}_2 \right)^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 \left\langle a'_{ij} \right\rangle =\sum_{i=1}^{4}{{\sf A}\left( \mathbf{G}_2 \right)^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}\left( {\sf TC}\left( \mathbf{G}_2 \right) \right)=\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}\left( {\sf TC}\left( \mathbf{G}_2 \right) \right) można równie dobrze uzyskać z macierzy \sum_{i=1}^{4}{{\sf A}\left( \mathbf{G}_2 \right)^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 \left\langle a_{ij} \right\rangle ={\sf A}\left( \mathbf{G} \right)^1+{\sf A}\left( \mathbf{G} \right)^2+\ldots+{\sf A}\left( \mathbf{G} \right)^{\left( n-1 \right)}, jeśli tylko i\neq j, to


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


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


b_{ij}=\left\lbrace\begin{array} {ll} 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}\left( \mathbf{G} \right) grafu prostego to macierz \left\langle c_{ij} \right\rangle, rozmiaru n\times m, otrzymana z macierzy incydencji {\sf B}\left( \mathbf{G} \right) poprzez zastąpienie w każdej kolumnie jednej z dwu jedynek przez -1(minus jeden).



Graf prosty \mathbf{G}_4

Przykład

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


{\sf B}\left( \mathbf{G}_4 \right)=\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}\left( \mathbf{G}_4 \right)=\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 \left\langle b_{ij} \right\rangle oraz zorientowanej macierzy incydencji \left\langle c_{ij} \right\rangle ={\sf C}\left( \mathbf{G} \right) zachodzi
    b_{ij} = \left\vert c_{ij} \right\vert\quad\textrm{dla}\ i=1,\ldots,n\  \textrm{oraz}\ j=1,\ldots,m.
  • W zorientowanej macierzy incydencji \left\langle c_{ij} \right\rangle mamy:
    c_{1j}+\ldots+c_{nj}=0\quad\textrm{dla}\ j=1,\ldots,m.

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


d_{ij}=\left\lbrace\begin{array} {ll} {\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}\left( \mathbf{G}_4 \right)=\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}=\left( V,E \right) jest grafem prostym, to


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


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

Przykład

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


\aligned {\sf B}\left( \mathbf{G}_4 \right)\cdot{\sf B}\left( \mathbf{G}_4 \right)^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}\left( \mathbf{G}_4 \right)+ {\sf A}\left( \mathbf{G}_4 \right). \endaligned


Dowód [Twierdzenia 15.4]

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


m_{ij}=b_{i1}\cdot b_{j1}+\ldots+b_{i\left\vert E \right\vert}\cdot b_{j\left\vert E \right\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,\left\vert E \right\vert uzyskujemy liczbę krawędzi incydentnych do v_i, czyli stopień {\sf deg}\ v_i.
image:End_of_proof.gif

Twierdzenie 15.5

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


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




Przykładowe drzewo \mathbf{H} wraz z zaznaczoną ścieżką P_i

Dowód

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

Niech \mathbf{H}=\left( {\sf V}\!\left(\mathbf{G}\right),{\sf E}\!\left(M\right) \right) 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'=\left\langle m'_{ij} \right\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}\!\left(\mathbf{G}\right) 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}\!\left(\mathbf{G}\right)-\left\lbrace w \right\rbrace a {\sf E}\!\left(\mathbf{H}\right). 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.

image:End_of_proof.gif

Wniosek 15.6

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

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

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


{\sf per}\ {\sf A}\left( \mathbf{G} \right)  = \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}\left( \mathbf{G} \right).

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


{\sf det}\ {\sf A}\left( \mathbf{G} \right)  = \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}=\left( V,E \right) 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}=\left( V_1\cup V_2,E \right) ma skojarzenie doskonałe wtedy i tylko wtedy, gdy \mathbf{G} ma niezerowy permanent.

Dowód

Niech \left\langle a_{ij} \right\rangle ={\sf A}\left( \mathbf{G} \right). 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}\left( i \right)}=1 dla i=1,\ldots,n.

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


{\sf per}\ {\sf A}\left( \mathbf{G} \right)  = \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}\left( i \right)}=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}\left( i \right)}=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}\left( i \right)=j\quad\textrm{wtedy i tylko wtedy, gdy }\quad v_i v_j\in M.


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

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


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


to założona równość a_{i\rho_{0}\left( i \right)}=1 mówi, że cyklowi temu odpowiada cykl v_{i_1}\rightarrow v_{i_2}\rightarrow\ldots\rightarrow v_{i_k}\rightarrow 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


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


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

image:End_of_proof.gif



Graf \mathbf{G}_5



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

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

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


{\sf A}\left( \mathbf{G}_5 \right)=\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}\left( \mathbf{G}_5 \right)=\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}\left( \mathbf{G} \right).

Obserwacja 15.8

Macierz sąsiedztwa {\sf A}\left( \mathbf{G} \right) 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}\!\left( \mathbf{G} \right) na maksymalną wartość własną macierzy {\sf A}\left( \mathbf{G} \right),
  • \lambda_{min}\!\left( \mathbf{G} \right) na minimalną wartość własną macierzy {\sf A}\left( \mathbf{G} \right).

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.


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


Dowód

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


\aligned \left\vert \lambda_{max}\!\left( \mathbf{G} \right) \right\vert &=\left\vert \lambda_{max}\!\left( \mathbf{G} \right)x_k \right\vert\\ &=\left\vert a_{k1}x_1+\ldots+a_{kn}x_n \right\vert\\ &\leq&a_{k1}\left\vert x_1 \right\vert+\ldots+a_{kn}\left\vert x_n \right\vert\\ &\leq a_{k1}+\ldots+a_{kn}\\ &={\sf deg}\ x_k\ \leq\ \Delta\left( \mathbf{G} \right). \endaligned
image:End_of_proof.gif

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

Obserwacja 15.10

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

Obserwacja 15.11

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

Twierdzenie 15.12 [wzór Hoffman'a]

W grafie regularnym \mathbf{G} stopnia r zachodzi


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


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

Dowód

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


U:={\sf A}\left( \mathbf{G} \right)-\lambda_{min}\!\left( \mathbf{G} \right)\cdot I - \left( r-\lambda_{min}\!\left( \mathbf{G} \right) \right)\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=\left\langle x_i \right\rangle będzie funkcją charakterystyczną najliczniejszego zbioru niezależnego X\subseteq{\sf V}\!\left(\mathbf{G}\right)takiego, że \mathbf{G}|_X jest antykliką. Oznacza to, że


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


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


y_i=\left\lbrace \begin{array} {ll} 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}\left( \mathbf{G} \right)\cdot x=x^T\cdot y=0


i w konsekwencji


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


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


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


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


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


przy czym oczywiście \lambda-\lambda_{min}\!\left( \mathbf{G} \right)\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:


\aligned x^T\cdot U\cdot x &= x^T\cdot\left( b_1\cdot\lambda_1\cdot u_1+\ldots+b_n\cdot\lambda_n\cdot u_n \right)\\ &= b_1^2\cdot\lambda_1+\ldots+b_n^2\cdot\lambda_n\ \geq\ 0. \endaligned

W konsekwencji


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


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

image:End_of_proof.gif

Wniosek 15.13

W regularnym grafie \mathbf{G} zachodzi


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


Dowód

Ponieważ podział zbioru wierzchołków {\sf V}\!\left(\mathbf{G}\right) 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


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


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


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


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

image:End_of_proof.gif