01ZTGA:Kapitola1 13: Porovnání verzí

Z WikiSkripta FJFI ČVUT v Praze
Přejít na: navigace, hledání
(Založena nová stránka: %\wikiskriptum{01ZTGA})
 
 
Řádka 1: Řádka 1:
 
%\wikiskriptum{01ZTGA}
 
%\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}

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

PDF [ znovu generovat, výstup z překladu ] Kompletní WikiSkriptum včetně všech podkapitol.
PDF Této kapitoly [ znovu generovat, výstup z překladu ] Přeložení pouze této kaptioly.
ZIPKompletní zdrojový kód včetně obrázků.

Součásti dokumentu 01ZTGA

součástakcepopisposlední editacesoubor
Hlavní dokument editovatHlavní stránka dokumentu 01ZTGAKarel.brinda 15. 1. 201223:45
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůAdmin 7. 9. 201513:51
Header editovatHlavičkový souborKarel.brinda 15. 1. 201212:34 header.tex
Kapitola0 editovatÚvodKarel.brinda 15. 1. 201212:36 cast0.tex
Kapitola1_1 editovatZákladní pojmyKarel.brinda 15. 1. 201212:46 cast1_kapitola1.tex
Kapitola1_2 editovatSouvislostKarel.brinda 15. 1. 201212:49 cast1_kapitola2.tex
Kapitola1_3 editovatBipartitní grafyKarel.brinda 15. 1. 201212:50 cast1_kapitola3.tex
Kapitola1_4 editovatStromyKubuondr 5. 1. 201909:06 cast1_kapitola4.tex
Kapitola1_5 editovatHledání minimální kostry grafuKarel.brinda 15. 1. 201212:51 cast1_kapitola5.tex
Kapitola1_6 editovatJednotažkyKarel.brinda 15. 1. 201212:53 cast1_kapitola6.tex
Kapitola1_7 editovatHamiltonovské kružnice a grafyKarel.brinda 15. 1. 201213:34 cast1_kapitola7.tex
Kapitola1_8 editovatPárování v grafechKarel.brinda 15. 1. 201213:40 cast1_kapitola8.tex
Kapitola1_9 editovatToky v sítíchKarel.brinda 15. 1. 201213:44 cast1_kapitola9.tex
Kapitola1_10 editovatHranové obarvení grafuKarel.brinda 15. 1. 201213:48 cast1_kapitola10.tex
Kapitola1_11 editovatVrcholové obarvení grafuKarel.brinda 15. 1. 201213:52 cast1_kapitola11.tex
Kapitola1_12 editovatPlanární grafyKarel.brinda 15. 1. 201213:56 cast1_kapitola12.tex
Kapitola1_13 editovatVlastní čísla adjacenční matice grafuKarel.brinda 15. 1. 201213:57 cast1_kapitola13.tex
Kapitola2_1 editovatBrouwerova věta o pevném boděKarel.brinda 15. 1. 201214:11 cast2_kapitola1.tex
Kapitola2_2 editovatPravděpodobnostní důkazy v teorii grafůKarel.brinda 15. 1. 201214:12 cast2_kapitola2.tex
Kapitola2_3 editovatExtremální teorie grafůKarel.brinda 15. 1. 201214:16 cast2_kapitola3.tex
Kapitola2_4 editovatRamseyovská číslaKarel.brinda 15. 1. 201214:18 cast2_kapitola4.tex
Kapitola3_1 editovatObyčejné mocninné řadyKarel.brinda 15. 1. 201214:22 cast3_kapitola1.tex
Kapitola3_2 editovatExponenciální generující funkceKarel.brinda 15. 1. 201214:22 cast3_kapitola2.tex

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}