Matematyka dyskretna 1/Wykład 15: 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{𝐆}$

, oznaczany przez

$\mathrm{\Delta }\left(\mathbf{𝐆}\right)$

to

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \Delta\left( \mathbf{G} \right):=\max\left\lbrace {\sf deg}\ v:\ v\in{\sf V}\!\left(G\right) \right\rbrace.}

Macierz sąsiedztwa Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf A}\left( \mathbf{G} \right)} grafu prostego $\mathbf{𝐆}=(\{v_1,\dots ,v_n\},E)$ to zero-jedynkowa macierz $⟨a_{ij}⟩$ rozmiaru $n\times n$, gdzie

$a_{ij}=\{\begin{array}{ll}1,& \text{jeżeli}{v}_i{v}_j\in E,\\ 0,& \text{w przeciwnym wypadku.}\end{array}$

Uwaga

Macierz sąsiedztwa grafu nieskierowanego jest symetryczna.

<flash>file=metalg_graph.swf|width=250|height=150</flash>

<div.thumbcaption>Graf prosty ${\mathbf{𝐆}}_0$ i graf skierowany ${\mathbf{𝐆}}_1$

Przykład

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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{𝐆}$, to graf Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf TC}\left( \mathbf{G} \right)} taki, że:

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf V}\!\left({\sf TC}\left( \mathbf{G} \right)\right)={\sf V}\!\left(\mathbf{G}\right)} , oraz
• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left( v,w \right)\in{\sf E}\!\left({\sf TC}\left( \mathbf{G} \right)\right)}

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

Twierdzenie 15.1

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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

(*) Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\langle a'_{ij} \right\rangle ={\sf A}\left( \mathbf{G} \right)^k} jest macierzą, w której $a{\text{'}}_{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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf A}\left( \mathbf{G} \right)^1} jest macierzą sąsiedztwa, co natychmiast daje (*) dla $k=1$. Niech teraz $k>1$. Oczywiście

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\langle a_{ij} \right\rangle ={\sf A}\left( \mathbf{G} \right)} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\langle a'_{ij} \right\rangle ={\sf A}\left( \mathbf{G} \right)^k} , oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\langle a''_{ij} \right\rangle ={\sf A}\left( \mathbf{G} \right)^{k-1}} , to

$a{\text{'}}_{ij}=a^{\prime }{\text{'}}_{i1}{a}_{1j}+\dots +a^{\prime }{\text{'}}_{in}{a}_{nj}.$

Wartość $a^{\prime }{\text{'}}_{il}$ to liczba wszystkich skierowanych marszrut z $v_i$ do $v_l$ o długości $k-1$. Tak więc iloczyn $a^{\prime }{\text{'}}_{il}{a}_{lj}$ jest równy liczbie wszystkich skierowanych $k$-elementowych marszrut mających postać $v_i\to \dots \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.

<flashwrap>file=Metalg domk.swf|size=small</flashwrap>

<div.thumbcaption>Graf ${\mathbf{𝐆}}_2$ (a) oraz jego przechodnie domknięcie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathbf{G}_3={\sf TC}\left( \mathbf{G}_2 \right)} (b)

Przykład

Grafy ${\mathbf{𝐆}}_2=(\{u_1,\dots ,u_5\},E)$ i ${\mathbf{𝐆}}_3=(\{u_1,\dots ,u_5\},E^{\prime })$ zostały przedstawione na animacji.

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\langle a'_{ij} \right\rangle =\sum_{i=1}^{4}{{\sf A}\left( \mathbf{G}_2 \right)^i}} wartość $a{\text{'}}_{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{𝐆}}_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{𝐆}}_2$ to

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf A}\left( {\sf TC}\left( \mathbf{G}_2 \right) \right)} można równie dobrze uzyskać z macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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{𝐆}$ o wierzchołkach $v_1,\dots ,v_n$ i macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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\ne j$, to

Parser nie mógł rozpoznać (błąd składni): {\displaystyle a_{ij}>0\quad \text{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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf B}\left( \mathbf{G} \right)} grafu $\mathbf{𝐆}=(\{v_1,\dots ,v_n\},\{e_1,\dots ,e_m\})$ to zero-jedynkowa macierz $⟨b_{ij}⟩$ rozmiaru $n\times m$, gdzie

