Matematyka dyskretna 1/Ćwiczenia 15: Metody algebraiczne w teorii grafów

Metody algebraiczne w teorii grafów

Ćwiczenie ex grfay met alg domk

Średnica spójnego grafu $\mathbf{𝐆}$ , to maksymalna odległość między parą wierzchołków zawartych w $\mathbf{𝐆}$ . Pokaż, że gdy $\mathbf{𝐆}$ jest grafem spójnym o średnicy $d$ , to zbiór macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left\lbrace {\sf A}\left( \mathbf{G} \right),{\sf A}\left( \mathbf{G} \right)^2,\ldots,{\sf A}\left( \mathbf{G} \right)^d \right\rbrace } jest liniowo niezależny.

Wskazówka

Graf $\mathbf{𝐆}$ ma średnicę $d$ , więc istnieją wierzchołki Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle v_k, v_l\in{\sf V}\!\left(\mathbf{G}\right) } takie, że najkrótsza marszruta łącząca $v_k$ z $v_l$ jest $d$ elementowa. Dla $s=1,2,\dots ,d$ rozważ element $a_{kl}^{\left(s\right)}$ macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left\langle a_{ij}^{\left( s \right)} \right\rangle ={\sf A}\left( \mathbf{G} \right)^s } .

Rozwiązanie

Niech Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left\langle a_{ij}^{\left( s \right)} \right\rangle ={\sf A}\left( \mathbf{G} \right)^s } , dla $s=1,2,\dots ,d$ . Z dowodu Twierdzenia [th][th Twierdzenie 1] wynika, że element $a_{ij}^{\left(s\right)}$ to liczba skierowanych marszrut z $v_i$ do $v_j$ nie dłuższych niż $s$ . Graf $\mathbf{𝐆}$ ma średnicę $d$ , więc istnieją wierzchołki Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle v_k, v_l\in{\sf V}\!\left(\mathbf{G}\right) } takie, że najkrótsza marszruta łącząca $v_k$ z $v_l$ jest $d$ elementowa. Otrzymujemy więc $a_{kl}^{\left(s\right)}=0$ dla $s<d$ oraz $a_{kl}^{\left(d\right)}>0$ . Żadna kombinacja liniowa zerowych elementów $a_{kl}^{\left(1\right)},a_{kl}^{\left(2\right)},\dots ,a_{kl}^{(d-1)}$ nie może dać niezerowej wartości $a_{kl}^{\left(d\right)}$ . A to implikuje niezależność zbioru Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left\lbrace {\sf A}\left( \mathbf{G} \right),{\sf A}\left( \mathbf{G} \right)^2,\ldots,{\sf A}\left( \mathbf{G} \right)^d \right\rbrace } .

Ćwiczenie ex grfay met alg per det

Pokaż, że prosty graf dwudzielny $\mathbf{𝐆}=(V_1\cup V_2,E)$ o niezerowym wyznaczniku i w którym $\left|V_1\right|=\left|V_2\right|$ ma skojarzenie doskonałe.

Wskazówka

Pokaż, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left\vert {\sf deg}\ {\sf A}\left( \mathbf{G} \right) \right\vert\leq{\sf per}\ {\sf A}\left( \mathbf{G} \right) } , a następnie skorzystaj z twierdzenia [th][th Twierzenie 7].

Rozwiązanie

Elementy $a_{ij}$ macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf A}\left( \mathbf{G} \right) } są dodatnie, więc korzystając z definicji wyznacznika Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf det}\ {\sf A}\left( \mathbf{G} \right) } oraz permanentu Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf per}\ {\sf A}\left( \mathbf{G} \right) } otrzymujemy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \left\vert {\sf det}\ {\sf A}\left( \mathbf{G} \right) \right\vert &=\left\vert \sum_{\sigma}(-1)^{ } sgn Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (\sigma)}{a_{1,\sigma(1)}\cdot a_{2,\sigma(2)}\cdot\ldots\cdot a_{n,\sigma(n)}} \right\vert\\ &\leq \sum_{\sigma}\left\vert (-1)^{ } sgn Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (\sigma)}{a_{1,\sigma(1)}\cdot a_{2,\sigma(2)}\cdot\ldots\cdot a_{n,\sigma(n)}} \right\vert\\ &=\sum_{\sigma}{a_{1,\sigma(1)}\cdot a_{2,\sigma(2)}\cdot\ldots\cdot a_{n,\sigma(n)}}\\ &={\sf per}\ {\sf A}\left( \mathbf{G} \right). \endaligned}

Jeżeli wyznacznik Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf det}\ {\sf A}\left( \mathbf{G} \right) } jest niezerowy, to permanent Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf per}\ {\sf A}\left( \mathbf{G} \right)\geq\left\vert {\sf deg}\ {\sf A}\left( \mathbf{G} \right) \right\vert } jest dodatni, więc na mocy Twierdzenia [th][th Twierzenie 7] graf $\mathbf{𝐆}$ ma skojarzenie doskonałe.

Ćwiczenie ex max(G)=deg(G)

Znajdź wszystkie wartości własne grafów ${{𝒦}}_n$ oraz ${{𝒦}}_{n,n}$ .

Wskazówka

Niech $e_i$ będzie wektorem złożonym z samych zer, poza pozycją $i$ , na której stoi jedynka. Wektory własne macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf A}\left( \mathcal{K}_{n} \right) } to

$\{\begin{array}{rc}{w}_1& =e_1+e_2+\dots +e_n,\\ w_k& =e_1-e_k& \text{<mrow data-mjx-texclass="ORD">dla</mrow>}k=2,3,\dots ,n.\end{array}$

Wektory własne macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf A}\left( \mathcal{K}_{n,n} \right) } to

$\{\begin{array}{rc}{u}_1& =e_1+e_2+\dots +e_{2n},\\ u_2& =e_1+\dots +e_n-e_{n+1}-\dots -e_{2n},\\ u_k& =e_1-e_{k-1}& \text{<mrow data-mjx-texclass="ORD">dla</mrow>}k=3,4,\dots ,n+1,\\ u_k& =e_{n+1}-e_k& \text{<mrow data-mjx-texclass="ORD">dla</mrow>}k=n+2,n+3,\dots ,2n.\end{array}$

Rozwiązanie

Niech $e_i$ będzie wektorem złożonym z samych zer, poza pozycją $i$ , na której stoi jedynka. Ponadto niech $J_n$ będzie macierzą rozmiaru $n\times n$ złożoną z samych jedynek, a $I_n$ macierzą diagonalną rozmiaru $n\times n$ posiadającą jedynki na przekątnej. Rozważmy kolejno grafy ${{𝒦}}_n$ oraz ${{𝒦}}_{n,n}$ :

• Graf pełny ${{𝒦}}_n$ .

Pokażmy, że wektory $w_i$ dane wzorami

$\{\begin{array}{rc}{w}_1& =e_1+e_2+\dots +e_n,\\ w_k& =e_1-e_k& \text{<mrow data-mjx-texclass="ORD">dla</mrow>}k=2,3,\dots ,n.\end{array}$

są wektorami własnymi macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf A}\left( \mathcal{K}_{n} \right)=J_n-I_n } . Dla $w_1$ mamy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned {\sf A}\left( \mathcal{K}_{n} \right)\cdot w_1&=\left( J_n-I_n \right)\left( e_1+e_2+\ldots+e_n \right)\\ &=J_n\cdot e_1+J_n\cdot e_2+\cdots+J_n\cdot e_n-I_n\cdot e_1-I_n\cdot e_2-\cdots-I_n\cdot e_n\\ &=\sum_{l= 1}^n e_l+\sum_{l= 1}^n e_l+\ldots+\sum_{l= 1}^n e_l-e_1-e_2-\ldots-e_n\\ &=\left( n-1 \right)\cdot e_1 +\left( n-1 \right)\cdot e_2 +\ldots+\left( n-1 \right)\cdot e_n\\ &=\left( n-1 \right)\cdot w_1, \endaligned}

czyli $w_1$ jest wektorem własnym o wartości własnej $n-1$ . Z kolei dla wektora $w_k$ przy $k=2,3,\dots ,n$ mamy

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned {\sf A}\left( \mathcal{K}_{n} \right)\cdot w_k&=\left( J_n-I_n \right)\left( e_1-e_k \right)\\ &=J_n\cdot e_1-J_n\cdot e_k-I_n\cdot e_1+I_n\cdot e_k\\ &=\sum_{l= 1}^n e_l-\sum_{l= 1}^n e_l-e_1+e_k\\ &=-w_k, \endaligned}

czyli $w_k$ jest wektorem własnym o wartości własnej $-1$ .

• Pełny graf dwudzielny ${{𝒦}}_{n,n}$ .

Pokażemy, że wektory $u_i$ dane przez

$\{\begin{array}{rc}{u}_1& =e_1+e_2+\dots +e_{2n},\\ u_2& =e_1+\dots +e_n-e_{n+1}-\dots -e_{2n},\\ u_k& =e_1-e_{k-1}& \text{<mrow data-mjx-texclass="ORD">dla</mrow>}k=3,4,\dots ,n+1,\\ u_k& =e_{n+1}-e_k& \text{<mrow data-mjx-texclass="ORD">dla</mrow>}k=n+2,n+3,\dots ,2n.\end{array}$

są wektorami własnymi macierzy

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf A}\left( \mathcal{K}_{n,n} \right)= \left[\begin{array} {c c} 0 & I_n \\ I_n & 0 \end{array} \right]. }

