Kreslení jedním tahem

Úloha číslo: 4113

Dokažte, že každý souvislý eulerovský rovinný graf lze nakreslit do roviny jedním uzavřeným nekřížícím se tahem (tah se může jen ’dotýkat’ ve vrcholech).

  • Řešení

    Uvažme tah \(T\), a v něm dvě po sobě jdoucí návštěvy téhož vrcholu \(v\), pří němž se tah ’kříží’.

    Tah si rozdělíme na úseky \(T_0,v,T_1,v,T_2\). Pokud úsek \(T_1\) projdeme v opačném směru, jedno křížení eliminujeme.

    elimonace křížení

    Takto postupně eliminujeme všechna křížení.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha vyžadující neobvyklý trik nebo nápad
En translation
	Zaslat komentář k úloze