Totálně cyklické orientace

Úloha číslo: 3288

Orientace grafu je totálně cyklická, pokud každá hrana leží v orientované kružnici. Dokažte, že graf \(G\) má \(T_G(0{,}2)\) totálně cyklických orientací.

  • Nápověda

    Použijte rekurentní vztah pro výpočet Tutteho polynomu.

  • Řešení

    Označme \(O(G)\) počet totálně cyklických orientací grafu \(G\). Dosazením 0 a 2 do Tutteho polynomu dostaneme následující vztah:

    \[ O(G) = \begin{cases} 0 & \textrm{pokud $e$ je most,} \\ 2O(G-e) & \textrm{pokud $e$ je smyčka, } \\ O(G-e) + O(G/e) & \textrm{pokud $e$ není most ani smyčka.} \end{cases} \]

    Pro prázdný graf pak \(O(G) = 1\).

    První dvě možnosti jsou jednoduché. Graf s mostem nemůže obsahovat totálně cyklickou orientaci díky mostové hraně. Naopak smyčku v grafu mohu zorientovat libovolným ze dvou možných způsobů a tedy počet orientací je dvakrát větší, než po odebrání smyčky. Smyčka také nemá žádný vliv na existenci orientace.

    Pro poslední vztah je potřeba rozebrat několik případů. Mějme totálně cyklickou orientaci grafu \(G\), že při otoční hrany \(e\) již totálně cyklickou nebude. Pak to bude dobrá orientace i pro \(G/e\), ale v \(G-e\) se nezapočítá. Pokud je možné hranu otočit, započte se jednou v \(G/e\) a jednou v \(G-e\). Zde je potřeba si vyzkoušet, že pokud hrana je otočitelná, tak i po jejím odebrání je orientace stále totálně cyklická.

    Víme tedy, že orientace z \(G\) se započtou. Ještě je potřeba ověřit, že nezapočteme nic navíc.

    Pokud je totálně cyklická orientace společná pro \(G/e\) a \(G-e\), tak na orientaci hrany \(e\) nezáleží a lze ji zvolit oběma způsoby.

    Pokud orientace \(G/e\) je totálně cyklická ale pro \(G-e\) není, pak existuje hrana \(f\), která si ve svém cyklu \(C\) v \(G\) vynucuje průchod hranou \(e\) v učitém směru.

    Kdyby tato orientace nebyla vhodná, tak ještě existuje hrana \(f’\), která ve svém cyklu \(C’\) nutí opačnou orientaci hraně \(e\), viz obrázek.

    Common cycle

    Pak ale ze společných vrcholů obou cyklů zvolíme vrcholy \(u\) a \(v\), třeba tak, aby byly nejblíže hraně \(e\) podél cyklu \(C\). Cyklus \(u-f’-v-f-u\) ovšem v dané orientaci vyhovuje orientacím hran \(f\) a \(f’\), aniž by procházel hranou \(e\).

    Tnto případ nemůže nastat, tedy taková hrana \(f’\) neexistuje a orientace \(e\) je určena jednoznačně a příslušná totálně cyklická orientace je započtena jen jedenkrát.

    Orientace, které by byly totálně cyklické v \(G-e\), ale nikoli v \(G/e\) nemohou existovat, protože sloučením dvou vrcholů do jednoho žádný cyklus nepřerušíme, ale nanejvýš nějaký rozdělíme na dva.

Obtížnost: Obtížná úloha
Úloha řešená úvahou
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze