Eulerovský graf a sjednocení kružnic

Úloha číslo: 3626

Dokažte, že hrany každého eulerovského grafu lze rozložit na disjunktní sjednocení kružnic.

Je rozklad jednoznačný? Pokud ne, je počet kružnic v rozkladu dán jednoznačně?

  • Řešení

    Indukcí: Eulerovský graf má uzavřený eulerovský tah. Pokud za \(C\) zvolíme nejkratší část tahu mezi dvěma výskyty stejného vrcholu, potom hrany \(C\) určují kružnici.

    Graf \(G-C\) je eulerovský, tedy z indukčního předpokladu je disjunktním sjednocením kružnic. Přidáním \(C\) do tohoto sjednocení dostaneme všechny hrany \(G\).

    Rozklad ani počet kružnic nejsou dány jednoznačně, např. \(K_5\) lze rozložit na dva pěticykly nebo na dva trojúhelníky a čtyřcyklus.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha řešená úvahou
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze