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

Metody algebraiczne w teorii grafów

Ćwiczenie 1

Ś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 $\{\mathsf{A}\left(\mathbf{𝐆}\right),\mathsf{A}{\left(\mathbf{𝐆}\right)}^2,\dots ,\mathsf{A}{\left(\mathbf{𝐆}\right)}^d\}$ jest liniowo niezależny.

Wskazówka

Graf $\mathbf{𝐆}$ ma średnicę $d$ , więc istnieją wierzchołki $v_k,v_l\in \mathsf{V}\left(\mathbf{𝐆}\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 $⟨a_{ij}^{\left(s\right)}⟩=\mathsf{A}{\left(\mathbf{𝐆}\right)}^s$ .

Rozwiązanie

Niech $⟨a_{ij}^{\left(s\right)}⟩=\mathsf{A}{\left(\mathbf{𝐆}\right)}^s$ , dla $s=1,2,\dots ,d$ . Z dowodu Twierdzenia 15.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 $v_k,v_l\in \mathsf{V}\left(\mathbf{𝐆}\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 $\{\mathsf{A}\left(\mathbf{𝐆}\right),\mathsf{A}{\left(\mathbf{𝐆}\right)}^2,\dots ,\mathsf{A}{\left(\mathbf{𝐆}\right)}^d\}$ .

Ćwiczenie 2

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 $\left|\mathsf{d}\mathsf{e}\mathsf{g}\mathsf{A}\left(\mathbf{𝐆}\right)\right|\le \mathsf{p}\mathsf{e}\mathsf{r}\mathsf{A}\left(\mathbf{𝐆}\right)$ , a następnie skorzystaj z twierdzenia 15.7.

Rozwiązanie

Elementy $a_{ij}$ macierzy $\mathsf{A}\left(\mathbf{𝐆}\right)$ są dodatnie, więc korzystając z definicji wyznacznika $\mathsf{d}\mathsf{e}\mathsf{t}\mathsf{A}\left(\mathbf{𝐆}\right)$ oraz permanentu $\mathsf{p}\mathsf{e}\mathsf{r}\mathsf{A}\left(\mathbf{𝐆}\right)$ otrzymujemy:

$\begin{array}{rl}\left|\mathsf{d}\mathsf{e}\mathsf{t}\mathsf{A}\left(\mathbf{𝐆}\right)\right|& =|\sum _{\sigma }(-1{)}^{\text{ sgn }(\sigma )}{a}_{1,\sigma (1)}\cdot a_{2,\sigma (2)}\cdot \dots \cdot a_{n,\sigma (n)}|\\ & \le \sum _{\sigma }|(-1{)}^{\text{ sgn }(\sigma )}{a}_{1,\sigma (1)}\cdot a_{2,\sigma (2)}\cdot \dots \cdot a_{n,\sigma (n)}|\\ & =\sum _{\sigma }{a}_{1,\sigma (1)}\cdot a_{2,\sigma (2)}\cdot \dots \cdot a_{n,\sigma (n)}\\ & =\mathsf{p}\mathsf{e}\mathsf{r}\mathsf{A}\left(\mathbf{𝐆}\right).\end{array}$

Jeżeli wyznacznik $\mathsf{d}\mathsf{e}\mathsf{t}\mathsf{A}\left(\mathbf{𝐆}\right)$ jest niezerowy, to permanent $\mathsf{p}\mathsf{e}\mathsf{r}\mathsf{A}\left(\mathbf{𝐆}\right)\ge \left|\mathsf{d}\mathsf{e}\mathsf{g}\mathsf{A}\left(\mathbf{𝐆}\right)\right|$ jest dodatni, więc na mocy Twierdzenia 15.7 graf $\mathbf{𝐆}$ ma skojarzenie doskonałe.

Ćwiczenie 3

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 $\mathsf{A}\left({{𝒦}}_n\right)$ to

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\lbrace \begin{array} {r c l l} w_1&=e_1+e_2+\ldots+e_n,\\ w_k&=e_1-e_k & \text{dla}\ k=2,3,\ldots,n. \end{array} \right}

Wektory własne macierzy $\mathsf{A}\left({{𝒦}}_{n,n}\right)$ to

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\lbrace \begin{array} {r c l l} u_1&=e_1+e_2+\ldots+e_{2n},\\ u_2&=e_1+\ldots+e_n-e_{n+1}-\ldots-e_{2n},\\ u_k&=e_1-e_{k-1} & \text{dla}\ k=3,4,\ldots,n+1,\\ u_k&=e_{n+1}-e_k & \text{dla}\ k=n+2,n+3,\ldots,2n. \end{array} \right}

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\lbrace \begin{array} {r c l l} w_1&=e_1+e_2+\ldots+e_n,\\ w_k&=e_1-e_k & \text{dla}\ k=2,3,\ldots,n. \end{array} \right}

są wektorami własnymi macierzy $\mathsf{A}\left({{𝒦}}_n\right)=J_n-I_n$ .

Dla $w_1$ mamy:

$\begin{array}{rl}\mathsf{A}\left({{𝒦}}_n\right)\cdot w_1& =(J_n-I_n)(e_1+e_2+\dots +e_n)\\ & =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+\dots +\sum _{l=1}^n{e}_l-e_1-e_2-\dots -e_n\\ & =(n-1)\cdot e_1+(n-1)\cdot e_2+\dots +(n-1)\cdot e_n\\ & =(n-1)\cdot w_1,\end{array}$

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

$\begin{array}{rl}\mathsf{A}\left({{𝒦}}_n\right)\cdot w_k& =(J_n-I_n)(e_1-e_k)\\ & =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,\end{array}$

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\lbrace \begin{array} {r c l l} u_1&=e_1+e_2+\ldots+e_{2n},\\ u_2&=e_1+\ldots+e_n-e_{n+1}-\ldots-e_{2n},\\ u_k&=e_1-e_{k-1} & \text{dla}\ k=3,4,\ldots,n+1,\\ u_k&=e_{n+1}-e_k & \text{dla}\ k=n+2,n+3,\ldots,2n. \end{array} \right}

są wektorami własnymi macierzy

$\mathsf{A}\left({{𝒦}}_{n,n}\right)=\left[\begin{array}{cc}0& I_n\\ I_n& 0\end{array}\right]$

• • Dla wektora $u_1$ mamy:

$\mathsf{A}\left({{𝒦}}_n\right)\cdot u_1=\left[\begin{array}{cc}0& I_n\\ I_n& 0\end{array}\right]\cdot \left[\begin{array}{c}1\\ ⋮\\ 1\end{array}\right]=\left[\begin{array}{c}n\\ ⋮\\ 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:

$\mathsf{A}\left({{𝒦}}_n\right)\cdot u_2=\left[\begin{array}{cc}0& I_n\\ I_n& 0\end{array}\right]\cdot \left[\begin{array}{c}1\\ ⋮\\ 1\\ -1\\ ⋮\\ -1\end{array}\right]=\left[\begin{array}{c}-n\\ ⋮\\ -n\\ n\\ ⋮\\ 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:

$\begin{array}{rl}\mathsf{A}\left({{𝒦}}_n\right)\cdot u_k& =\left[\begin{array}{cc}0& I_n\\ I_n& 0\end{array}\right]\cdot (e_1-e_{k-1})\\ & =\left[\begin{array}{cc}0& I_n\\ I_n& 0\end{array}\right]\cdot e_1-\left[\begin{array}{cc}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,\end{array}$

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:

$\begin{array}{rl}\mathsf{A}\left({{𝒦}}_n\right)\cdot u_k& =\left[\begin{array}{cc}0& I_n\\ I_n& 0\end{array}\right]\cdot (e_{n+1}-e_k)\\ & =\left[\begin{array}{cc}0& I_n\\ I_n& 0\end{array}\right]\cdot e_{n+1}-\left[\begin{array}{cc}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,\end{array}$

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

Ćwiczenie 4

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 15.9. wystarczy pokazać, że $\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ jest wartością własną macierzy $\mathsf{A}\left(\mathbf{𝐆}\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

$w_i=\{\begin{array}{cl}1& \text{jeśli}{v}_i\in C,\\ 0& \text{w przeciwnym przypadku.}\end{array}$

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

Ćwiczenie 5

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:

$u_i=\{\begin{array}{ll}{w}_i,& \text{jeśli}{v}_i\in V_1,\\ -w_i,& \text{w przeciwnym przypadku.}\end{array}$

Ćwiczenie 6

Udowodnij, że w spójnym grafie prostym $\mathbf{𝐆}$ , liczba $-\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ jest wartością własną macierzy $\mathsf{A}\left(\mathbf{𝐆}\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 15.9 zamieniając $\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ na $-\mathrm{\Delta }\left(\mathbf{𝐆}\right)$ .