• • Dla wektora $u_1$ mamy:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf A}\left( \mathcal{K}_{n} \right)\cdot u_1\ =\ \left[\begin{array} {c c} 0 & I_n \\ I_n & 0 \end{array} \right]\cdot \left[\begin{array} {c} 1 \\ \vdots \\ 1 \end{array} \right] \ =\ \left[\begin{array} {c} n \\ \vdots \\ n \end{array} \right] \ =\ n\cdot u_1, }

czyli $u_1$ jest wektorem własnym o wartości własnej $n$ .

• • Dla wektora $u_2$ mamy:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf A}\left( \mathcal{K}_{n} \right)\cdot u_2\ =\ \left[\begin{array} {c c} 0 & I_n \\ I_n & 0 \end{array} \right]\cdot \left[\begin{array} {c} 1 \\ \vdots \\ 1 \\ -1 \\ \vdots \\ -1 \end{array} \right] \ =\ \left[\begin{array} {c} -n \\ \vdots \\ -n \\ n \\ \vdots \\ n \end{array} \right] \ =\ -n\cdot u_1, }

czyli $u_2$ jest wektorem własnym o wartości własnej $-n$ .

• • Dla wektora $u_k$ , przy $k=3,4,\dots ,n+1$ , mamy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned {\sf A}\left( \mathcal{K}_{n} \right)\cdot u_k&= \left[\begin{array} {c c} 0 & I_n \\ I_n & 0 \end{array} \right] \cdot\left( e_1-e_{k-1} \right)\\ &= \left[\begin{array} {c c} 0 & I_n \\ I_n & 0 \end{array} \right] \cdot e_1- \left[\begin{array} {c c} 0 & I_n \\ I_n & 0 \end{array} \right] \cdot e_{k-1}\\ &=\sum_{l= 1+n}^{2n} e_l-\sum_{l= 1+n}^{2n} e_l\\ &=0, \endaligned}

czyli $u_k$ jest wektorem własnym o wartości własnej $0$ .

• • Dla wektora $u_k$ , przy $k=n+2,n+3,\dots ,2n$ , mamy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned {\sf A}\left( \mathcal{K}_{n} \right)\cdot u_k&= \left[\begin{array} {c c} 0 & I_n \\ I_n & 0 \end{array} \right] \cdot\left( e_{n+1}-e_k \right)\\ &= \left[\begin{array} {c c} 0 & I_n \\ I_n & 0 \end{array} \right] \cdot e_{n+1}- \left[\begin{array} {c c} 0 & I_n \\ I_n & 0 \end{array} \right] \cdot e_k\\ &=\sum_{l= 1}^n e_l-\sum_{l= 1}^n e_l\\ &=0, \endaligned}

czyli $u_k$ jest wektorem własnym o wartości własnej $0$ .

Ćwiczenie ex max(G)=deg(G)

Udowodnij, że 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)$ .

Wskazówka

Do dowodu implikacji w prawo na mocy Obserwacji [obs][Obserwacja 9] wystarczy pokazać, że $\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ jest wartością własną macierzy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle {\sf A}\left( \mathbf{G} \right) } . Dla spójnej składowej $C$ wyznaczającej graf regularny stopnia $\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ przeanalizuj wektor własny $w={[w_1,w_2,\dots ,w_n]}^T$ zdefiniowany w następujący sposób

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

Dla dowodu odwrotnej implikacji zastanów się, co zmieni się w ciągu nierówności z dowodu Obserwacji [obs][Obserwacja 9], i jakie można wyciągnąć z tego wnioski.

Ćwiczenie ex -lambda

Pokaż, że jeśli $\lambda$ jest wartością własną dwudzielnego grafu $\mathbf{𝐆}=(V_1\cup V_2,E)$ , to także $-\lambda$ jest wartością własną grafu $\mathbf{𝐆}$ .

Wskazówka

Niech $V_1\cup V_2=\{v_1,v_2,\dots ,v_n\}$ . Dla wektora własnego $w={[w_1,w_2,\dots ,w_n]}^T$ , odpowiadającego wartości własnej $\lambda$ , przeanalizuj wektor własny $u={[u_1,u_2,\dots ,u_n]}^T$ zdefiniowany jako:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \displaystyle u_i= \left\lbrace \begin{array} {ll} w_i, & \textrm{jeśli}\ v_i\in V_1,\\ -w_i, & \textrm{w przeciwnym przypadku.} \end{array} \right. }

Ćwiczenie ex -deg(G)

Udowodnij, że 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 \displaystyle {\sf A}\left( \mathbf{G} \right) } wtedy i tylko wtedy, gdy $\mathbf{𝐆}$ jest regularnym grafem dwudzielnym stopnia $\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ .

Wskazówka

Przeanalizuj ciąg nierówności w dowodzie Obserwacji [obs][Obserwacja 9] zamieniając $\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ na $-\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ .