Vyvážená orientace

Úloha číslo: 4314

Mějme neorientovaný graf, jehož všechny vrcholy mají sudé stupně. Dokažte, že je možné hrany zorientovat tak, aby se v každém vrcholu vstupní stupeň rovnal výstupnímu.
  • Řešení

    Bez újmy na obecnosti je graf souvislý (jinak zpracujeme každou komponentu zvlášť). Podle věty o charakterizaci eulerovskych tahů v souvislém grafu se sudými stupni existuje uzavřený eulerovský tah. Stačí projít tah v jednom z možných směrů a zorientovat hrany tak, jak jimi tah prochází.
Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha řešená úvahou
Úloha na dokazování, ověřování
	Zaslat komentář k úloze