(Навеяно задачей "Пересечь все отрезки")

Пусть в некотором графе существует путь Эйлера, причём из каждой вершины выходит чётное число рёбер.
Будем считать, что путь проходит через вершину х

1 3
\ /
х
/ \
2 4

в порядке (1,2) и (3,4), не самопересекающийся, иначе (например, (1,4) и (2,3)) — самопересекающийся.

Можно ли любой такой путь с чётными вершинами построить без самопересечений?
(И почему можно? )

Привет, mrhru!

M>Пусть в некотором графе существует путь Эйлера, причём из каждой вершины выходит чётное число рёбер.
M>Будем считать, что путь проходит через вершину х
M>

M> 1 3
M> \ /
M> х
M> / \
M> 2 4

M>в порядке (1,2) и (3,4), не самопересекающийся, иначе (например, (1,4) и (2,3)) — самопересекающийся.
M>Можно ли любой такой путь с чётными вершинами построить без самопересечений?
M>(И почему можно? )

Если путь идет, например, как (1,4), а потом (2,3), то ветку (4,2) меняем на (2,4), т.е. идем по ней в обратном направлении. Аналогично для б`ольших значений. Если мы пойдем по пути, то рано или поздно прийдем в одно из "соседних" ответвлений из данной вершины. Заворачиваем путь в обратную сторону. Делаем так для всех вершин...

Здравствуйте, mrhru, Вы писали:

M>(Навеяно задачей "Пересечь все отрезки")

M>Пусть в некотором графе существует путь Эйлера, причём из каждой вершины выходит чётное число рёбер.
M>Будем считать, что путь проходит через вершину х
M>

M> 1 3
M> \ /
M> х
M> / \
M> 2 4

M>в порядке (1,2) и (3,4), не самопересекающийся, иначе (например, (1,4) и (2,3)) — самопересекающийся.

M>Можно ли любой такой путь с чётными вершинами построить без самопересечений?
M>(И почему можно? )

Можно. Пусть у нас имеется такое самопересечение. (1, x, 4) — (4 .... 2) — (2, x, 3). развернем путь так: (1, x, 2) — (2 .... 4) — (4, x, 3), это не повлияет на другие самопересечения (меняем только направление обхода кусочка цикла). Повторив достаточное количество раз, получим путь без самопересечений.

Здравствуйте, Apapa, Вы писали:

...

A>Если путь идет, например, как (1,4), а потом (2,3), то ветку (4,2) меняем на (2,4), т.е. идем по ней в обратном направлении. Аналогично для б`ольших значений. Если мы пойдем по пути, то рано или поздно прийдем в одно из "соседних" ответвлений из данной вершины. Заворачиваем путь в обратную сторону. Делаем так для всех вершин...



И это, и решения m.a.g — правильные и совпадают!

У меня вышло чуть длиннее, но было связанным с алгоритмом построения такого пути.
Надо было в задачу вставить.
(Приведенные ответы его не дают)

Но тем не менее:

Каков алгоритм построения пути Эйлера без самопересечений.

Здравствуйте, mrhru, Вы писали:

M>Каков алгоритм построения пути Эйлера без самопересечений.

Берем обычный алгоритм построения Эйлерова цикла на двух стеках и модифицируем его следующим образом:
когда мы нашли цикл, то в цикл вставляем не просто вытолкнутые из стека вершины, а при необходимости переворачиваем.

Здравствуйте, m.a.g., Вы писали:

MAG>Здравствуйте, mrhru, Вы писали:

M>>Каков алгоритм построения пути Эйлера без самопересечений.

MAG>Берем обычный алгоритм построения Эйлерова цикла на двух стеках и модифицируем его следующим образом:
MAG>когда мы нашли цикл, то в цикл вставляем не просто вытолкнутые из стека вершины, а при необходимости переворачиваем.

Понятно (почти ), спасибо. А можно узнать по-подробнее о "обычный алгоритм построения Эйлерова цикла на двух стеках"

Здравствуйте, mrhru, Вы писали:

M>Здравствуйте, m.a.g., Вы писали:

MAG>>Здравствуйте, mrhru, Вы писали:

M>>>Каков алгоритм построения пути Эйлера без самопересечений.

MAG>>Берем обычный алгоритм построения Эйлерова цикла на двух стеках и модифицируем его следующим образом:
MAG>>когда мы нашли цикл, то в цикл вставляем не просто вытолкнутые из стека вершины, а при необходимости переворачиваем.

M>Понятно (почти ), спасибо. А можно узнать по-подробнее о "обычный алгоритм построения Эйлерова цикла на двух стеках"

Описан, например, здесь.

Здравствуйте, mrhru, Вы писали:

M>Можно ли любой такой путь с чётными вершинами построить без самопересечений?
M>(И почему можно? )

Да, можно. И вот как.



Раскрасим плоскость, на которую нанесен граф, в 2 цвета(*).
Внешняя территория — белая, граничные территории — черные, и так далее.

(*) Почему можно покрасить в 2 цвета: из-за того, что в каждом углу сходится четное число границ (т.е. ребер графа).

Теперь исключим из внимания белые территории. При этом сами границы мы не удалили.

Очевидно, что путь обхода графа — это путь обхода всех границ всех черных территорий.

Черные территории соприкасаются углами. Значит, нужно каждый стык либо расцепить, либо оставить в покое (для стыков из 3 и более территорий — можно частично расцепить).

В центре каждой черной территории поставим точку. Это будут вершины нового графа.
Соединим точки ребрами, проходящими через стыки.
Построим дерево, удовлетворяющее этим потребностям (очевидно, это легко сделать: у нас нет изолированных территорий — так уж мы раскрасили граф).

Теперь оставим стыки, соответствующие ребрам дерева, а остальные — расцепим.

Вот мы и получили то, что хотели.
Во-первых: путь, лежащий в плоскости и без самопересечений,
Во-вторых: обходящий все территории по всем границам, а следовательно, задействующий все ребра исходного графа.
Вуаля.

Здравствуйте, Кодт, Вы писали:

...



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