Задачка по теории графов

Mailer

http://mms.blog.ru/440081.html
правда ли что эта игра не имеет решения?
подскажите плз где можно док-во в посмотреть

Lokomotiv59

Достаточно убедиться, что формула Эйлера не выполняется.

seregaohota

В любом учебнике по теории графов про планарность графов. AFAIR Граф не планарен тогда и только тогда, когда он содержит подграфы G_{3,3} (что у тебя на картинке когда 3 вершины соединены с каждой из 3 других) или G_5 (звезда в окружности).
Так что та задача не имеет решения.

Mailer

благодарю!

Slamchek

Кажется, там то ли через колодец, то ли через что-то ещё можно мостик проложить. :-) Так что решается.

Lokomotiv59

Граф не планарен тогда и только тогда, когда он содержит подграфы G_{3,3}
неправда
Граф не планарен, тогда и только тогда, когда не содержит подграфов, гомеоморфных K_5 и K_33.
А вообще — все гораздо проще — нафиг китерий Куратовского, тем более, что его доказательство все равно ссылается на непланарность этих графов. А доказательство непланарности --- подстановка в формулу Эйлера:
для всякого планарного графа: В - Р + Г = 2,
В — кол-во вершин,
Р — кол-во ребер,
Г — кол-во граней (то есть соединенных в цикл вершин, так, что никакие две несоседние вершины не соединены ребром).

Lokomotiv59

Разные есть точки зрения на этот вопрос.

stm7543347

Я так понимаю, форма игры выбрана с целью: "А вот прикольно будет, если у кого-нибудь получится..."

Zag2t

Прошел! Гы Там же дома и колодца не точки Причем через них можно провести линию…

Sander

Круто,
теперь я тоже смог пройти, а ведь часа полтора бился!

toxin

Пришлось поставить масштаб 20% - иначе скорости мышки не хватало... Но в соседней головоломке похоже уже от математической неразрешимости не уйти.

a101

Обманываешь

От огня должны быть другого цвета. Красный - это как раз ошибочный путь

griz_a

не понял, как через них провести линию

Sander

Обманываешь
понятное дело
Оставить комментарий
Имя или ник:
Комментарий: