Je to strom nebo není to strom?

Úkol: Nechť $ G$ je orientovaný graf na $ n\ge 2$ vrcholech s $ n-1$ hranami. Označme $ A$ matici typu $ n\times (n-1)$ takovou, že $ A_{ij}=-1$, pokud hrana $ j$ vychází z vrcholu $ i$, $ A_{ij}=1$, pokud hrana $ j$ vchází do vrcholu $ i$ a $ A_{ij}=0$ jinak. Nechť $ A'$ je matice, která vznikne z $ A$ vynecháním prvního řádku. Dokažte, že $ A'$ je singulární právě tehdy, pokud $ G$ obsahuje cyklus; to je v našem případě ekvivalentní tomu, že $ G$ není strom, a také tomu, že $ G$ není souvislý. Navíc, pokud $ A'$ není singulární, potom platí $ \vert\!\mathop{\rm det}\nolimits A'\vert=1$.


Řešení: Nechť $ G$ obsahuje kružnici; můžeme zvolit takovou, která sama sebe nekříží. Označme $ \vec{w}$ vektor řádu $ n-1$, jehož nenulové složky jsou pouze na pozicích hran ležících na této kružnici. Zvolme si směr obíhání po této kružnici a za každou hranu na této kružnici, která jde po směru (resp. proti směru) obíhání, napíšeme do $ \vec{w}$ do příslušné složky $ 1$ (resp. $ -1$). Potom $ A'\vec{w}$ je nulový vektor: aby mohla být $ j$-tá složka vektoru $ \vec{w}$ a zároveň i $ i$-tého řádku $ A'$ nenulová, musí $ i$-tý vrchol ležet na zvolené kružnici a musí jím procházet $ j$-tá hrana. Pro daný bod to buďto není žádná hrana, nebo jsou to právě dvě hrany. V každém případě (obě dovnitř; obě ven; jedna ven a jedna dovnitř) je složkový součin $ \vec{w}$$ i$-tým řádkem $ A'$ roven nule. Je tedy $ A'\vec{w}=0$, a tudíž musí být matice $ A'$ singulární.

Nechť naopak $ G$ neobsahuje kružnici, a je tedy strom (vzhledem k počtu hran nelze v takovém případě sestrojit nesouvislý graf). Je-li $ n=2$, je tvrzení zřejmé, nechť tedy $ n>2$. Protože $ G$ je strom, obsahuje alespoň dva vrcholy stupně jedna. Alespoň jeden z těchto vrcholů, označme ho $ v$, odpovídá některému z řádků matice $ A'$. Podle tohoto řádku, který obsahuje pouze jediný nenulový prvek, lze determinant matice $ A'$ rozvinout -- vzniklá matice $ A''$ odpovídá grafu $ G'$, který vznikne z $ G$ vynecháním vrcholu $ v$. Tento graf je také strom: cyklus jsme nepřidali, ani jsme graf neroztrhli na dvě nesouvislé části. Nyní řekneme, že důkaz vedeme indukcí dle počtu vrcholů grafu $ G$; dle indukčního předpokladu platí $ \vert\!\mathop{\rm det}\nolimits A''\vert=1$ a tedy $ \vert\!\mathop{\rm det}\nolimits A'\vert=\vert\pm 1\vert\vert\!\mathop{\rm det}\nolimits A''\vert=1$, čímž je tvrzení příkladu dokázáno.

$ \ast$DK$ \ast$