Простая задача про графы

Gugumot

Есть неориентированный граф. Известно, что есть простой цикл (без повторяющихся вершин проходящий через первое и второе ребро, есть простой цикл, проходящий через второе и третье ребро. Есть ли простой цикл, проходящий через первое и третье ребро?

Lokomotiv59

Здесь была лажа

Gugumot

Может приведешь свой контр пример, чтобы мы показали где у тебя ошибка?

Xephon

 
Может приведешь свой контр пример, чтобы мы показали где у тебя ошибка?

И много вас там решают эту тривиальную задачу?

filippov2005

А теорему Менгера проходят на дискре?

griz_a

Сейчас я где-нибудь ошибусь, наверное, но попробую :)
Рассмотрим эти два цикла. Будем считать что они элементарные. Выкинем остальной граф. Будем считать, что полученное и есть начальный граф. Если циклы не пересекаются кроме как по второму ребру, то искомый цикл очевиден. Если оба содержат первое или третье ребро, то тоже.
Пусть ситуация обстоит не так. Заменим наш граф на другой, в котором каждый участок одного из циклов без пересечений с другим циклом заменим на одно ребро. Получится индуцированные 1 и 3 ребра, причем они различны. Ребро 1 где-то пристыковывается ко второму циклу, деля его на два подграфа. Выкинем подграф, не содержащий ребра 3, к содержащему приделаем ребро 1. Получим цикл, простой, поскольку мы к куску простого цикла приделали ребро.

filippov2005

Действительно просто. Даже оговорка
Если циклы не пересекаются кроме как по второму ребру, то искомый цикл очевиден. Если оба содержат первое или третье ребро, то тоже.
не нужна.
 А я порисовал картинки, начал рассуждения про точки пересечения циклов и забил, подумал, что надо 2-связностью 1-ого и 2-ого, 2-ого и 3-ого, а, значит, 1-ого и 3-ого пользоваться.

Xephon

Пусть цикл, содержащий рёбра 1,2 называется A и пусть цикл, содержащий рёбра 2,3 называется B.
Циклы A,B будут пересекаться (как минимум по ребру 2).
Если ребро 3 лежит в цикле A, то он будет искомым.
Иначе действует так: начиная от ребра 3, будем идти по циклу B в две стороны — до пересечения с циклом A. Получим две точки пересечения: X,Y.
Тогда искомым циклом будет объединение двух дуг:
1) дуги цикла B от т.X до т.Y — по которой мы ходили
2) одной из двух дуг цикла A, соединяющей т.X с т.Y — нужна та дуга, которая содержит ребро 1.

P.S. примерно так же, как и у Frau, но без лишних индуцирований.
Было бы неплохо тем, кто постит задачи, немного самим подумать над их решением.

Gugumot

Было бы неплохо тем, кто постит задачи, немного самим подумать над их решением.
А ты не сомневайся, я подумал. Задача на мой взгляд интересная и те, кто над ней подумал, не потеряли время зря. Не понимаю твоих претензий.
Оставить комментарий
Имя или ник:
Комментарий: