Prostor cyklů grafu

Úkol: Označme $ G_E$ množinu eulerovských podgrafů souvislého grafu $ G$, čili podgrafů, jejichž všechny vrcholy mají sudé stupně. Uvažme {\bb Z}$ _2^m$, kde $ m$ je počet hran $ G$, a ztotožněme přirozeným způsobem vektory tohoto prostoru s podgrafy grafu $ G$. Označme $ E$ množinu vektorů reprezentujících podgrafy z $ G_E$. Dokažte, že $ E$ je vektorový podprostor a je algebraickým doplňkem20 množiny $ S$, obsahující vektory odpovídající podgrafům $ S^v$, kde $ v$ jsou vrcholy grafu $ G$ (vše nad tělesem {\bb Z}$ _2$). Podgraf $ S^v$ obsahuje právě ty hrany grafu $ G$, které jsou incidentní21 s vrcholem $ v$. Odtud dokažte, že dimenze $ E$ je $ m-n+1$, kde $ n$ je počet vrcholů grafu $ G$.


Řešení: $ E$ je vektorový podprostor (nad {\bb Z}$ _2$, tedy $ 1+1=0$), neboť obsahuje nulový vektor (prázdný podgraf je eulerovský) a součet dvou jeho libovolný vektorů mu také náleží (symetrická diference dvou eulerovských grafů je eulerovský graf). Nechť $ \vec{w}\in E$ a $ \vec{s}^v$ je vektor odpovídající libovolnému podgrafu $ S^v$. Potom počet nenulových složek v součtu $ \sum\nolimits_{i=1}^{m}w_i{(\vec{s}^v)}_i$ je roven stupni vrcholu $ v$ v podgrafu odpovídajícím vektoru $ \vec{w}$, a je tedy sudý, neboli nulový (modulo dvě). Navíc, každý vektor $ \vec{w}$, který splňuje výše uvedenou rovnost pro všechny $ \vec{s}^v$, nutně odpovídá nějakému eulerovskému podgrafu. Tedy $ E$ je právě algebraickým doplňkem $ S$. Pokud ukážeme, že $ \dim
\mathop{\mbox{{\Cal L}}}\nolimits(S)=n-1$, obdržíme okamžitě $ \dim E=m-(n-1)=m-n+1$.

Dimenze $ S$ je nejvýše $ n-1$, neboť $ \sum\nolimits_{v} \vec{s}^v$ je nulový vektor, a tedy vektory v $ S$ nejsou lineárně nezávislé. Nechť $ W$ je libovolná neprázdná podmnožina vrcholů, jejíž mohutnost je nejvýše $ n-1$. Potom $ \sum\nolimits_{v\in W} \vec{s}^v$ (to je obecná lineární kombinace nad {\bb Z}$ _2^m$) má nenulovou složku na místě hrany, spojující některý z vrcholů z $ W$ s některým z vrcholů mimo $ W$. Tedy vskutku libovolných (nejvýše) $ n-1$ vektorů množiny $ S$ je lineárně nezávislých a tedy $ \dim S=n-1$.

$ \ast$DK$ \ast$