В Волшебном лесу лесные жители между некоторыми деревьями протоптали тропинки. Оказалось, что у каждого дерева встречаются ровно по три тропинки. Однажды Винни Пух вышел из своего домика, что находился под деревом, и пошёл по одной из тропинок. Дойдя по тропинке до первого встречного дерева, Винни повернул налево, затем, дойдя до следующего дерева, повернул направо, затем снова налево и так далее... Докажите, что когда-нибудь Винни Пух вернётся домой.

Предыдущий
вопрос Следующий
вопрос

Да, Винни Пух обязательно вернется домой. Для этого рассмотрим каждое посещенное дерево как вершину графа, а каждую тропинку как ребро. Так как у каждого дерева три тропинки, то каждая вершина в графе будет иметь степень 3.

Таким образом, так как каждая вершина имеет степень 3, то граф является эйлеровым, что означает, что он содержит эйлеров цикл. Эйлеров цикл - это цикл, который проходит по каждому ребру в графе ровно один раз.

Таким образом, Винни Пух, следуя по тропинкам, образует эйлеров цикл, и в конечном итоге обязательно вернется домой, так как он пройдет по каждой тропинке ровно один раз.