Можно ли построить три дома вырыть три колодца

Задача: Три соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу. Дорожки не могут проходить через колодцы и домики рисунок 22

Рисунок. Задача о домиках и колодцах.

Для решения этой задачи воспользуемся теоремой, доказанной Эйлером в 1752 году, которая является одной из основных в теории графов. Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых.

Теорема. Если многоугольник разбит на конечное число многоугольников так, что любые два многоугольника разбиения или не имеют общих точек, или имеют общие вершины, или имеют общие ребра, то имеет место равенство

В — Р + Г = 1, (*)

где В — общее число вершин, Р — общее число ребер, Г — число многоугольников (граней).

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

Действительно, после проведения такой диагонали в новом разбиении будет В вершин, Р+1 ребер и количество многоугольников увеличится на единицу. Следовательно, имеем

В — (Р + 1) + (Г+1) = В — Р + Г.

Пользуясь этим свойством, проведем диагонали, разбивающие входящие многоугольники на треугольники, и для полученного разбиения покажем выполнимость соотношения (*) рисунок 24

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

для удаления треугольника ABC требуется снять два ребра, в нашем случае AB и BC;

для удаления треугольника MKN требуется снять одно ребро, в нашем случае MN.

В обоих случаях равенство (*) не изменится. Например, в первом случае после удаления треугольника граф будет состоять из В-1 вершин, Р-2 ребер и Г-1 многоугольника:

(В — 1) — (Р + 2) + (Г -1) = В — Р + Г.

Продолжая этот процесс удаления треугольников, в конце концов мы придем к разбиению, состоящему из одного треугольника. Для такого разбиения В = 3, Р = 3, Г = 1 и, следовательно,

B — Р + Г= 1.

Значит, равенство (*) имеет место и для исходного разбиения, откуда окончательно получаем, что для данного разбиения многоугольника справедливо соотношение (*).

Заметим, что соотношение Эйлера не зависит от формы многоугольников. Многоугольники можно деформировать, увеличивать, уменьшать или даже искривлять их стороны, лишь бы при этом не происходило разрывов сторон. Соотношение Эйлера при этом не изменится.

Приступим теперь к решению задачи о трех домиках и трех колодцах.

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

Эти ребра образуют на плоскости многоугольник, разделенный на более мелкие многоугольники. Поэтому для этого разбиения должно выполняться соотношение Эйлера

В — Р + Г= 1.

Добавим к рассматриваемым граням еще одну — внешнюю часть плоскости по отношению к многоугольнику. Тогда соотношение Эйлера примет вид

В — Р + Г = 2,

причем В = 6 и Р = 9.

Следовательно, Г = 5. Каждая из пяти граней имеет по крайней мере четыре ребра, поскольку, по условию задачи, ни одна из дорожек не должна непосредственно соединять два дома или два колодца. Так как каждое ребро лежит ровно в двух гранях, то количество ребер должно быть не меньше (5*4)/2 = 10, что противоречит условию, по которому их число равно 9.

Полученное противоречие показывает, что ответ в задаче отрицателен — нельзя провести непересекающиеся дорожки от каждого домика к каждому колодцу.

1. Регистрация:
   25.01.12
   Сообщения:

   97

   Благодарности:
   9

   ЭдСуровый

   Живу здесь

   Регистрация:
   25.01.12
   Сообщения:
   97
   Благодарности:
   9
   Адрес:

   Санкт-Петербург

   Скважина на три дома

   Здравствуйте. Вопрос просчитывается пока в теории. Имеем три дома в ряд. Три хозяина. Между домами по 50 метров. Предлагают сделать скважину для воды. Люди говорят, что глубиной 60-70 метров. Хотим ее сделать на три дома. Выберем место по середине, сделаем скважину, опустим насос, сделаем от него разводку на три дома.(как я думаю просто тройник на трубу ПНД). А как дальше ? У каждого в доме накопительный бачок литров на 50, счетчик воды и коллектор. А если включат два-три дома одновременно краны ? Будет давление ? Или так не делают ? Понятно, что лучше бачок этот сделать общий около скважины и из него уже качать. Но такой возможности нет. Это дома для сезонного проживания, зимой народ появляется наездами. Этот бачок просто замерзнет зимой или сопрут. А так у каждого в доме, под охраной и в тепле. Да еще наверно фильтры нужны будут от какой-нибудь гадости.
   Какие у нас есть варианты ?

2. Регистрация:
   08.07.08
   Сообщения:

   11.443

   Благодарности:
   14.135

   Protasevich

   консультирую помаленьку

   Регистрация:
   08.07.08
   Сообщения:
   11.443
   Благодарности:
   14.135
   Адрес:

   Орел

3. Регистрация:
   25.01.12
   Сообщения:

   97

   Благодарности:
   9

   ЭдСуровый

   Живу здесь

   Регистрация:
   25.01.12
   Сообщения:
   97
   Благодарности:
   9
   Адрес:

   Санкт-Петербург

   Спасибо за наводку, буду изучать.

