Aktuální verze z 15. 1. 2012, 13:57

Zdrojový kód

%\wikiskriptum{01ZTGA}
 
\section{Vlastní čísla adjacenční matice grafu}
 
V této poslední části první kapitoly shrneme některé vlastnosti adjacenční
matice grafu. Budeme zde používat poznatků z předmětu Teorie matic
(TEMA), který je ve studijním plánu zařazen do zimního semestru třetího
ročníku a je povinný pro zaměření \emph{Matematické modelování} a
\emph{Softwarové inženýrství}. Tyto poznatky nebudeme dokazovat, uvedeme
je však ve formě poznámek a neočíslovaných definic. Rovněž pro úplnost
stručně zopakujeme definici \ref{def:adjacencni-matice} a větu \ref{thm:adjac-matice-pocet-sledu}.
 
\begin{defn*}
Buď $G=(V,E)$ graf, $n=\# V$. \textbf{Adjacenční maticí} grafu $G$
rozumíme matici $\vec{A}_{G}\in\{0,1\}^{n,n}$, pro jejíž prvky platí\[
\left(\vec{A}_{G}\right)_{ij}=\begin{cases}
1 & \textrm{pro }\{ v_{i},v_{j}\}\in E\\
0 & \textrm{jinak}\end{cases}\]
 
