Интересная головоломка

[|kerish|]

На приложенной картинке нарисовано 3 дома и 3 станции (газ,свет,вода).
Проведите линиями (какими угодно, хоть в окружную, хоть как) газ,свет и воду в каждый дом.
Линии не должны пересекаться!

[A.A.Z.]

Нельзя.

[Создатель]

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

[tyomitch]

Нельзя.

А мы даже доказательство этого факта в эту сессию сдавали

[BV]

У меня не получается. Один дом без света остаётся...

[A.A.Z.]

Код: Выделить всё

     3.7 Дома и трубы

     Q:  Не  выходя  из плоскости, соедините каждый дом  с источниками
воды (1), газа(2) и нефти(3) так, чтобы трубы не пресекались между собой.
Передвигать ничего нельзя.

     /_\ /_\ /_\
     |_| |_| |_|

      _   _   _
     |1| |2| |3|

     A:  Это  невозможно! (см.  теорию графов) Вот более-менее понятное
доказательство:

     Рассмотрим слyчай, когда имеется 3 дома и только 2 вида pесypсов в
2-меpном  пространстве  любое  расположение необходимых 6-ти труб можно
привести к следующему(подобному):

       ------|X|-----
      /              \
     *-------|X|------*
      \              /
       ------|X|-----

     в  любом  случае, при  любом  расположении  один дом (на  рис. - в
середине) будет "блокирован" и, если будет необходимо добавить еще один
ресурс,  то  средний дом останется без этого ресурса (в отличие от двух
остальных домов.
     * Примечание ОП: Конкретно в теории графов надо смотреть теорему
Понтрягина - Куратовского.

Вот, даже доказательство не поленился найти

[tyomitch]

3.7 Дома и трубы

Q: Не выходя из плоскости, соедините каждый дом с источниками
воды (1), газа(2) и нефти(3) так, чтобы трубы не пресекались между собой.
Передвигать ничего нельзя.

Код: Выделить всё

     /_\ /_\ /_\
     |_| |_| |_|

      _   _   _
     |1| |2| |3|


A: Это невозможно! (см. теорию графов) Вот более-менее понятное
доказательство:

Рассмотрим слyчай, когда имеется 3 дома и только 2 вида pесypсов в
2-меpном пространстве любое расположение необходимых 6-ти труб можно
привести к следующему(подобному):

Код: Выделить всё


       ------|X|-----
      /              \
     *-------|X|------*
      \              /
       ------|X|-----


в любом случае, при любом расположении один дом (на рис. - в
середине) будет "блокирован" и, если будет необходимо добавить еще один
ресурс, то средний дом останется без этого ресурса (в отличие от двух
остальных домов.
* Примечание ОП: Конкретно в теории графов надо смотреть теорему
Понтрягина - Куратовского.

Вот, даже доказательство не поленился найти

Подчёркнутое утверждение мне не кажется очевидным.

[tyomitch]

Вот строгое доказательство, которое мы сдавали:

(Обозначим буквами В, Р, Г числа вершин, рёбер, граней соответственно)

1. Есть Т.Эйлера о многогранниках: В + Г = Р + 2.
Она справедлива для связных плоских графов и легко доказывается для них индукцией по рёбрам от остовного дерева.

2. Сосчитаем рёбра графа: каждая грань - 3-или-более-угольник; поэтому каждая грань задаёт ≥3Г рёбер. При этом каждое ребро будет посчитано дважды - в гранях по одну и по другую свою сторону. Получаем 2Р ≥3Г.

3. Подставляем равенство Эйлера в полученное неравенство: имеем 2Р ≥3(Р + 2 - В) = 3Р + 6 - 3В, т.е. Р ≤ 3В - 6.

Все полученные пока результаты справедливы для любых связных плоских графов.

4. У графа "три дома - три колодца" В=6, Р=9. Кроме того, любой его цикл имеет чётную длину, т.к. рёбра идут всегда от дома к колодцу. Значит, все его грани - 4-или-более-угольники. Повторяя расчёты из п.п. 2 и 3, получаем 2Р ≥4Г, Р ≥2Г = 2(Р + 2 - В) = 2Р + 4 - 2В, Р ≤ 2В - 4.

5. Подставляем числа вершин и рёбер нашего графа в полученное неравенство: 9 ≤ 2*6 - 4 = 8. Получено противоречие. Следовательно, граф "три дома - три колодца" не м.б. плоским.

6 (бонус). Этой же техникой доказывается, что полный пятивершинник (5 вершин, каждая связана со всеми остальными) не м.б. плоским. У него В=5, Р=10. Подставляя эти числа в неравенство из п.3, имеем 10 ≤ 3*6 - 6 = 9. Получено противоречие.

Т.Понтрягина-Куратовского гораздо сложнее, и утверждает гораздо более сильные вещи. Т.е. в доказательстве AAZ она упомянута имхо зря.

[GSerg]

Тёмыч, не поверишь, но я знал, что придёшь ты и скажешь именно это...