Соедини 6 точек не пересекая линий, Реально? Поделиться Опции

[JKmoto]

Наткнулся в нете на игрушку, так и сяк ее, ни вкакую.
Суть такая - три дома, к ним подключить воду, електроенергию, отопление. Соединяются линиями, линии не могут пересекаться.

Вот интересно - ето реально, или игра стеб?

http://flesh.ru/flesh/game_409.html

[DmT]

была уже на фане такая тема.
Я там вроде как приводил доказательства почему это не возможно. Гугли на тему существования планарного графа. Отвечая на вопрос односложно - нет, не возможно

[A.Vas]

JKmoto,
нет, нереально. Если мне не изменяет память, эту задачу придумал Эйлер, и в оригинале она была про троих друзей, живущих в трёх домах и использующих три колодца - кажется, с водой, с молоком и с маслом.

P.S. Увидев доменное имя сайта flesh.ru, я сначала думал, что сайт посвящён гуро или снаффу. Кто бы мог подумать, что за таким говорящим названием скрывается банальная неграмотность... <_<

[DmT]

http://ru.wikipedia.org/wiki/%D0%9F%D0%BB%...%80%D0%B0%D1%84
Критерий непланарности
необходимое условие — если граф не планарный, то он должен содержать больше 4 вершин, степень которых больше 3, или больше 5 вершин степени больше 2.
А в задаче граф из (3+3) вершин каждая со степенью 3. => граф непланарный.

Сообщение отредактировал DmT - 19.12.2010, 19:33

[ApxuBatop]

за 5 минут прошел!

[Neko-mata]

ApxuBatop,
у тебя в 1 месте точно пересечение есть.. Там где зелёная линия идёт к 3-му дому сквозь 2 оранжевых.

Сообщение отредактировал metallsatanist - 20.12.2010, 5:21

[ApxuBatop]

не, я там в гильбертово пространство вошел, в нем нет пересечений!)))

[..::RUSS::..]

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

Эти ребра образуют на плоскости многоугольник, разделенный на более мелкие многоугольники. Поэтому для этого разбиения должно выполняться соотношение Эйлера В - Р + Г= 1. Добавим к рассматриваемым граням еще одну - внешнюю часть плоскости по отношению к многоугольнику. Тогда соотношение Эйлера примет вид В - Р + Г = 2, причем В = 6 и Р = 9. Следовательно, Г = 5. Каждая из пяти граней имеет по крайней мере четыре ребра, поскольку, по условию задачи, ни одна из дорожек не должна непосредственно соединять два дома или два колодца. Так как каждое ребро лежит ровно в двух гранях, то количество ребер должно быть не меньше (5в€™4)/2 = 10, что противоречит условию, по которому их число равно 9. Полученное противоречие показывает, что ответ в задаче отрицателен - нельзя провести непересекающиеся дорожки от каждого домика к каждому колодцу.