4. Регистрация:
   08.07.08
   Сообщения:

   11.443

   Благодарности:
   14.135

   Protasevich

   консультирую помаленьку

   Регистрация:
   08.07.08
   Сообщения:
   11.443
   Благодарности:
   14.135
   Адрес:

   Орел

   @ЭдСуровый, попробуйте еще поиском пройтись, такие вопросы поднимались не один раз…

5. Регистрация:
   10.12.13
   Сообщения:

   1.936

   Благодарности:
   1.344

   Kzh77

   Живу здесь

   Регистрация:
   10.12.13
   Сообщения:
   1.936
   Благодарности:
   1.344
   Адрес:

   Россия, Москва

   Это один из лучших способов поссориться с соседями.

   Последнее редактирование модератором: 21.03.14

6. Регистрация:
   25.01.12
   Сообщения:

   97

   Благодарности:
   9

   ЭдСуровый

   Живу здесь

   Регистрация:
   25.01.12
   Сообщения:
   97
   Благодарности:
   9
   Адрес:

   Санкт-Петербург

   Вчера встречался на своей поляне с человеком, который роет колодцы уже 12 лет. Он походил по участку с двумя прутиками в руках и показал два места, где пересекаются две водяные жилы. Глубина 8-9 метров. Предлагает сделать колодец на 10 метровых колец, туда ввести ПНД под землей и ввод в дом. А там уже насосная станция, коллектор, бойлер, водяной резервуар, разводка по дому. По деревне, которая в 1 км от нас, такие колодцы встречаются часто. И все на глубине 9-11 метров. И народ живет и радуется. Может нам так и сделать. Три колодца на три дома. Или один колодец (для эксперимента — есть ли вода, какая, дебит узнать), а остальные делают две скважины на 10 метров и все то-же самое. Дома для сезонного проживания.

7. Регистрация:
   24.03.09
   Сообщения:

   41.605

   Благодарности:
   32.040

   Андрей 203

   Администратор

   Регистрация:
   24.03.09
   Сообщения:
   41.605
   Благодарности:
   32.040
   Адрес:

   Уфа

   @ЭдСуровый, самый антиконфликтный вариант, это обустройство индивидуального колодца для каждого хозяина/дома.

8. Регистрация:
   04.11.10
   Сообщения:

   4.069

   Благодарности:
   1.350

   cantexnik

   Живу здесь

   Регистрация:
   04.11.10
   Сообщения:
   4.069
   Благодарности:
   1.350
   Адрес:

   Ужгород

   Единственный вариант.

9. Регистрация:
   04.04.11
   Сообщения:

   942

   Благодарности:
   206

   servisnik

   Живу здесь

   Регистрация:
   04.04.11
   Сообщения:
   942
   Благодарности:
   206
   Адрес:

   Архангельск

   У меня коллега по работе, решил с соседом по участкам выкопать колодец на двоих.
   Выкопали.
   Было это два года назад. С тех пор даже не здороваются друг с другом.

10. Регистрация:
    25.01.12
    Сообщения:

    97

    Благодарности:
    9

    ЭдСуровый

    Живу здесь

    Регистрация:
    25.01.12
    Сообщения:
    97
    Благодарности:
    9
    Адрес:

    Санкт-Петербург

    Про колодец понятно, там все видно. Вопрос со скважинами. Говорят, что если дом для лета, а зимой наездами, то такая скважина на 10 метрах года за три затянется песком и все, воды нет. Ее уже не прокачать. А что по опыту ? Есть в этом доля правды ? И что можно сделать, чтобы этого избежать.

    Последнее редактирование модератором: 21.11.17

11. Регистрация:
    04.04.11
    Сообщения:

    942

    Благодарности:
    206

    servisnik

    Живу здесь

    Регистрация:
    04.04.11
    Сообщения:
    942
    Благодарности:
    206
    Адрес:

    Архангельск

    Видно Вы еще сами не определились что хотите.

    Если наездами 3 года, то
    Если летом пользоваться, а зимой наездами, то вряд ли.

12. Регистрация:
    25.01.12
    Сообщения:

    97

    Благодарности:
    9

    ЭдСуровый

    Живу здесь

    Регистрация:
    25.01.12
    Сообщения:
    97
    Благодарности:
    9
    Адрес:

    Санкт-Петербург

    Да нет. Вопросы сейчас стоят так:
    1 Вариант. Глубокая скважина 70 (? а может и больше) метров с гарантированным дебитом на три
    дома. Бюджет — от 100 000 руб и выше на каждый дом.
    2 Вариант. По одному колодцу на 10 метров к каждому дому. Бюджет — макс. 100 000 руб на каждый дом.
    3 Вариант. Первый строит колодец за 100 000 руб. Смотрим, все ли нормально (чистота
    воды, глубина, дебит). И тогда остальные два делают просто по скважине, но на 10 метров.
    Бюджет скважины — 50 000 руб. на человека.
    Все цены приведены уже под ключ (насосные станции, трубы ПНД и прочее до коллектора).

    Вот и возникают отсюда вопросы.
    1. По первому варианту — уже практически раздумали делать.
    2. По второму — сомнения вот такого плана. Если три колодца будут сидеть на одной жиле (по 50 метров расстояние друг от друга в один ряд), но на разных перекрестках — вода не будет мигрировать из одного колодца в другой ?
    3. И вопрос по варианту 3 — мелкая скважина не будет забиваться песком, если летом жить по выходным, а зимой наездами (раз в месяц) ?

    Последнее редактирование модератором: 21.03.14

