Z poslední přednášky (8-mé): Probrali jsme něco... tuším, že šlo o další důkaz počtu neisomorfních stromů a následně ještě něco k izomorfismu stromů. Já to ale přesně nevím, protože jsem to vůbec nestíhal. Omluvte tedy zatím mojí minulou indispozici, pokusím se jí napravit jakmile to bude jen trochu možné.
Přípravné práce k Větě o prostoru cyklů grafu (na straně 330):
Mluvili jsme mimo jiné o Kihofových zákonech (píše se to jinak, ale to není podstatné), což si možná ještě mnozí pamatujete, napovím: mluví o elektrickém napětí a druhý o el. proudu. Jsou tedy dva z jednoho vyplýval vztah pro napětí v elektrické smyčce (tedy že je rovno nule) a z druhého zase že součet proudů vstupujících a vystupujících z uzlu je roven nule. Možná v opačném pořadí, to si už nepamatuju.
Mějme úplný graf Kn=(V,E). V={1,2,...,n}.
Ptáme se, kolik má takový úplný graf kružnic:
Pro ty co to přečtou napíšu-li to slovy je to Suma ((n nad k)*((k-1)!)/2) pro k od 3 do n.
Mějme G=(V,E) pevně zvolený graf.
E={e1, e2, ..., em} je pevně dané očíslování hran (je libovolné, ale již neměnné)
E' Í E je Eulerovská, jestliže graf (V,E') má všechny stupně sudé.
Měli jsme Lemma, že E' je Eulerovská Ű $ kružnice E1, ..., Ek v G tak, že
1) ČEi (i=1,..,k) = E'
2) Ei Ç Ej (iąj) = 0
({0,1}, +, *) těleso Z2
{0,1}m = množina m-člených 0-1 vektorů (x1, ..., xm) xiÎ{0,1}
({0,1}m, +, *) je vektorový prostor; +,* je definováno po složkách; odpovídá množině všech podmnožin množiny E (viz charakteristická funkce).
Označme třeba Q (na přednášce jsme jej označili "kroucené" E) množinu všech charakteristických vektorů Eulerovských podmnožin.
Tedy Q = {kE'; E' Í E & E' Eulerovský}
A už Věta o prostoru cyklů (kružnic) grafu (VOPKG)
Pro každý graf G platí:
1) Q je vektorový prostor (podprostor {0,1}m)
2) Je-li G souvislý graf, potom dim(Q)=|E|-|V|+1
3) Báze Q je tvořena všemi elementárními kružnicemi vzhledem k nějaké (pevně zvolené) kostře grafu
Důkaz:
1) pro nulový vektor, tedy (0,...,0) je char. množina prázdné množiny E' a 0 je Eulerovská.
0*x=0 (vektor); 1*x=x;
zbývá ještě x,y Î Q Ţ x+y Î Q
Buď x char. vektor E' Eulerovské a y char. vektor E'' také Eulerovské a tvrdíme, že x+y je char. vektor množiny E'DE'' kde E'DE'' definujeme jako (E'-E'') Č (E''-E') tedy sjednocení obou množin mínus jejich průnik.
Tedy stačí ukázat, že když jsou E' a E'' Eulerovské pak E'DE'' je také Eulerovská. Pak je jejich char. vektor také v Q.
Zvolme libovolný vrchol v. Označme k počet hran počet hran vycházejících z v naležících do E' i E'', tedy také do jejich průniku. Pak počet hran, který zbude v E'DE'' je:
|{e Î E'DE''; v Î e}| = |{e Î E'; v Î e}| - k + |{e Î E''; v Î e}| - k = |{e Î E'; v Î e}| + |{e Î E''; v Î e}| - 2k
A protože |{e Î E'; v Î e}| je sudé číslo (E' je Eulerovský) a |{e Î E''; v Î e}| je také sudé číslo (ze stejného důvodu (E'')) pak výsledek je opět sudý, tedy E'DE'' je Eulerovská. Pak tedy jeho char. vektor je v Q což je součet x+y a tedy Q je vektorový prostor.
Teď malá odbočka od důkazu, ještě se k tomu vrátíme a dokážeme 2) a 3)
Věta:
G=(V,E), T=(V,E0) je pevně zvolená kostra grafi G. G předpokládáme souvislý.
Vezmu-li e Î E-E0; e={x,y} a tvrdím, že graf (V,E0 Č {e}) obsahuje právě jednu kružnici.
Tedy lidsky: mám-li strom nějakého souvislého grafu a přidám do něj jedinou hranu, která v něm ještě nebyla ale v samotném souvislém grafu ano, pak vznikne právě jedna kružnice. To, že je to pravda je asi jasné, pokud si představíte strom grafu s jedinou komponentou, pak přidáním jedné hrany zcela jistě vznikne kružnice, neboť strom je maximální graf bez kružnic jak jsme dokazovali tuším v 7-me přednášce. Ale proč jen jedna jediná ? No to je dle mého dosti patrné... prostě proto, že spojím dva body x,y, které již spojené byly, ale díky tomu že byly "spojeny" stromem, pak může existovat jediná cesta z x do y (před přidáním) a to společně s přidanou hranou vytvoří kružnici.
Ale důkaz: Víme, že (V,E0 Č {e}) obsahuje kružnici (jak jsem již psal, strom je max. graf bez kružnic, tedy proto). Pokud by (V,E0 Č {e}) obsahoval dvě různé kružnice s množinami hran E', E'' pak e Î E', E'' a tedy graf (E' Č E'')-{e} obsahoval kružnici, což je spor.
Tato (jednoznačně určená) kružnice se nazývá elementární kružnice určená e,T a značíme ji (kde T je strom) Ke(T)
A vracíme se k důkazu....
Pokud ukážu, že je Q báze, pak jsem hotov, neboť dimenze je počet prvků Q tedy |Q|=|množina všech elementárních kružnic|=|E|-|E0|=|E|-|V|+1 (tedy všechny hrany mínus hrany stromu (těch je |V|-1 u souvislého grafu, tedy grafu s jedinou komponentou).
Důkaz: 3)
E0={e1, ..., en-1} tj. při vhodném očíslování :-)) zcela jistě můžu zajistit abych měl v množině hran stromu grafu právě tyhle hrany.
Nechť E' je elementární kružnice určená hranou ei i ł n.
Pak kE' = ((n-1)nějakých nul, či jedniček a, 0,0,...,0,1,0,...,0) kde 1-čka je na i-tém místě a kE' značí charakteristickou funkci (vektor) množiny E'.
Jsou takové kEi LN ? No zcela zřejmě ano, neboť každý takový vektor má právě na i-tém místě 1-čku což již nemá žádný z dalších (jiných !) Ei. Tedy charakteristické vektory (funkce) elementárních kružnic jsou LN.
Dokážeme, že char. vektory el. kružnic (všech) vzhledem k nějaké pevně dané kostře T T=(V,E0) generuje Q
E' Í E libovolná Eulerovská množina.
Definujme množinu E'' předpisem: kE''=Součet kKe pro každé e Î E'-E0
E'' je Eulerovská, jak jsme dokázali v 1)
Ukáži, že E''=E'
Uvažme množinu (E'DE''). Dokážeme, že (E'DE'') Í E0 (neboť platí, že E'-E0=E''-E0; plyne z toho, že jediná elementární kružnice obsahující e je Ke(T))
A (E'DE'') je Eulerovská množina. Tedy pak (E'DE'')=0 neboť to je jediná Eulerovská podmnožina stromu. Strom není Eulerovský tj. zcela jistě nemá všechny stupně sudé.
A tedy E' Ç E0 = E'' Ç E0 a tedy E'=E''
Důsledek: |Q| = 2|E|-|V|+1