$b_{ij}=\{\begin{array}{ll}1,& \text{jeśli wierzchołek}{v}_i\text{jest incydentny z krawędzią}{e}_j,\\ 0,& \text{w przeciwnym wypadku.}\end{array}$

Zorientowana macierz incydencji Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf C}\left( \mathbf{G} \right)} grafu prostego to macierz $⟨c_{ij}⟩$, rozmiaru $n\times m$, otrzymana z macierzy incydencji Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf B}\left( \mathbf{G} \right)} poprzez zastąpienie w każdej kolumnie jednej z dwu jedynek przez $-1$(minus jeden).

<flash>file=metalg_graph_incyd.swf|width=250|height=200</flash>

<div.thumbcaption>Graf prosty ${\mathbf{𝐆}}_4$

Przykład

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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}

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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 $⟨b_{ij}⟩$ oraz zorientowanej macierzy incydencji Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\langle c_{ij} \right\rangle ={\sf C}\left( \mathbf{G} \right)} zachodzi $b_{ij}=\left|c_{ij}\right|\text{dla}i=1,\dots ,n\text{oraz}j=1,\dots ,m.$
• W zorientowanej macierzy incydencji $⟨c_{ij}⟩$ mamy: $c_{1j}+\dots +c_{nj}=0\text{dla}j=1,\dots ,m.$

Macierz stopni Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf D}\left( \mathbf{G} \right)} grafu prostego $\mathbf{𝐆}=(\{v_1,\dots ,v_n\},E)$ to diagonalna macierz $⟨d_{ij}⟩$ rozmiaru $n\times n$, gdzie

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle d_{ij}=\left\lbrace\begin{array} {ll} {\sf deg}\ v_i, & \text{jeżeli}\ i=j,\\ 0, & \text{w przeciwnym wypadku.} \end{array} \right. }

Przykład

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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{𝐆}=(V,E)$ jest grafem prostym, to

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf B}\left( \mathbf{G} \right)^T} jest macierzą transponowaną macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf B}\left( \mathbf{G} \right)} .

Przykład

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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). \end{align}}

Dowód [Twierdzenia 15.4]

Niech $m_{ij}$ będzie elementem w $i$-tym wierszu oraz w $j$-tej kolumnie macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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}+\dots +b_{i\left|E\right|}\cdot b_{j\left|E\right|}.$

Rozważmy dwa przypadki:

• $i\ne 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,\dots ,\left|E\right|$ uzyskujemy liczbę krawędzi incydentnych do $v_i$, czyli stopień Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf deg}\ v_i} .

Twierdzenie 15.5

Niech $\mathbf{𝐆}$ 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf C}\left( \mathbf{G} \right)} , w którym kolumny odpowiadają krawędziom z pewnego podzbioru Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf E}\!\left(M\right)} zbioru Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf E}\!\left(\mathbf{G}\right)} . Wtedy

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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.

<flash>file=metalg_tree_div.swf|width=300|height=200</flash>

<div.thumbcaption>Przykładowe drzewo $\mathbf{𝐇}$ 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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^{\prime }=⟨m{\text{'}}_{ij}⟩$ 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{𝐇}$, by w nowej macierzy

$m{\text{'}}_{ij}\ne 0$ 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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\le 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{𝐇}$ 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 \dots \to v_{k_s}\to v_i$. Oczywiście, dla $i\ne 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{𝐇}$ jest dokładnie $n-1$ krawędzi, przypisanie wierzchołkowi $v_i$ krawędzi $e_i$ jest bijekcją między Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf V}\!\left(\mathbf{G}\right)-\left\lbrace w \right\rbrace} a Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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^{\prime }$ jest więc macierzą trójkątną górną z niezerową przekątną, co kończy dowód.

Załóżmy teraz, że $\mathbf{𝐇}$ nie jest drzewem. Ponieważ $\mathbf{𝐇}$ ma jedynie $n-1$ krawędzi, to zależność miedzy liczbą wierzchołków, krawędzi i składowych spójnych daje, że $\mathbf{𝐇}$ ma co najmniej $2$ składowe. Niech wierzchołki $v_{i_1},\dots ,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=\pm 1$, 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,\dots ,i_l$ otrzymujemy wektor zerowy. To oczywiście oznacza, że macierz $M$ jest osobliwa.

Wniosek 15.6

W spójnym grafie prostym $\mathbf{𝐆}$ o $n$ wierzchołkach rząd macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf C}\left( \mathbf{G} \right)} wynosi $n-1$.

Wielomian charakterystyczny grafu $\mathbf{𝐆}$ to wielomian charakterystyczny macierzy sąsiedztwa Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf A}\left( \mathbf{G} \right)} .

Permanent grafu $\mathbf{𝐆}$ to permanent macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf A}\left( \mathbf{G} \right)} , czyli

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf A}\left( \mathbf{G} \right)} .

Wyznacznik grafu $\mathbf{𝐆}$ to wyznacznik macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf A}\left( \mathbf{G} \right)} , czyli

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf det}\ {\sf A}\left( \mathbf{G} \right) = \sum_{\sigma}(-1)^{\mathsf{ sgn}(\sigma)}{a_{1,\sigma(1)}\cdot a_{2,\sigma(2)}\cdot\ldots\cdot a_{n,\sigma(n)}}.}

<flash>file=metalg_matching.swf|width=250|height=150</flash>

<div.thumbcaption>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{𝐆}=(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{𝐆}=(V_1\cup V_2,E)$ ma skojarzenie doskonałe wtedy i tylko wtedy, gdy $\mathbf{𝐆}$ ma niezerowy permanent.

Dowód

Niech Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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{𝐆}$ jest niezerowy wtedy i tylko wtedy, gdy istnieje permutacja ${\rho }_0$ liczb $1,\dots ,n$ taka, że $a_{i{\rho }_0\left(i\right)}=1$ dla $i=1,\dots ,n$.

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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,\dots ,n$.

2. Graf $\mathbf{𝐆}$ ma doskonałe skojarzenie $M\subseteq E$ wtedy i tylko wtedy, gdy istnieje permutacja ${\rho }_0$ liczb $1,\dots ,n$ taka, że $a_{i{\rho }_0\left(i\right)}=1$ dla $i=1,\dots ,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\text{wtedy i tylko wtedy, gdy }{v}_i{v}_j\in M.$

Nadto $a_{i{\rho }_0\left(i\right)}=1$ dla wszystkich $i=1,\dots ,n$.

Z drugiej strony, jeśli $(i_1,\dots ,i_k)$ jest cyklem permutacji ${\rho }_0$, tzn.

${\rho }_0\left(i_1\right)=i_2,{\rho }_0\left(i_2\right)=i_3,\dots ,{\rho }_0\left(i_{k-1}\right)=i_k,{\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}\to v_{i_2}\to \dots \to v_{i_k}\to v_{i_1}$ w grafie $\mathbf{𝐆}$. Oczywiście w grafie dwudzielnym cykl taki musi mieć parzystą liczbę wierzchołków, tak więc zbiór krawędzi

$\{v_{i_1}{v}_{i_2},v_{i_3}{v}_{i_4},\dots ,v_{i_{k-1}}{v}_{i_k}\}$

tworzy doskonałe skojarzenie zbioru wierzchołków $\{v_{i_1},v_{i_2},v_{i_3},\dots v_{i_{k-1}},v_{i_k}\}$. Po zsumowaniu skojarzeń odpowidającym wszystkim cyklom permutacji ${\rho }_0$ otrzymamy skojarzenie doskonałe w grafie $\mathbf{𝐆}$.

<flash>file=Metalg graf g5.swf|width=250|height=250</flash>

<div.thumbcaption>Graf ${\mathbf{𝐆}}_5$

<flash>file=Metalg graf g52.swf|width=250|height=250</flash>

<div.thumbcaption>Skojarzenie doskonałe w grafie ${\mathbf{𝐆}}_5$

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

Macierz sąsiedztwa Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf A}\left( \mathbf{G}_5 \right)} to

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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{𝐆}$ to wartość własna macierzy sąsiedztwa Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf A}\left( \mathbf{G} \right)} .

Obserwacja 15.8

Macierz sąsiedztwa Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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{𝐆}$ przyjmujemy oznaczenia:

• ${\lambda }_{max}\left(\mathbf{𝐆}\right)$ na maksymalną wartość własną macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf A}\left( \mathbf{G} \right)} ,
• ${\lambda }_{min}\left(\mathbf{𝐆}\right)$ na minimalną wartość własną macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf A}\left( \mathbf{G} \right)} .

Obserwacja 15.9

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

$\left|{\lambda }_{max}\left(\mathbf{𝐆}\right)\right|\le \mathrm{\Delta }\left(\mathbf{𝐆}\right).$

Dowód

Niech $\left|\mathbf{𝐆}\right|=n$ oraz $x=⟨x_1,\dots ,x_n⟩$ będzie niezerowym wektorem własnym macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf A}\left( \mathbf{G} \right)=\left\langle a_{ij} \right\rangle } o wartości własnej ${\lambda }_{max}\left(\mathbf{𝐆}\right)$. Bez straty ogólności można założyć, że $\left|x_k\right|=\underset{i=1,\dots ,n}{\max }\left|x_i\right|=1$. Oszacowanie modułu $k$-tej współrzędnej wektora Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf A}\left( \mathbf{G} \right)\cdot x=\lambda_{max}\!\left( \mathbf{G} \right)\cdot x} daje nierówność:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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). \end{align}}

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

