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

From Studia Informatyczne

Metody algebraiczne w teorii grafów

Ćwiczenie 1

Średnica spójnego grafu \displaystyle \mathbf{G} , to maksymalna odległość między parą wierzchołków zawartych w \displaystyle \mathbf{G} . Pokaż, że gdy \displaystyle \mathbf{G} jest grafem spójnym o średnicy \displaystyle d , to zbiór macierzy \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 \displaystyle \mathbf{G} ma średnicę \displaystyle d , więc istnieją wierzchołki \displaystyle v_k, v_l\in{\sf V}\!\left(\mathbf{G}\right) takie, że najkrótsza marszruta łącząca \displaystyle v_k z \displaystyle v_l jest \displaystyle d elementowa. Dla \displaystyle s=1,2,\ldots,d rozważ element \displaystyle a_{kl}^{\left( s \right)} macierzy \displaystyle \left\langle a_{ij}^{\left( s \right)} \right\rangle ={\sf A}\left( \mathbf{G} \right)^s .

Rozwiązanie

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

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

Wskazówka

Pokaż, że \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 15.7.

Rozwiązanie

Elementy \displaystyle a_{ij} macierzy \displaystyle {\sf A}\left( \mathbf{G} \right) są dodatnie, więc korzystając z definicji wyznacznika \displaystyle {\sf det}\ {\sf A}\left( \mathbf{G} \right) oraz permanentu \displaystyle {\sf per}\ {\sf A}\left( \mathbf{G} \right) otrzymujemy:


\displaystyle \aligned \left\vert {\sf det}\ {\sf A}\left( \mathbf{G} \right) \right\vert &=\left\vert \sum_{\sigma}(-1)^{ \textrm{ sgn } \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)^{ \textrm{ sgn } \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 \displaystyle {\sf det}\ {\sf A}\left( \mathbf{G} \right) jest niezerowy, to permanent \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 15.7 graf \displaystyle \mathbf{G} ma skojarzenie doskonałe.

Ćwiczenie 3

Znajdź wszystkie wartości własne grafów \displaystyle \mathcal{K}_{n} oraz \displaystyle \mathcal{K}_{n,n} .

Wskazówka

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


\displaystyle \left\lbrace \begin{array} {r c l l} w_1&=e_1+e_2+\ldots+e_n,\\ w_k&=e_1-e_k & \textrm{dla}\ k=2,3,\ldots,n. \end{array}  \right.


Wektory własne macierzy \displaystyle {\sf A}\left( \mathcal{K}_{n,n} \right) to


\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} & \textrm{dla}\ k=3,4,\ldots,n+1,\\ u_k&=e_{n+1}-e_k & \textrm{dla}\ k=n+2,n+3,\ldots,2n. \end{array}  \right.


Rozwiązanie

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

  • Graf pełny \displaystyle \mathcal{K}_{n} .

Pokażmy, że wektory \displaystyle w_i dane wzorami


\displaystyle \left\lbrace \begin{array} {r c l l} w_1&=e_1+e_2+\ldots+e_n,\\ w_k&=e_1-e_k & \textrm{dla}\ k=2,3,\ldots,n. \end{array}  \right.


są wektorami własnymi macierzy \displaystyle {\sf A}\left( \mathcal{K}_{n} \right)=J_n-I_n .

Dla \displaystyle w_1 mamy:

\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 \displaystyle w_1 jest wektorem własnym o wartości własnej \displaystyle n -1 . Z kolei dla wektora \displaystyle w_k przy \displaystyle k=2,3,\ldots,n mamy


\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 \displaystyle w_k jest wektorem własnym o wartości własnej \displaystyle -1 .

  • Pełny graf dwudzielny \displaystyle \mathcal{K}_{n,n} .

Pokażemy, że wektory \displaystyle u_i dane przez


\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} & \textrm{dla}\ k=3,4,\ldots,n+1,\\ u_k&=e_{n+1}-e_k & \textrm{dla}\ k=n+2,n+3,\ldots,2n. \end{array}  \right.


są wektorami własnymi macierzy


\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 \displaystyle u_1 mamy:
\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 \displaystyle u_1 jest wektorem własnym o wartości własnej \displaystyle n .

    • Dla wektora \displaystyle u_2 mamy:
\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 \displaystyle u_2 jest wektorem własnym o wartości własnej \displaystyle -n .

    • Dla wektora \displaystyle u_k , przy \displaystyle k=3,4,\ldots,n+1 , mamy:
\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 \displaystyle u_k jest wektorem własnym o wartości własnej \displaystyle 0 .

    • Dla wektora \displaystyle u_k , przy \displaystyle k=n+2,n+3,\ldots,2n , mamy:
\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 \displaystyle u_k jest wektorem własnym o wartości własnej \displaystyle 0 .

Ćwiczenie 4

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

Wskazówka

Do dowodu implikacji w prawo na mocy Obserwacji 15.9. wystarczy pokazać, że \displaystyle \Delta\left( \mathbf{G} \right) jest wartością własną macierzy \displaystyle {\sf A}\left( \mathbf{G} \right) . Dla spójnej składowej \displaystyle C wyznaczającej graf regularny stopnia \displaystyle \Delta\left( \mathbf{G} \right) przeanalizuj wektor własny \displaystyle w=\left[w_1,w_2,\ldots,w_n\right]^T zdefiniowany w następujący sposób


\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 15.9, i jakie można wyciągnąć z tego wnioski.

Ćwiczenie 5

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

Wskazówka

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


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

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

Wskazówka

Przeanalizuj ciąg nierówności w dowodzie Obserwacji 15.9 zamieniając \displaystyle \Delta\left( \mathbf{G} \right) na \displaystyle -\Delta\left( \mathbf{G} \right) .