\end{defn*}
\begin{rem}
Adjacenční matice má následující vlastnosti:
\begin{itemize}
\item $\vec{A}$ je reálná, nezáporná, symetrická. Ze symetrie plyne, že
má reálné spektrum, a podle Schurovy věty pro normální matice (viz
\cite{PNLA}) je unitárně diagonalizovatelná, tj. existuje unitární
matice $\vec{P}$ ($\vec{P}\vec{P}^{\T}=\vec{I}$, neboli $\vec{P}^{\T}=\vec{P}^{-1}$)
tak, že\[
\vec{P}^{-1}\vec{A}_{G}\vec{P}=\vec{\Lambda}=\diag(\lambda_{1},...,\lambda_{n}).\]
Protože $\vec{A}_{G}$ je reálná, jsou matice $\vec{P},\vec{\Lambda}$
(konstruované v důkazu Schurovy věty) také reálné a tedy $\vec{P}$
je ortogonální. Její sloupce i řádky tvoří ortonormální (ON) bázi
prostoru $\R^{n}$. Z toho, že $\vec{\Lambda}$ je reálná, je vidět
i $\sigma(\vec{A})\subset\R$, i když reálnost vlastních čísel symetrické
matice je možné dokázat snadno i bez Schurovy věty.
\item Protože spektrum matice ani stopa se podobnostními transformacemi
nemění, platí $\Tr\vec{A}_{G}=\sum\lambda_{i}$ , kde $\lambda_{i}$
jsou všechna vlastní čísla matice $\vec{A}_{G}$. Protože ovšem $\left(\forall i\in\hat{n}\right)\left(\vec{A}_{ii}=0\right)$,
tak $0=\Tr\vec{A}_{G}=\sum\lambda_{i}$.
\item Nechť $k\in\hat{n}$. Potom prvek $\left(\vec{A}_{G}^{k}\right)_{ij}$
je roven počtu sledů délky $k$ z vrcholu $v_{i}$ do vrcholu $v_{j}$.
(věta \ref{thm:adjac-matice-pocet-sledu})
\item Uvědomíme-li si, jakým způsobem vzniká $(i,j)$-tý prvek matice $\vec{A}_{G}\vec{A}_{G}=\vec{A}_{G}^{2}$,
tak ze symetrie $\vec{A}_{G}$ plyne $\left(\vec{A}_{G}^{2}\right)_{ii}=d_{G}(v_{i})$.
Lze uvažovat i podle předchozího bodu, že totiž $\left(\vec{A}_{G}^{2}\right)_{ii}$
je počet sledů délky $2$ z $v_{i}$ do $v_{i}$, a to je zřejmě právě
$d_{G}(v_{i})$.
\item Protože\[
\Tr\left(\vec{A}_{G}^{2}\right)=\Tr\left(\vec{P}^{-1}\vec{A}_{G}^{2}\vec{P}\right)=\Tr\left(\underbrace{\vec{P}^{-1}\vec{A}_{G}\vec{P}}_{\vec{\Lambda}}\underbrace{\vec{P}^{-1}\vec{A}_{G}\vec{P}}_{\vec{\Lambda}}\right)=\Tr\vec{\Lambda}^{2}=\sum_{i=1}^{n}\lambda_{i}^{2},\]
tak z předchozího bodu máme\[
\sum_{i=1}^{n}\lambda_{i}^{2}=\Tr\left(\vec{A}_{G}^{2}\right)=\sum_{i=1}^{n}d_{G}(v_{i})=2\# E.\]
 
\end{itemize}
\end{rem}
\begin{notation*}
Vlastní čísla matice $\vec{A}_{G}$ označme tak, aby byla uspořádána
podle velikosti. Největší vlastní číslo označíme $\Lambda$:\[
\lambda_{1}\leq\lambda_{2}\leq...\leq\lambda_{n}=\Lambda.\]
Ze Schurovy věty plyne, že pořadí diagonálních prvků matice $\vec{\Lambda}=\vec{P}^{-1}\vec{A}_{G}\vec{P}$
je možné volit libovolně, proto BÚNO můžeme uvažovat \[
\vec{\Lambda}=\left(\begin{array}{cccc}
\lambda_{1}\\
 & \ddots\\
 &  & \lambda_{n-1}\\
 &  &  & \Lambda\end{array}\right).\]
 
\end{notation*}
\begin{rem*}
Spektrální normou matice $\vec{A}$ nazýváme číslo\[
\left\Vert \vec{A}\right\Vert =\max_{\left\Vert \vec{x}\right\Vert =1}\vec{x}^{\T}\vec{A}\vec{x}.\]
Její název pochází z platnosti vztahu\[
\left\Vert \vec{A}_{G}\right\Vert =\rho(\vec{A}),\]
kde $\rho(\vec{A)}$ je spektrální poloměr matice $\vec{A}$.
\end{rem*}
\begin{proof}
(pro symetrickou nezápornou matici $\vec{A}_{G}$). Platí
 
$\vec{x}^{\T}\vec{A}_{G}\vec{x}=\underbrace{\vec{x}^{\T}\vec{P}}_{\vec{y}^{\T}}\underbrace{\vec{P}^{\T}\vec{A}_{G}\vec{P}}_{\vec{\Lambda}}\underbrace{\vec{P}^{\T}\vec{x}}_{\vec{y}}$.
Protože $\vec{P}$ je ON, má $\vec{y}=\vec{P}^{\T}\vec{x}$ také normu
$1$. Proto\[
\max_{\left\Vert \vec{x}\right\Vert =1}\vec{x}^{\T}\vec{A}_{G}\vec{x}=\max_{\left\Vert \vec{y}\right\Vert =1}\vec{y}^{\T}\vec{\Lambda}\vec{y}=\max_{\left\Vert \vec{y}\right\Vert =1}\left(y_{1},...,y_{n}\right)\left(\begin{array}{ccc}
\lambda_{1}\\
 & \ddots\\
 &  & \lambda_{n}\end{array}\right)\left(\begin{array}{c}
y_{1}\\
\vdots\\
y_{n}\end{array}\right)=\]
\[
=\max_{\left\Vert \vec{y}\right\Vert =1}\sum_{i=1}^{n}\lambda_{i}y_{i}^{2}\leq\sum_{i=1}^{n}\Lambda y_{i}^{2}=\Lambda\sum_{i=1}^{n}y_{i}^{2}=\Lambda.\]
Ukázali jsme tedy\[
\max_{\left\Vert \vec{x}\right\Vert =1}\vec{x}^{\T}\vec{A}_{G}\vec{x}\leq\Lambda.\]
Pokud ovšem zvolíme\[
\vec{y}={\scriptstyle \left(\begin{array}{c}
0\\
0\\
\vdots\\
0\\
1\end{array}\right)},\]
tj. jednička bude na posledním řádku odpovídajícím pozici vlastního
čísla $\Lambda$, tak\[
\sum_{i=1}^{n}\lambda_{i}y_{i}^{2}=\Lambda,\]
a tedy platí\[
\left\Vert \vec{A}\right\Vert =\max_{\left\Vert \vec{x}\right\Vert =1}\vec{x}^{\T}\vec{A}_{G}\vec{x}=\Lambda=\rho(\vec{A}_{G}).\]
 
\end{proof}
\begin{thm}
\label{thm:bipart-adjac-sym}Je-li graf $G$ bipartitní, je spektrum
jeho adjacenční matice symetrické kolem počátku na reálné ose.
\end{thm}
\begin{proof}
Adjacenční matice bipartitního grafu má při vhodném uspořádání vrcholů
tvar\[
\vec{A}_{G}=\left(\begin{array}{cc}
\vec{0} & \vec{B}\\
\vec{B}^{\T} & \vec{0}\end{array}\right).\]
Nechť nyní $\lambda\in\sigma(\vec{A}_{G})$. Potom $\vec{A}_{G}\vec{x}=\lambda\vec{x}$
pro nějaké $\vec{x}\neq\vec{0}$. Blokově\[
\left(\begin{array}{cc}
\vec{0} & \vec{B}\\
\vec{B}^{\T} & \vec{0}\end{array}\right)\left(\begin{array}{c}
\vec{y}\\
\vec{z}\end{array}\right)=\lambda\left(\begin{array}{c}
\vec{y}\\
\vec{z}\end{array}\right),\]
kde\[
\vec{x}=\left(\begin{array}{c}
\vec{y}\\
\vec{z}\end{array}\right).\]
Porovnáme-li jednotlivé bloky, dostaneme rovnosti\begin{eqnarray*}
\vec{B}\vec{z} & = & \lambda\vec{y},\\
\vec{B}^{\T}\vec{y} & = & \lambda\vec{z}.\end{eqnarray*}
Nyní místo vektoru $\left(\begin{array}{c}
\vec{y}\\
\vec{z}\end{array}\right)$ vezmeme vektor $\left(\begin{array}{c}
\vec{y}\\
-\vec{z}\end{array}\right).$ Pro něj platí\[
\vec{A}_{G}\left(\begin{array}{c}
\vec{y}\\
-\vec{z}\end{array}\right)=\left(\begin{array}{c}
-\vec{B}\vec{z}\\
\vec{B}^{\T}\vec{y}\end{array}\right)=\left(\begin{array}{c}
-\lambda\vec{y}\\
\lambda\vec{z}\end{array}\right)=-\lambda\left(\begin{array}{c}
\vec{y}\\
-\vec{z}\end{array}\right).\]
To ale znamená, že $-\lambda\in\sigma(\vec{A}_{G})$ a k němu příslušný
vlastní vektor je $\left(\begin{array}{c}
\vec{y}\\
-\vec{z}\end{array}\right)\neq\vec{0}$.
\end{proof}
\begin{rem*}
Otázkou je, zda jsme mohli BÚNO předpokládat, že matice $\vec{A}_{G}$
má již vhodný blokový tvar, tj. zda při jiném uspořádání vrcholů se
nezmění spektrum adjacenční matice grafu. Abychom dokázali odpovědět,
nejdříve si uvědomme, že permutaci vrcholů grafu $G$ odpovídá současná
permutace řádků i sloupců jeho adjacenční matice. Tato dvojitá permutace
lze však vyjádřit součinem\[
\vec{A}'_{G}=\vec{P}^{\T}\vec{A}_{G}\vec{P},\]
kde $\vec{P}$ je tzv. permutační matice.
\end{rem*}
\begin{defn*}
\textbf{Permutační matice} je regulární matice $\vec{P}\in\{0,1\}^{n,n}$
taková, že obsahuje právě $n$ jedniček, tj. vznikne permutací řádků
nebo sloupců jednotkové matice.
\end{defn*}
\begin{rem*}
Je snadno vidět, že každý sloupec $\vec{P}$ má normu $1$ a každé
dva různé sloupce jsou navzájem kolmé. Proto platí\[
\vec{P}^{\T}\vec{P}=\vec{I},\]
neboli $\vec{P}^{\T}=\vec{P}^{-1}$, takže $\vec{P}$ je ortogonální.
Tím pádem ovšem $\vec{A}'_{G}=\vec{P}^{\T}\vec{A}_{G}\vec{P}=\vec{P}^{-1}\vec{A}_{G}\vec{P}$,
což znamená, že adjacenční matice $G$, kterou po zpermutování vrcholů
označujeme $\vec{A}'_{G}$, je podobná původní matici $\vec{A}_{G}$.
Proto má stejné spektrum.
\end{rem*}
\begin{defn*}
Řekneme, že matice $\vec{A}\in\C^{n,n}$ je \textbf{rozložitelná},
právě když existuje permutační matice $\vec{P}$ tak, že \[
\vec{P}^{\T}\vec{A}\vec{P}=\left(\begin{array}{cc}
\vec{B}_{11} & \vec{B}_{12}\\
\vec{0} & \vec{B}_{22}\end{array}\right),\]
kde $\vec{B}_{11},\vec{B}_{22}$ jsou čtvercové bloky řádu nejméně
$1$. V opačném případě se $\vec{A}$ nazývá \textbf{nerozložitelnou}
maticí.
\end{defn*}
\begin{thm*}
Adjacenční matice grafu $G$ je nerozložitelná právě tehdy, když $G$
je souvislý.
\end{thm*}
 
 
\begin{thm*}
Buď $\vec{A}$ nezáporná nerozložitelná matice řádu $n\geq2$. Potom
$\rho(\vec{A})\in\sigma(\vec{A})$ \emph{(to je (mimo jiné) obsahem
Perron-Frobeniovy věty)}. Jestliže navíc existuje $\alpha\in\C,\left|\alpha\right|=1,\alpha\neq1$
takové, že i $\alpha\rho(\vec{A)}\in\sigma(\vec{A})$, potom existuje
diagonální matice $\vec{D}=\diag(\delta_{1},...,\delta_{n})$, $\left|\delta_{i}\right|=1$
$\forall i\in\hat{n}$, taková, že\[
\vec{A}\vec{D}=\alpha\vec{D}\vec{A}.\]
 
\end{thm*}
\begin{thm}
Graf $G$ je bipartitní, právě když je spektrum jeho adjacenční matice
symetrické kolem počátku na reálné ose.
\end{thm}
\begin{proof}
Jeden směr ekvivalence již obsahuje věta \ref{thm:bipart-adjac-sym}.
Zbývá dokázat implikaci $\boxed{{\Leftarrow:}}$.
\begin{enumerate}
\item Nechť $G$ je souvislý, tj. $\vec{A}_{G}=\left(a_{ij}\right)$ je
nerozložitelná. Potom lze použít předchozí větu. Z předpokladu symetrie
$\sigma(\vec{A)}$ platí, že existuje matice $\vec{D}=\diag(\delta_{1},...,\delta_{n})$
taková, že\begin{equation}
\vec{A}\vec{D}=\vec{D}\vec{A}.\label{eq:ad-da}\end{equation}
Protože potom samozřejmě i $\vec{A}\gamma\vec{D}=\gamma\vec{D}\vec{A}$
pro každé $\gamma\neq0$, lze BÚNO předpokládat $\delta_{1}=1$. Pokud
nyní porovnáme prvky v (\ref{eq:ad-da}) na $(i,j)$-tém místě takovém,
že $\{ i,j\}\in E$, tj. $a_{ij}=1$, dostaneme\[
a_{ij}\delta_{j}=-\delta_{i}a_{ij},\]
takže $\delta_{j}=-\delta_{i}$. Protože $G$ je souvislý, lze se
z každého vrcholu dostat do každého, a tak postupnou aplikací právě
odvozeného pravidla (s uvážením $\delta_{1}=1$) dostaneme\[
\left(\forall i\in\hat{n}\right)\left(\delta_{i}=\pm1\right).\]
Nyní provedeme rozklad množiny vrcholů:\begin{eqnarray*}
V_{1} & = & \left\{ \left.i\right|\delta_{i}=+1\right\} ,\\
V_{2} & = & \left\{ \left.i\right|\delta_{i}=-1\right\} .\end{eqnarray*}
Je zřejmé, že $V_{1}$ ani $V_{2}$ nejsou prázdné a že uvnitř $V_{1}$ani
$V_{2}$ nevede hrana, protože\[
\left(\forall i,j\in\hat{n}\right)\left(\{ i,j\}\in E\Rightarrow\delta_{j}=-\delta_{i}\right).\]
 
\item Nechť $G$ není souvislý, tj. $G=G_{1}\cup...\cup G_{l}$, kde $G_{i}$
($i\in\hat{l}$) jsou jednotlivé komponenty grafu. Potom jeho vrcholy
očíslujeme tak, že vrcholy z jedné komponenty jsou bezprostředně za
sebou. $\vec{A}_{G}$ bude mít tvar\[
\vec{A}_{G}=\left(\begin{array}{cccc}
\vec{A}_{G_{1}} &  &  & \vec{0}\\
 & \vec{A}_{G_{2}}\\
 &  & \ddots\\
\vec{0} &  &  & \vec{A}_{G_{l}}\end{array}\right).\]
Nechť $-\Lambda\in\sigma\left(\vec{A}_{G_{i}}\right)$. Potom protože
$G_{i}$ je komponenta, tak $\vec{A}_{G_{i}}$ je nerozložitelná a
z Perron-Frobeniovy věty také $\Lambda\in\sigma\left(\vec{A}_{G_{i}}\right)$.
Podle prvního bodu je tedy $G_{i}$ bipartitní graf, a podle druhé
implikace věty je \emph{celé} spektrum $\vec{A}_{G_{i}}$ symetrické.
Komponentu $G_{i}$ můžeme tedy z $G$ odstranit a adjacenční matice
výsledného grafu bude mít stále symetrické spektrum. Tak postupně
dokážeme, že všechny komponenty jsou bipartitní grafy. Tím pádem je
i $G$ bipartitní, stačí totiž definovat\[
V_{1}=\bigcup_{i=1}^{l}V_{1}^{i}\;,\; V_{2}=\bigcup_{i=1}^{l}V_{2}^{i}.\]
 
\end{enumerate}
\end{proof}
\begin{thm*}
Nechť $\vec{A}\geq0$. Potom $\rho(\vec{A})$ je vlastní číslo $\vec{A}$
a vlastní vektor k němu lze volit nezáporný.
\end{thm*}
\begin{thm}
Nechť $G$ je graf, $\vec{A}_{G}$ jeho adjacenční matice, $\Lambda=\max\sigma(\vec{A}_{G})$.
Potom platí\[
\delta(G)\leq\Lambda\leq\Delta(G).\]
 
\end{thm}
\begin{proof}
Nechť $\vec{x}$ je nezáporný vlastní vektor matice $\vec{A}_{G}$
příslušný k vlastnímu číslu $\Lambda$. Zvolme jej tak, aby $\max_{i\in\hat{n}}x_{i}=1$
a označme $k=\arg\max_{i\in\hat{n}}x_{i}$. Potom (když $k$ jako
index dole udává $k$-tou složku)\begin{equation}
\Lambda=\left(\Lambda\vec{x}\right)_{k}=\left(\vec{A}_{G}\vec{x}\right)_{k}\leq\left(\vec{A}_{G}\left(\begin{array}{c}
1\\
\vdots\\
1\end{array}\right)\right)_{k}=\left(\begin{array}{c}
d_{G}(v_{1})\\
\vdots\\
d_{G}(v_{n})\end{array}\right)_{k}\leq\Delta(G).\label{eq:lambda-leq-deltaG}\end{equation}
 
 
Pro důkaz druhé nerovnosti lze použít vlastnosti spektrální normy
matice:\[
\Lambda=\max_{\left\Vert \vec{x}\right\Vert =1}\vec{x}^{\T}\vec{A}\vec{x}\geq\underbrace{\frac{1}{\sqrt{n}}(1,...,1)}_{\vec{x}_{0}^{\T}}\vec{A}_{G}\underbrace{\frac{1}{\sqrt{n}}\left(\begin{array}{c}
1\\
\vdots\\
1\end{array}\right)}_{\vec{x}_{0}}=\frac{1}{n}(1,...,1)\left(\begin{array}{c}
d_{G}(v_{1})\\
\vdots\\
d_{G}(v_{n})\end{array}\right)=\]
\[
=\frac{1}{n}\sum_{i=1}^{n}d_{G}(v_{i})\geq\frac{1}{n}\sum_{i=1}^{n}\delta(G)=\delta(G).\]
 
\end{proof}
\begin{rem*}
Kdy platí $\Lambda=\Delta(G)$? V (\ref{eq:lambda-leq-deltaG}) jsou
celkem dvě nerovnosti, v obou musí platit rovnost. Co se týká pravé
nerovnosti, musí $d_{G}(v_{k})=\Delta(G)$. Rovnost v levé nerovnosti,
tj.\[
\left(\vec{A}_{G}\vec{x}\right)_{k}\leq\left(\vec{A}_{G}\left(\begin{array}{c}
1\\
\vdots\\
1\end{array}\right)\right)_{k},\]
znamená\[
(a_{k1},...,a_{kn})\left(\begin{array}{c}
x_{1}\\
\vdots\\
x_{n}\end{array}\right)=(a_{k1},...,a_{kn})\left(\begin{array}{c}
1\\
\vdots\\
1\end{array}\right).\]
Víme, že $x_{k}=1$. Uvedená nerovnost vynucuje, aby $x_{j}=1$ pro
každé $i$ takové, že $a_{ki}=1$. Potom lze ale (\ref{eq:lambda-leq-deltaG})
napsat i pro $k=i$, opět musí platit v obou nerovnostech rovnost,
a z té pravé plyne $d_{G}(v_{i})=\Delta(G)$. Jinými slovy, vrchol
$k$ i všichni jeho sousedi $v_{i}$ musí mít stupeň roven $\Delta(G)$,
přičemž $x_{k}=1$, $x_{i}=1$ pro každé $i\in\left\{ \left.j\in\hat{n}\right|v_{j}\in N(v_{k})\right\} $.
Úvahu lze tedy zopakovat pro všechny sousedy vrcholu $v_{k}$, takže
i všichni sousedi všech sousedů $v_{k}$ musí mít stupeň $\Delta(G)$
atd.
\end{rem*}
\begin{cor}
Je-li $G$ souvislý graf, tak platí\[
\left(\Lambda=\Delta(G)\right)\Leftrightarrow\left(\delta(G)=\Lambda=\Delta(G)\right).\]
 
\end{cor}