Vlastnosti matice incidence grafu

Úkol: Označme $ I_G$ matici incidence grafu $ G$$ n$ vrcholy (definici viz v příkladu 7.5). Dokažte následující tvrzení.

  1. Všechna její vlastní čísla jsou reálná. Navíc pro všechna vlastní čísla je jejich geometrická a algebraická násobnost stejná.
  2. Všechna její vlastní čísla jsou v absolutní hodnotě menší nebo rovna maximálnímu stupni v grafu $ G$.
  3. Existuje vlastní vektor s nezápornými složkami příslušející největšímu vlastnímu číslu. Použijte výsledků příkladu 14.1.
  4. Největší vlastní číslo je alespoň velikost minimálního stupně v grafu $ G$.
  5. Pokud je největší vlastní číslo vícenásobné, potom je graf $ G$ nesouvislý. Dokažte, že opačná implikace nemusí platit.
  6. Určete největší vlastní číslo a k němu příslušný vlastní vektor pro $ d$-regulární graf (každý vrchol je spojen právě s $ d$ ostatními vrcholy).
  7. Pokud je graf $ G$ bipartitní a $ \lambda$ je jeho vlastní číslo, potom i $ -\lambda$ je jeho vlastní číslo. Navíc násobnost vlastních čísel $ \lambda$ a $ -\lambda$ je stejná.


Řešení:


1. Matice incidence jsou symetrické, a tedy algebraické a geometrické násobnosti jejich vlastních čísel se shodují a jejich vlastní čísla jsou reálná. Navíc z jejich vlastních vektorů lze sestavit ortogonální bázi.


2. Pokud by $ \lambda$ bylo vlastní číslo matice incidence větší než maximální stupeň v grafu, potom by byla matice $ I_G-\lambda \mathbbm{1}$ ostře diagonálně dominantní, tedy regulární (definici a důkaz viz v příkladu 1.4 či 9.2). Pak ale $ \lambda$ nemůže být vlastním číslem matice $ I_G$.


3. Za vektor $ \vec{x}$ z příkladu 14.1 budeme volit postupně prvky kanonické báze. Všechny takto vytvořené posloupnosti obsahují nezáporné vektory (neboť matice $ I_G$ má nezáporné elementy). Mohou nastat dva případy. Buď některá z posloupností konverguje k vlastnímu vektoru odpovídajícmu největšímu kladnému vlastnímu číslu ( $ \lambda_{{\rm max}}$) matice incidence a pak jsme hotovi. Nebo mohla mít matice $ I_G$ také vlastní číslo $ -\lambda_{{\rm max}}$, ale pak alespoň jedna z posloupností má dva hromadné body, jejichž součet je vlastní vektor k  $ \lambda_{{\rm max}}$.


4. Označme $ \vec{v}_1$ nezáporný vektor příslušející největšímu vlastnímu číslu $ \lambda_1$. Pokud je $ \lambda_1$ nulové (a přitom největší), musí být všechna její vlastní čísla nulová (neboť stopa $ I_G$ je nula), a tedy je $ I_G$ nulová a uvažovaný graf je tvořen pouze izolovanými vrcholy. Tvrzení příkladu je v tomto případě triviální.

Nechť nadále $ \lambda_1>0$. Nechť $ i_0$ je složka vektoru $ \vec{v}_1$ s nejmenší nenulovou hodnotou a nechť $ I$ je množina indexů, které odpovídají vrcholům, které leží ve stejné komponentě souvislosti jako $ i_0$. Zřejmě $ (\vec{v}_1)_i\ge (\vec{v}_1)_{i_0}$ pro $ i\in I$; žádná z těchto složek totiž nemůže být nulová22, neboť jejich vrcholy leží ve stejné komponentě souvislosti jako vrchol odpovídající $ i_0$. Označme $ \delta $ minimální stupeň v grafu $ G$. Potom platí

$\displaystyle \lambda_1 (\vec{v}_1)_{i_0}=(I_G\vec{v}_1)_{i_0}\ge
\sum\limits_{i\in N(i_0)} (\vec{v}_1)_i\ge
\delta (\vec{v}_1)_{i_0}\,,$

sčítá se přes sousedy vrcholu odpovídajícího $ i_0$. Odtud pak již přímo plyne $ \lambda_1\ge\delta$.


5. Označme $ \vec{v}_1$ a $ \vec{v}_2$ lineárně nezávislé vlastní vektory příslušející vlastnímu číslu $ \lambda_1>0$ (případ $ \lambda_1=0$ je triviální). Bez újmy na obecnosti lze předpokládat, že $ \vec{v}_1$ je nezáporný, a že vektor $ \vec{v}_2$ obsahuje nějaké kladné složky. Uvažme nyní vektor $ \vec{v}=\vec{v}_1-\alpha
\vec{v}_2$, kde $ \alpha$ je největší kladné číslo takové, že vektor $ \vec{v}$ je ještě nezáporný. Některé složky $ \vec{v}$ jsou nulové (jinak lze zvolit $ \alpha$ větší), ale ne všechny jeho složky ($ \vec{v}_1$ a $ \vec{v}_2$ jsou lineárně nezávislé). Žádný z vrcholů, jehož složka ve $ \vec{v}$ je nulová, nemůže být spojen cestou s kterýmkoli vrcholem, jehož složka je ve $ \vec{v}$ nenulová; jinak by totiž nemohlo platit $ \lambda_1 \vec{v}=I_G \vec{v}$. Potom ale tyto vrcholy leží v různých (ne nutně dvou) komponentách grafu, a tedy uvažovaný graf není souvislý.

Protipříklad k opačnému tvrzení (k bodu 5) najděte sami, stačí uvažovat vhodný graf se třemi vrcholy.


6. Největší vlastní číslo je $ d$ (díky bodům 2 a 4 nemůže být ani větší ani menší) a odpovídající vlastní vektor je $ (1,\ldots,1)$.


7. Nechť $ \vec{v}$ je vlastní vektor příslušný k vlastnímu číslu $ \lambda$. Změňme znaménko u všech složek vektoru $ \vec{v}$, které odpovídají vrcholům v jedné z partit; takto získáme vektor $ \vec{v}\,'$. Potom $ I_G \vec{v}\,'=-\lambda \vec{v}\,'$ (viz též příklad 7.5, bod 2), a tedy i $ -\lambda$ je vlastním číslem matice incidence. Z postupu důkazu je též vidět, že se násobnosti vlastních čísel $ \lambda$ a $ -\lambda$ shodují. Existuje totiž izomorfismus příslušných vlastních podprostorů (toto zobrazení spočívá v záměně znamének u složek odpovídajích vrcholům v jedné z partit).

$ \ast$DK$ \ast$