Eulerovské množiny hran

Úloha číslo: 3652

Nechť \(G=(V, E)\) je graf. Množina hran \(E’ \subseteq E\) je eulerovská, jestliže graf \((V, E’)\) má všechny stupně sudé. (Nevyžadujeme, aby byl podgraf souvislý.)

  • Varianta

    Dokažte, že soubor všech eulerovských množin hran daného grafu je uzavřený na symetrickou diferenci. Tedy, dokažte, že pokud \(E_1, E_2 \subseteq E\) jsou eulerovské množiny hran, potom, \(E_1 \Delta E_2\) je také eulerovská množina hran.

  • Řešení

    Jsou-li \(E_1\) a \(E_2\) eulerovské, a \(v\) je libolovolný vrchol, potom stupeň \(v\) ve \((V,E_1 \Delta E_2)\) je roven součtu stupňů vrcholu \(v\) ve \((V,E_1)\) a \((V,E_1)\), ovšem dvakrát musíme odečíst každou hranu se kterou je \(v\) incidentní v průniku \(E_1 \cap E_2\).

    Součet resp. rozdíl tří sudých čísel je sudé číslo, tedy \(E_1 \Delta E_2\) je eulerovská.

  • Varianta

    Dokažte, že pro každou eulerovskou množinu hran \(E’\) je \(G = (V, E’)\) sjednocením hranově disjunktních kružnic.

  • Řešení

    Dokazujeme indukcí podle počtu hran v \(E’\).

    Je-li \(E’\) prázdná, jde o prázdné sjednocení.

    Je-li neprázdná, zvolíme libovolný vrchol stupně alespoň dvě a z něj vedeme libovolný tah. Protože stupně jsou alespoň dva, lze tento tah lze prodlužovat tak dlouho, dokud se nějaký vrchol \(v\) na tahu nezopakuje. Úsek tohoto tahu mezi dvěma výskyty \(v\) určuje kružnici \(C\).

    Protože \(C\subseteq E’\), je \(C \Delta E’=E’\setminus C\) a tedy \(E’\setminus C\) má méně hran než \(E’\). Z předchozí varianty víme, že \(E’\setminus C\) je eulerovská a dle indukčního předpokladu ji lze rozložit na disjunktní sjednocení kružnic. Přidáním \(C\) do tohoto rozkladu získáme hledaný rozklad.

  • Varianta

    Uměli byste určit počet všech eulerovských množin hran daného grafu?

  • Nápověda

    Zvolte libovolnou kostru (v případě nesouvislého \(G\) sjednocení koster jeho komponent). Každá mimokostrová hrana vytvoří spolu s vybranymi hranami kostry cyklus.

    Ukažte, že tyto cykly jsou lineárně nezávislé a přitom generují vektorový prostor eulerovských množin. Jejich počet určuje dimenzi tohoto prostoru a z něj lze odvodit i počet eulerovských množin.

  • Řešení

    Je-li \(e\) mimokostrová hrana a \(C\) odpovídající cyklus, potom tuto hranu nelze eliminovat žádnou linární kombinací ostatních cyklů odpovídajících mimokostrovým hranám, jednoduše proto, že ji žádný z těchto cyklů neobsahuje. Proto je systém mimokostrových cyklů lineárně nezávislý.

    Nechť \(K\) je pevně zvolená kostra a \(E’\) je libovolná eulerovská množina. Ukážeme, že \(E’\) lze vyjádřit jako lineární kombinací cyklů určených hranami \(E’\setminus K=\{e_1,\dots,e_k\}\). Označme \(C_i\) cyklus určený mimokostrovou hranou \(e_i\). Množina \(R=E’ \Delta C_1 \Delta \dots \Delta C_k\) neobsahuje žádnou mimokostrovou hranou \(e_i\), protože tyto mají v symetrické diferenci právě dva výskyty: jednou v \(E’\) a podruhé v \(C_i\).

    Tedy \(R\subseteq K\) a přitom \(R\) je eulerovská. Protože by každý neprázdný podgraf kostry musel obsahovat list, t.j. vrchol stupně 1, musí být \(R\) prázdná, neboli \(E’ = C_1 \Delta \dots \Delta C_k\). Tím jsme ukázali, že cykly odpovídající nekostrovým hranám generují prostor eulerovských množin.

    Zbývá dopočítat, že sjednocení koster komponent \(G\) má \(|V|-c\) hran, kde \(c\) je počet komponent grafu \(G\).

  • Odpověď

    Počet eulerovských množin grafu s \(c\) komponentami souvislosti je \(2^{|E|-|V|+c}\).

Obtížnost: Obtížná úloha
Úloha na dokazování, ověřování
Úloha vyžadující neobvyklý trik nebo nápad
Komplexní úloha
En translation
	Zaslat komentář k úloze