NDMI 058 -- Toky a cykly v grafech

V roce 2009/2010 přednáší Robert Šámal a Tomáš Kaiser (cca 3 přednášky)

Další info v SISu, časem zde přibudou aktuálnější informace o probíraných tématech.
Přednášet se začíná druhý týden v semestru.

Poznámky z přednášky (většina semestru, ale zatím hodně syrová verze).

příklady po předposlední přednášce

1) Buď $G$ sjednocení vrcholově disjunktních sudých kružnic. Jak vypadá polytop perfektních párování grafu $G$? 2) Buď $G$ kubický graf bez mostů. Kolik nejvíce hran $G$ lze pokrýt třemi párováními? 3) Dokažte charakterizaci $MP$ pomocí charakterizace $PMP$. Návod: vezměte dvě kopie daného grafu. Pro každý vrchol původního grafu spojte jeho dvě kopie hranou s vhodnou vahou.

příklady po páté přednášce

1) třetí příklad z minula 2) dokončete chybějící část důkazu věty "o vyvážených orientacích".

příklady po čtvrté přednášce

(Snad je to v tom texu pro všechny čitelné. Zkusím to brzy vystavit v lepší formě. Prozatím: \calF je psací F, \perp je symbol "kolmítko".)


1) Buď $G$ orientovaný multigraf, jehož hrany jsou obarveny červeně, modře a zeleně.
Pro libovolné dva vrcholy $u$, $v$ v $G$ jsou následující tvrzení ekvivalentní:

 a) existuje cesta $P$ z $u$ do $v$ (ne nutně orientovaná správným směrem), která 
 nepoužívá žádnou červenou hranu a všechny modré hrany jsou orientované ve směru cesty.

 b) $u$, $v$ nejdou "oddělit": neexistuje množina $U$, která by obsahovala $u$, ale ne $v$, taková, že
 všechny hrany, které vedou mezi $U$ a zbytkem grafu jsou buďto červené, nebo jsou modré a vedou do $U$.


2) Pro každý graf bez mostů existuje nenulový tok (v dostatečně velké grupě).


3) Buď $G$ or.multigraf, $\Gamma$ těleso. Označme $V$ vektorový prostor $\Gamma^{E(G})$ a $\calF = \calF_\Gamma(G)$
jeho podprostor tvořený všemi $\Gamma$-toky na $G$.
Uvažme skalární součin $f\cdot g = \sum_e f(e)g(e)$. 
a) Nalezněte ortogonální doplněk k $\calF$ ve $V$, tj. vektorový prostor 
$\calF^\perp = \{x \in V: x \cdot f = 0 \mbox{pro všechna $f \in \calF$}\}$. 
b) Nalezněte bázi prostoru $\calF^\perp$.
c) Může $\calF \cap \calF^\perp$ obsahovat nenulový vektor?

příklady po třetí přednášce

žádné

příklady po druhé přednášce

1) a) Najděte nenulový 5-tok pro Petersenův graf. b) Najděte nenulový 4-tok pro K₄.
2) Kubický graf s mostem nemá hranové 3-obarvení (dokažte přímo, bez použití toků).
3)Symetrie Petersenova grafu:
a) Kneserův graf K(n,k) má jako vrcholy všechny k-prvkové podmnožiny n-prvkové množiny. Dva vrcholy jsou spojené hranou, pokud příslušné množiny jsou disjunktní. Ukažte, že Petersenův graf je isomorfní K(5,2).

Řekneme, že graf $G$ je $H$-transitivní, pokud kdykoli jsou $H_1$, $H_2$ podgrafy $G$, a oba $H_i$ jsou isomorfní s $H$, existuje automorfismus $G$, který převádí $H_1$ na $H_2$.
Řekneme, že graf $G$ je silně $H$-transitivní, pokud kdykoli jsou $H_1$, $H_2$ podgrafy $G$, oba $H_i$ jsou isomorfní s $H$ a $f: H_1 \to H_2$ je nějaký isomorfismus, tak existuje automorfismus $G$, který rozšiřuje $f$.

b) Petersenův graf je $K_1$-transitivní (neboli vrcholově tranzitivní).
c) Petersenův graf je $K_2$-transitivní (neboli hranově tranzitivní).
d) Petersenův graf je silně $K_2$-transitivní (neboli obloukově tranzitivní, arc-transitive).
e) Petersenův graf je silně $T$-transitivní, kde $T$ je strom s 5 hranami, který v Petersenově grafu tvoří hrana a čtyři hrany s ní sousedící.
f) Petersenův graf je $M$-transitivní, kde $M$ je párování s 5 hranami.

příklady po první přednášce

Odevzdání -- do příští přednášky, nejlépe přímo před ní, případně emailem.
1) a) Nalezněte tokový polynom pro $K_4$. Aplikujte na grupy $Z_4$ a $Z_2^2$.
b) Bez použití části a) zjistěte, kolik má $K_4$ nenulových $Z_4$-toků. (Orientaci si vyberte jakou chcete, neboť na ní nezáleží.)
c) Bez použití částí a), b) zjistěte, kolik má $K_4$ nenulových $Z_2^2$-toků.

2) Nelezněte nenulový $\Gamma$-tok pro Petersenův graf (na obrázku) a co nejmenší grupu $\Gamma$.