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

{thm}{Twierdzenie} {obs}[thm]{Obserwacja} {con}[thm]{Wniosek}

{article} {../makraB}

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

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle 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 [Uzupelnij]

Macierz sąsiedztwa grafu nieskierowanego jest symetryczna.

Przykład [Uzupelnij]

[!h]

{metalg_graph} {Graf prosty ${\mathbf{𝐆}}_0$ i graf skierowany ${\mathbf{𝐆}}_1$. [Rysunek z pliku: metalggraph.eps]}

Na rysunku Uzupelnic pict metalg graph| 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 [Uzupelnij]

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 [Uzupelnij]

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.

Przykład [Uzupelnij]

Grafy ${\mathbf{𝐆}}_2=(\{u_1,\dots ,u_5\},E)$ i ${\mathbf{𝐆}}_3=(\{u_1,\dots ,u_5\},E^{\prime })$ zostały przedstawione na rysunku Uzupelnic pict metalg domk|.

[!h]

{metalg_domk} {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) [Rysunek z pliku: metalgdomk.eps]}

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 [Uzupelnij]

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 \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 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

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

Przykład [Uzupelnij]

[!h]

{metalg_graph_incyd} {Graf prosty ${\mathbf{𝐆}}_4$. [Rysunek z pliku: metalggraphincyd.eps]}

Dla grafu ${\mathbf{𝐆}}_4=(\{v_1,\dots ,v_5\},\{e_1,\dots ,e_7\})$ przedstawionego na rysunku Uzupelnic pict metalg graph incyd| 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 {\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 [Uzupelnij]

 

• 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{<mrow data-mjx-texclass="ORD">dla</mrow>}i=1,\dots ,n\text{<mrow data-mjx-texclass="ORD">oraz</mrow>}j=1,\dots ,m.$

• W zorientowanej macierzy incydencji $⟨c_{ij}⟩$ mamy:

$c_{1j}+\dots +c_{nj}=0\text{<mrow data-mjx-texclass="ORD">dla</mrow>}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, & \textrm{jeżeli}\ i=j,\\ 0, & \textrm{w przeciwnym wypadku.} \end{array} \right. }

Przykład [Uzupelnij]

Dla grafu ${\mathbf{𝐆}}_4$ przedstawionego na rysunku Uzupelnic pict metalg graph incyd| 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 [Uzupelnij]

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 [Uzupelnij]

Policzmy macierze opisane w Twierdzeniu [[##th B*Bt=D+A|Uzupelnic th B*Bt=D+A|]] dla grafu ${\mathbf{𝐆}}_4$ z rysunku Uzupelnic pict metalg graph incyd|. 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). \endaligned}

Dowód [Uzupelnij]

[Dowód Twierdzenia [[##th B*Bt=D+A|Uzupelnic th B*Bt=D+A|]].] 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 [Uzupelnij]

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)\ \textrm{jest drzewem wtedy i tylko wtedy, gdy } MParser nie mógł rozpoznać (błąd składni): {\displaystyle jest nieosobliwa.} }

Dowód [Uzupelnij]

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 Uzupelnic pict metalg tree div|, indeksem $i$, czyli $e_i=v_{k_s}{v}_i$.

[!h]

{metalg_tree_div} {Przykładowe drzewo $\mathbf{𝐇}$ wraz z zaznaczoną ścieżką $P_i$. [Rysunek z pliku: metalgtreediv.eps]}

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 [Uzupelnij]

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)^{\mbox{\sf sgn}(\sigma)}{a_{1,\sigma(1)}\cdot a_{2,\sigma(2)}\cdot\ldots\cdot a_{n,\sigma(n)}}. }

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.

[!h]

{metalg_matching} {Skojarzenie niedoskonałe (a) i doskonałe (b) [Rysunek z pliku: metalgmatching.eps]}

Twierdzenie [Uzupelnij]

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 [Uzupelnij]

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

1. 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{<mrow data-mjx-texclass="ORD">wtedyitylkowtedy<mo>,</mo>gdy</mrow>}{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{𝐆}$.

Przykład [Uzupelnij]

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

[!h]

{metalg_graf_g5} {Graf ${\mathbf{𝐆}}_5$. [Rysunek z pliku: metalggrafg5.eps]}

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 Uzupelnic metalg graf g52|, 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]. }

[!h]

{metalg_graf_g52} {Skojarzenie doskonałe w grafie ${\mathbf{𝐆}}_5$. [Rysunek z pliku: metalggrafg52.eps]}

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 [Uzupelnij]

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 [Uzupelnij]

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 [Uzupelnij]

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). \endaligned}

Dowód następnych dwu obserwacji pozostawiamy jako ćwiczenia [ex][ex max(G)=deg(G)] i [ex][ex -deg(G)].

Obserwacja [Uzupelnij]

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 [Uzupelnij]

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 [Uzupelnij]

[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 [Uzupelnij]

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

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle x_i=\left\lbrace \begin{array} {ll} 1, & \textrm{jeśli}\ v_i\in X,\\ 0, & \textrm{w przeciwnym wypadku.} \end{array} \right. }

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

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

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. \endaligned}

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 [Uzupelnij]

W regularnym grafie $\mathbf{𝐆}$ zachodzi

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

Dowód [Uzupelnij]

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 Uzupelnic th Hoffman| 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 [[##obs max(G)=deg(G)|Uzupelnic obs max(G)=deg(G)|]] mamy $r={\lambda }_{max}\left(\mathbf{𝐆}\right)$, co pozwala zakończyć dowód.