Обход Москвы

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[EUgeneUS]

Ktina в сообщении #1373894 писал(а):

Попытка решения:

Если в графе нечётных вершин нет, можно доказать возможность обхода по индукции.
А вот если нечётные вершины имеются... там будет посложнее.

Если в графе нечетных вершин нет, то существует эйлеров цикл (можно обойти всё по одному разу и вернуться, откуда начали.
Если в графе две нечетные вершины, то существует эйлеров путь (можно обойти всё по одному разу, но начинать надо с одной нечетной вершины, и заканчивать в другой).

Это знают все, кто решал задачи "обведите рисунок, не отрывая карандаша от бумаги", которые публиковались в журнале "Пионер".

Пусть есть граф $G$, который "нужно обойти ровно два раза".
Построим граф $G'$, путем удвоения ребер графа $G$:
а) каждой вершине графа $G$, соответствует ровно одна вершина графа $G'$
б) каждому ребру графа $G$, соответствует два ребра графа $G'$, соединяющие соответствующие вершины.

Тогда обойдя все вершины графа $G'$ по одному разу, мы получим путь, которым можно обойти граф $G$ пройдя по каждому ребру два раза - по построению $G'$.
Внимание вопрос, сколько нечетных вершин в графе $G'$?

[wrest]

(Ktina, читать только после усвоения предыдущего поста)

Ktina в сообщении #1373894 писал(а):

А вот если нечётные вершины имеются... там будет посложнее.

Для шестиклассников объясняют так: представим каждое ребро как два. Тогда все вершины станут заведомо четными и на графе обязательно появится эйлеровский цикл. Тогда обходим по нему наш граф два раза -- задача решена ;)

[EUgeneUS]

wrest

(Кстати)

Если применить теорему Эйлера для ориентированных графов, то так же легко доказывается, что не только любой связный граф можно "обойти два раза", но так "обойти два раза", что каждое ребро будет пройдено в обоих направлениях.