13. Регистрация:
    24.03.09
    Сообщения:

    41.605

    Благодарности:
    32.040

    Андрей 203

    Администратор

    Регистрация:
    24.03.09
    Сообщения:
    41.605
    Благодарности:
    32.040
    Адрес:

    Уфа

    У меня такой 3-х дюймовой скважине почти 40 лет, использование только сезонное, проблем нет. Всё зависит от конкретной гидрологии.

14. Регистрация:
    02.12.13
    Сообщения:

    32

    Благодарности:
    45

    Моя Вода

    Участник

    Регистрация:
    02.12.13
    Сообщения:
    32
    Благодарности:
    45
    Адрес:

    Санкт-Петербург

    Хорошо пробуренная и обсаженная скважина прослужит достаточно долго.
    На прошлой неделе меняли насос в скважине на песок, пробуренной 15 лет назад. Используется сезонно.

    Вопрос: в каком районе дом (а)?

15. Регистрация:
    30.03.13
    Сообщения:

    3.164

    Благодарности:
    2.867

    Сверловщик

    Живу здесь

    Регистрация:
    30.03.13
    Сообщения:
    3.164
    Благодарности:
    2.867
    Адрес:

    поселок городского типа Приволжский

    Верное решение.
    То же самое, что и одна жена на три дома.

Плоские и планарные графы

Граф, который можно начертить на плоскости так, чтобы рёбра его пересекались только в его вершинах, называется планарным графом. Его изображение на плоскости без пересечения рёбер назовём плоским графом. Граф, который не является планарным, называется непланарным. Заметим, что в общем случае рёбра графа могут пересекаться между собой, причём точки пересечения не обязательно являются вершинами графа.

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

Можно также сказать, что граф, изоморфный плоскому графу, называется планарным. Например, все три изоморфных графа (рис.8) Г1 , Г2 , Г3 на следующем рисунке планарные, но только Г2, и Г3 — плоские.

Рис.8

Планарный граф на рис. 9.1 можно изобразить в виде изоморфных плоских графов (рис. 9.2 и рис. 9.3):

Рис.9.1 Рис.9.2 Рис.9.3

Естественно поставить следующий вопрос: всегда ли можно изобразить плоский граф так, чтобы все его рёбра были прямолинейными отрезками? Этот вопрос остаётся открытым.

Задача о трёх домах и трёх колодцах

На одном участке земли были построены три дома и вырыты три колодца для их обитателей.

Природа страны и её климат таковы, что колодцы часто пересыхают, поэтому важно, чтобы от каждого из домов имелся доступ к каждому из трёх колодцев. Спустя некоторое время обитатели домов А, В, и С (рис.10) серьёзно поссорились друг с другом и решили проложить дорожки к трём колодцам а, b, с так, чтобы по пути к колодцам и обратно им не приходилось встречать друг друга.

Рис.10

А возможно ли это? Является ли соответствующий граф плоским, т.е. можно ли провести дорожки так, чтобы они не пересекались нигде, кроме вершин графа А, В, С и а, b, с? С помощью непосредственной проверки легко убедиться, что всегда можно провести 8 тропинок, которые, кроме указанных точек, других точек пересечения иметь не будут, а девятая тропинка обязательно пересечёт хотя бы одну из них. На рис. 4 показан один из возможных вариантов проведения тропинок. Решим эту задачу посредством рассуждений.

От домиков А и С проведём требуемые тропинки. Полученный граф разделит плоскость на области: X , Y , Z.

Легко заметить, что домик В может находиться в одной из этих областей. Рассмотрим каждый случай в отдельности.

1. Если домик В находится в области Z, как изображено на рисунке, то от него невозможно провести тропинку к b, которая не пересекалась бы ни с одной из уже проведённых тропинок.

2. Если домик В находится в области Y , то от него невозможно провести тропинку к объекту а, которая не пересекалась бы ни с одной из уже проведённых.

3. Если домик В находится в области X, то от него невозможно провести тропинку к объекту c, которая не пересекалась бы ни с одной из уже проведённых.

Итак, получается, что граф, выражающий ситуацию данной задачи, плоским быть не может. А это значит, что задача неразрешима.