Obserwacja 15.10

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

Obserwacja 15.11

W spójnym grafie prostym $\mathbf{𝐆}$ liczba $-\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ jest wartością własną macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf A}\left( \mathbf{G} \right)} wtedy i tylko wtedy, gdy $\mathbf{𝐆}$ jest regularnym grafem dwudzielnym stopnia $\mathrm{\Delta }\left(\mathbf{𝐆}\right)$.

Twierdzenie 15.12 [wzór Hoffman'a]

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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{𝐆}\right)$ oznacza największy możliwy rozmiar indukowanej antykliki w grafie $\mathbf{𝐆}$.

Dowód

Niech Parser nie mógł rozpoznać (błąd składni): {\displaystyle n=\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert} oraz

Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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=⟨x_i⟩$ będzie funkcją charakterystyczną najliczniejszego zbioru niezależnego Parser nie mógł rozpoznać (błąd składni): {\displaystyle X\subseteq{\sf V}\!\left(\mathbf{G}\right)} takiego, że $\mathbf{𝐆}{|}_X$ jest antykliką. Oznacza to, że

$x_i=\{\begin{array}{ll}1,& \text{jeśli}{v}_i\in X,\\ 0,& \text{w przeciwnym wypadku.}\end{array}$

Wtedy Parser nie mógł rozpoznać (błąd składni): {\displaystyle y={\sf A}\left( \mathbf{G} \right)\cdot x} jest funkcją charakterystyczną zbioru sąsiadów wierzchołków w $X$, czyli

$y_i=\{\begin{array}{ll}1,& \text{jeśli}{v}_i\notin X,\\ 0,& \text{w przeciwnym wypadku.}\end{array}$

To z kolei daje, że

Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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{𝐆}\right)\cdot \left|x\right|-(r-{\lambda }_{min}\left(\mathbf{𝐆}\right))\cdot n^{-1}\cdot {\left|x\right|}^2.$

Uzasadnimy teraz, że $x^T\cdot U\cdot x\ge 0$. Dla $j={[1,1,\dots ,1]}^T$ mamy:

$U\cdot j=r\cdot j-{\lambda }_{min}\left(\mathbf{𝐆}\right)\cdot j-(r-{\lambda }_{min}\left(\mathbf{𝐆}\right))\cdot j=0.$

Z kolej każdy inny wektor własny $z$ macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf A}\left( \mathbf{G} \right)} o wartości własnej $\lambda$, który jest prostopadły do $j$ spełnia

$U\cdot z=(\lambda -{\lambda }_{min}\left(\mathbf{𝐆}\right))\cdot z,$

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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. \end{align}}

W konsekwencji

$0\le -{\lambda }_{min}\left(\mathbf{𝐆}\right)\cdot \left|x\right|-(r-{\lambda }_{min}\left(\mathbf{𝐆}\right))\cdot n^{-1}\cdot {\left|x\right|}^2.$

Ponieważ $\left|x\right|=\alpha \left(\mathbf{𝐆}\right)$ a Parser nie mógł rozpoznać (błąd składni): {\displaystyle n=\left\vert {\sf V}\!\left(\mathbf{G}\right) \right\vert} , to ta ostatnia jest innym zapisem dowodzonej nierówności.

Wniosek 15.13

W regularnym grafie $\mathbf{𝐆}$ zachodzi

$\chi \left(\mathbf{𝐆}\right)\ge 1-\frac{{\lambda }_{max}\left(\mathbf{𝐆}\right)}{{\lambda }_{min}\left(\mathbf{𝐆}\right)}.$

Dowód

Ponieważ podział zbioru wierzchołków Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf V}\!\left(\mathbf{G}\right)} na rozłączne podzbiory $V_1,\dots ,V_k$ indukujące antykliki, jest równoważny z kolorowaniem grafu $\mathbf{𝐆}$ przy użyciu $k$ kolorów, to

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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{𝐆}$ to Twierdzenie 15.12 daje więc

$\chi \left(\mathbf{𝐆}\right)\ge \frac{{\lambda }_{min}\left(\mathbf{𝐆}\right)-r}{{\lambda }_{min}\left(\mathbf{𝐆}\right)}.$

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