|
Anonymous3856
|
|
enthusiast
|
|
|
|
|
|
|
Рег.: 30.09.2005
|
|
Сообщений: 352
|
|
|
|
Рейтинг: 76
|
|
Простая задача про графы
01.05.2011 00:09
|
|
|
Есть неориентированный граф. Известно, что есть простой цикл (без повторяющихся вершин), проходящий через первое и второе ребро, есть простой цикл, проходящий через второе и третье ребро. Есть ли простой цикл, проходящий через первое и третье ребро?
|
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
|
Здесь была лажа
Редактировал FMX (02.05.2011 10:25)
|
|
|
Anonymous3856
|
|
enthusiast
|
|
|
|
|
|
|
Рег.: 30.09.2005
|
|
Сообщений: 352
|
|
|
|
Рейтинг: 76
|
|
Re: Простая задача про графы
[re: FMX]
01.05.2011 09:47
|
|
|
Может приведешь свой контр пример, чтобы мы показали где у тебя ошибка?
|
|
|
altal
|
|
|
|
|
|
|
|
|
Рег.: 12.01.2003
|
|
Сообщений: 5640
|
|
|
|
Рейтинг: 2904
|
|
|
В ответ на:
Может приведешь свой контр пример, чтобы мы показали где у тебя ошибка?
И много вас там решают эту тривиальную задачу?
|
Уставать по жизни бог дал долю мою.
И я, как положено, устаю. |
|
|
Pooh
|
|
|
|
|
|
|
|
|
Рег.: 23.10.2003
|
|
Сообщений: 5399
|
|
|
|
Рейтинг: 3869
|
|
|
А теорему Менгера проходят на дискре?
|
|
|
FrauSoboleva
|
|
Don't Quixote
|
|
|
|
|
|
|
Рег.: 20.11.2004
|
|
Сообщений: 28501
|
|
|
|
Рейтинг: 9798
|
|
|
Сейчас я где-нибудь ошибусь, наверное, но попробую 
Рассмотрим эти два цикла. Будем считать что они элементарные. Выкинем остальной граф. Будем считать, что полученное и есть начальный граф. Если циклы не пересекаются кроме как по второму ребру, то искомый цикл очевиден. Если оба содержат первое или третье ребро, то тоже.
Пусть ситуация обстоит не так. Заменим наш граф на другой, в котором каждый участок одного из циклов без пересечений с другим циклом заменим на одно ребро. Получится индуцированные 1 и 3 ребра, причем они различны. Ребро 1 где-то пристыковывается ко второму циклу, деля его на два подграфа. Выкинем подграф, не содержащий ребра 3, к содержащему приделаем ребро 1. Получим цикл, простой, поскольку мы к куску простого цикла приделали ребро.
|
How much wood would woodchuck chuck, if a woodchuck could chuck wood |
|
|
Pooh
|
|
|
|
|
|
|
|
|
Рег.: 23.10.2003
|
|
Сообщений: 5399
|
|
|
|
Рейтинг: 3869
|
|
|
Действительно просто. Даже оговорка В ответ на:
Если циклы не пересекаются кроме как по второму ребру, то искомый цикл очевиден. Если оба содержат первое или третье ребро, то тоже.
не нужна.
А я порисовал картинки, начал рассуждения про точки пересечения циклов и забил, подумал, что надо 2-связностью 1-ого и 2-ого, 2-ого и 3-ого, а, значит, 1-ого и 3-ого пользоваться.
|
|
|
altal
|
|
|
|
|
|
|
|
|
Рег.: 12.01.2003
|
|
Сообщений: 5640
|
|
|
|
Рейтинг: 2904
|
|
Re: Простая задача про графы
[re: Pooh]
01.05.2011 14:08
|
|
|
Пусть цикл, содержащий ребра 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, но без лишних индуцирований.
Было бы неплохо тем, кто постит задачи, немного самим подумать над их решением.
|
Уставать по жизни бог дал долю мою.
И я, как положено, устаю. |
|
|
Anonymous3856
|
|
enthusiast
|
|
|
|
|
|
|
Рег.: 30.09.2005
|
|
Сообщений: 352
|
|
|
|
Рейтинг: 76
|
|
Re: Простая задача про графы
[re: altal]
01.05.2011 20:03
|
|
|
Quote:
Было бы неплохо тем, кто постит задачи, немного самим подумать над их решением.
А ты не сомневайся, я подумал. Задача на мой взгляд интересная и те, кто над ней подумал, не потеряли время зря. Не понимаю твоих претензий.
|
|
Список
Плоский
Дерево
