Filtr seznamu úloh?

Zvolte požadované hodnoty úrovní a požadované štítky. V obsahu budou zobrazeny pouze úlohy mající jednu ze zvolených úrovní každé škály a alespoň jeden štítek. Pokud chcete filtrovat pouze podle některých škál nebo jen podle štítků, nechte ostatní skupiny prázdné.

Škály

Obtížnost

Štítky

Typ úlohy
«
«
«

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 T0,v,T1,v,T2. Pokud úsek T1 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