Консультация № 172845
03.10.2009, 04:05
0.00 руб.
0 11 0
Здравствуйте! Столкнулся с такой головоломкой:



Т.е. зачеркнуть все (будем говорить ребра) этого графа в точности по одному разу. Лично я думаю, что именно в этом случае так не получится (может я ошибаюсь). Если это действительно так, то помогите пожалуйста найти закономерность по которой можно будет легко определить можно ли будет зачеркнуть все ребра в точности по одному разу (что-то типа Эйлеров путь). Лично я заметил что если в графе равное количество как парных степеней (т.е. количество ребер которые соприкасаются с вершиной) вершин так и непарных, то точно получится зачеркнуть все ребра в точности по одному разу и заметил, что если количество непарных степеней вершин ровно вдвое больше количества парных - БЕЗРЕЗУЛЬТНО (что именно наблюдается на рисунке). Но опять же, я не на 100% уверен в своих наблюдениях и мне очень нужна Ваша помощь в поиску закономерностей (если данная головоломка действительно не решается).

P.S. Пробовал использовать правила наличия Эйлерового путя (дискретная математика) как цикличного так и НЕТ, но здесь это что-то не срабатывает. Помогите пожалуйста!

Обсуждение

Неизвестный
03.10.2009, 04:08
общий
... хочу заметить, что неважно откуда начинать, начало этого "пути" я выбрал случайно Если кому интересно зачем мне это, то здесь причин две:
1. Собранные данные по этой проблеме будут использоваться в написании программы проверки, а можно ли...
2. Огромный интерес в решении головоломок. Надеюсь на Вашу помощь
давно
Советник
165461
578
03.10.2009, 08:32
общий
Николай // Programmator :
Здравствуйте!

Судя по рисунку, каждое следующее зачеркнутое ребро смежно с предыдущим. Если это так по условию, то задача сводится к поиску гамильтонова пути на дуальном графе.
Неизвестный
03.10.2009, 10:00
общий
Николай // Programmator :
Графом тут нужно считать не саму картинку, а то, что Вы на ней нарисуете. Вершины графа - области, а ребра - пересекающие отрезки. Для каждой области (вершины) нужно посчитать количество границ вокруг нее, которые нужно пересечь. Дальше нужно исследовать четность степеней вершин нового графа (областей). Если все четные - любая может стать началом Эйлерова пути. Если есть 2 нечетные, то одна из них должна стать началом, а другая концом. Если нечетных больше - построить Эйлеров путь не удастся, т.к. во все точки кроме начала и конца нужно прийти И уйти (т.е. нужны 2 ребра, или любое четное количество ребер).
давно
Советник
165461
578
03.10.2009, 12:15
общий
Яна:
Скорее всего, Вы правы - задачу нужно понимать именно так.
Тогда граф можно и не строить. Просто считаем число границ для каждой области. Для рисунка в задаче это будут числа 5, 5, 4, 5, 4, и 9 (для внешней области). Пересечь все границы можно, если нечетных чисел среди них не более двух.
Неизвестный
03.10.2009, 14:51
общий
Lang21:
Выходит эта головоломка не решается, правильно?
давно
Советник
165461
578
03.10.2009, 15:31
общий
А как ее понимать?
Если нужно последовательно проходить из одной области в другую, так, чтобы пересечь все ребра, то решается (см. сообщение Яны и мое дополнение). То есть, есть критерий, но для Вашего рисунка он не выполняется.
Если нужно последовательно зачеркивать смежные ребра, то однозначного критерия нет, вроде бы. Тогда можно посмотреть теоремы о гамильтоновых графах и алгоритмы поиска гамильтонова пути.
Неизвестный
03.10.2009, 17:11
общий
Lang21:
Нужно зачеркивать чтобы (как Вы написали ранее) каждое следующее ребро было смежно с пердыдущим... Меня интересует, подходит ли для данного критерия правило, что среди чисел количества границ для каждой области должно быть не больше двух нечетных чисел? И почему именно не больше двух?
Неизвестный
03.10.2009, 17:23
общий
Можно оттолкнуться от следующего.
Имеем фигуру. У нее - N сторон. Когда мы их зачеркиваем, то последовательно то входим, то выходим из прямоугольника. Если сторон четное количество, то мы останемся после вычеркивания всех сторон там же, где и были (то есть или внутри или снаружи фигуры). Если сторон, которые надо вычеркнуть, нечетное количество, то, если мы начали снаружи - останемся внутри, если начали изнутри - окажемся снаружи фигуры...
Следовательно, если мы имеем в фигуре две части с нечетным количеством сторон, то, начиная из первой, можем остаться во второй...
Если их больше, то решения точно не будет. В данном случае таких фигур три...
Мне так кажется...
Неизвестный
03.10.2009, 17:43
общий
Всем большое спасибо! Вы мне очень помогли
Неизвестный
08.10.2009, 19:42
общий
Вы правы данная задача неразрешима, это одна из интерпретаций задачи Кёнигсбергские мосты.
В свою очередь могу Вам предложить такое неполное решение задачи:
Неизвестный
10.10.2009, 16:50
общий
Gh0stik:
Интересное решение, я даже ни сразу заметил, что одна остается незачёркунутой. Спасибо
Форма ответа