Jak poznat stupeň souvislosti v grafu?

Úkol: Nechť $ G$ je $ d$-regulární graf s $ n$ vrcholy a $ E(A,B)$ je množina hran, které spojují nějaký vrchol z  $ A\subset V(G)$ s nějakým vrcholem z  $ B\subset V(G)$. Určete, jak souvisí

$\displaystyle \min_{\emptyset\subsetneq W\subsetneq V(G)}\frac{\vert E(W,V(G)\setminus W)\vert}{\vert W\vert\vert V(G)\setminus W\vert}$ (43)

s rozdílem prvního ($ \lambda_1$) a druhého ($ \lambda_2$) největšího vlastního čísla matice incidence grafu $ G$.

Tento výraz vyjadřuje ,,stupeň souvislosti grafu''. Pokud se graf například skládá ze dvou uvnitř dobře propojených částí, které jsou spojeny jen několika málo hranami, bude výraz 43 malý. U nesouvislých grafů je tento výraz nulový.


Poznámka k označení: V řešení budeme používat složkový skalární součin $ \langle\vec{a}\vert\vec{b}\rangle =\sum_i a_ib_i$. Tento zápis lze chápat také jako násobení řádkového vektoru sloupcovým vektorem. Pro vektor $ \vec{a}$ tedy znamená $ \vert\vec{a}\rangle $ sloupcový vektor jeho složek a $ \langle\vec{a}\vert =\vert\vec{a}\rangle ^T$.


Řešení: Označme $ n$ počet vrcholů grafu $ G$, $ \vec{j}=(1,\ldots,1)$, $ \vec{e}=\vec{j}/\sqrt{n}$ a $ \vec{w}$ charakteristický vektor množiny vrcholů $ W$, tedy vektor, který obsahuje jedničky pouze na místech odpovídajících vrcholům z množiny $ W$ a jinde nuly. Budeme vyšetřovat výraz $ \vert E(W,V(G)\setminus W)\vert=
\langle \vec{j}-\vec{w}\vert I_G \vec{w}\rangle$. Díky $ d$-regularitě víme, že $ I_G\vert\vec{j}\rangle =d\vert\vec{j}\rangle $ (tedy také $ \langle\vec{j}\vert I_G=d\langle\vec{j}\vert $) a podobně $ I_G\vert\vec{e}\rangle =d\vert\vec{e}\rangle $. Podle příkladu 7.6 je $ \lambda_1=d$.

   to $ \ds
\langle \vec{j}-\vec{w}\vert I_G \vert\vec{w}\rangle=
\langle \vec{j}\vert I_G \vert\vec{w}\rangle-
\langle \vec{w}\vert I_G \vert\vec{w}\rangle=\hfill$$\displaystyle \hss
$

$\displaystyle \lambda_1 \langle \vec{j}\vert\vec{w}\rangle-
\big\langle\langle ...
...
I_G \big\vert\vec{w}-\langle \vec{e}\vert\vec{w}\rangle
\vec{e}\big\rangle\,.
$

Použili jsme $ \langle\vec{w}-\vec{e}\langle\vec{e}\vert\vec{w}\rangle \vert I_G\vert\vec{e}\...
...d\langle\vec{w}-\vec{e}\langle\vec{e}\vert\vec{w}\rangle \vert\vec{e}\rangle =0$. Tato kolmost také ukazuje, že pokud rozvineme vektor $ \vec{x}=\vec{w}-\vec{e}\langle\vec{e}\vert\vec{w}\rangle $ do báze vlastních vektorů $ I_G$, bude složka u $ \vec{e}$ nulová. Potom ovšem $ \langle\vec{x}\vert I_G\vert\vec{x}\rangle \le \lambda_2\langle\vec{x}\vert\vec{x}\rangle $.

   to $ \ds
\langle \vec{j}-\vec{w}\vert I_G \vert\vec{w}\rangle\ge \lambda_1
\langle...
...\vert\vert\vec{w}-\langle \vec{e}\vert\vec{w}\rangle
\vec{e}\vert\vert^2=\hfill$$\displaystyle \hss
$

$\displaystyle \lambda_1 \vert W\vert - \lambda_1 \vert W\vert^2/n -
\lambda_2 (\langle \vec{w}\vert\vec{w} \rangle - \langle
\vec{e}\vert\vec{w} \rangle^2)=$

$\displaystyle \lambda_1(\vert W\vert-\vert W\vert^2/n)-\lambda_2(\vert W\vert-\vert W\vert^2/n)=
(\lambda_1-\lambda_2)(\vert W\vert-\vert W\vert^2/n)\,.$

Tyto výpočty lze shrnout (pro libovolné $ W\subset V(G)$, $ 0<\vert W\vert<n$)

$\displaystyle \frac{\vert E(W,V(G)\setminus W)\vert}{\vert W\vert\vert V(G)\set...
...\vert W\vert)}{n\vert W\vert(n-\vert W\vert)}=
\frac{\lambda_1-\lambda_2}{n}\,.$

To je spodní odhad pro minimum výrazu 43. Jako dodatek k bodu 5 příkladu 7.6 tedy vidíme, že u nesouvislých $ d$-regulárních grafů je už maximální vlastní číslo automaticky vícenásobné ( $ \lambda_2=\lambda_1$).

$ \ast$DK$ \ast$