Здравствуйте, mrhru, Вы писали:
M>Можно ли любой такой путь с чётными вершинами построить без самопересечений? M>(И почему можно? )
Да, можно. И вот как.
Раскрасим плоскость, на которую нанесен граф, в 2 цвета(*).
Внешняя территория — белая, граничные территории — черные, и так далее.
(*) Почему можно покрасить в 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), это не повлияет на другие самопересечения (меняем только направление обхода кусочка цикла). Повторив достаточное количество раз, получим путь без самопересечений.
Здравствуйте, mrhru, Вы писали:
M>Каков алгоритм построения пути Эйлера без самопересечений.
Берем обычный алгоритм построения Эйлерова цикла на двух стеках и модифицируем его следующим образом:
когда мы нашли цикл, то в цикл вставляем не просто вытолкнутые из стека вершины, а при необходимости переворачиваем.
...
A>Если путь идет, например, как (1,4), а потом (2,3), то ветку (4,2) меняем на (2,4), т.е. идем по ней в обратном направлении. Аналогично для б`ольших значений. Если мы пойдем по пути, то рано или поздно прийдем в одно из "соседних" ответвлений из данной вершины. Заворачиваем путь в обратную сторону. Делаем так для всех вершин...
И это, и решения m.a.g — правильные и совпадают!
У меня вышло чуть длиннее, но было связанным с алгоритмом построения такого пути.
Надо было в задачу вставить.
(Приведенные ответы его не дают)
Но тем не менее:
Каков алгоритм построения пути Эйлера без самопересечений.
Здравствуйте, m.a.g., Вы писали:
MAG>Здравствуйте, mrhru, Вы писали:
M>>Каков алгоритм построения пути Эйлера без самопересечений.
MAG>Берем обычный алгоритм построения Эйлерова цикла на двух стеках и модифицируем его следующим образом: MAG>когда мы нашли цикл, то в цикл вставляем не просто вытолкнутые из стека вершины, а при необходимости переворачиваем.
Понятно (почти ), спасибо. А можно узнать по-подробнее о "обычный алгоритм построения Эйлерова цикла на двух стеках"
Здравствуйте, mrhru, Вы писали:
M>Здравствуйте, m.a.g., Вы писали:
MAG>>Здравствуйте, mrhru, Вы писали:
M>>>Каков алгоритм построения пути Эйлера без самопересечений.
MAG>>Берем обычный алгоритм построения Эйлерова цикла на двух стеках и модифицируем его следующим образом: MAG>>когда мы нашли цикл, то в цикл вставляем не просто вытолкнутые из стека вершины, а при необходимости переворачиваем.
M>Понятно (почти ), спасибо. А можно узнать по-подробнее о "обычный алгоритм построения Эйлерова цикла на двух стеках"