Počet koster

Úkol: Dokažte, že v orientovaném grafu $ G$$ n\ge 2$ vrcholy se skrývá právě $ \mathop{\rm det}\nolimits Q'$ různých koster. $ Q'$ je Laplaceova matice bez prvního řádku a prvního sloupce (viz příklad 7.2). Kostra grafu je jeho libovolný podgraf, který je strom. Návod: použijte příklady 7.1, 7.2, 8.8.

Pomocí tohoto vzorce pak určete počet koster úplného grafu, tedy grafu, kde každé dva vrcholy jsou spojeny hranami v obou směrech.


Řešení: Nejprve se budeme věnovat grafům, které mají alespoň $ n-1$ hran. Podle Cauchyovy-Binetovy věty (příklad 8.8), je determinant matice $ Q'$ roven součtu kvadrátů determinantů všech podmatic matice $ B'$$ n-1$ sloupci. Tyto podmatice odpovídají (bijektivně) podgrafům grafu $ G$ s právě $ n-1$ hranami a podle příkladu 7.1 mají determinanty $ \pm 1$ právě tehdy, pokud je tento podgraf strom, tedy je kostrou grafu $ G$; jinak je jejich hodnota nula. Tedy determinant matice $ Q'$ je roven počtu podgrafů grafu $ G$, které jsou stromy, neboli je roven počtu koster grafu $ G$.

Nyní obrátíme pozornost ke grafům s méně jak $ n-1$ hranami. Takový graf $ G$ nemá žádnou kostru (neboť není souvislý), a tedy stačí ukázat singularitu matice $ Q'$. Hodnost matice $ B'$ je nejvýše $ n-2$ (tolik má nejvýše sloupců). Tedy hodnost matice $ Q'$ je nejvýše $ n-2$ dle věty o hodnosti součinu matic a tedy matice $ Q'$ je singulární. Její determinant je tedy nula, což je i počet podgrafů grafu $ G$, které jsou stromy.

Je-li $ G$ úplný graf, potom $ Q'=n\mathbbm{1}-J$, kde $ \mathbbm{1}$ je jednotková matice a $ J$ matice ze samých jedniček, obě jsou řádu $ n-1$. Podle výsledků příkladu 9.3 má matice $ Q'$ dvě vlastní čísla: $ (n-2)$-násobné $ n$ a jednonásobné $ n-(n-1)=1$. Determinant matice je součinem jejích vlastních čísel (braných v jejich algebraické násobnosti) a tedy platí $ \mathop{\rm det}\nolimits Q'=n^{n-2}$. Počet koster úplného grafu na $ n$ vrcholech je tedy $ n^{n-2}$.

$ \ast$DK$ \ast$