Задача о трёх колодцах: доказательство через теорию графов

Задача о трёх колодцах - одна из самых известных головоломок теории графов: есть три дома и три колодца (в другой версии - вода, газ и электричество), и от каждого дома нужно провести дорожку к каждому колодцу так, чтобы никакие две дорожки не пересекались. Сколько ни крути расположение точек, девятую дорожку провести без пересечения не получится - и это не отсутствие фантазии, а строгий математический факт. Ниже разберём, как задача сводится к графу, который в теории графов называют $K_{3,3}$, как формула Эйлера для плоских графов доказывает невозможность такого чертежа и почему тот же приём работает для целого класса похожих задач. Прежде чем читать доказательство, поэкспериментируйте с калькулятором ниже: он показывает, при каком числе домов и колодцев граф ещё можно нарисовать без пересечений, а при каком - уже нет.

Как формулируется задача о трёх колодцах

Условие звучит обманчиво просто. На плоскости отмечены три точки - дома $A$, $B$, $C$ - и три точки - колодцы $1$, $2$, $3$. Нужно соединить каждый дом с каждым колодцем непрерывной линией так, чтобы ни одна пара линий не пересекалась, и линии не проходили через чужие дома или колодцы. Всего нужно провести $3 \times 3 = 9$ дорожек. Первые восемь провести без пересечений действительно можно - как бы вы ни расставили точки, найдётся способ. А вот девятая всегда упирается в уже занятую территорию: любая попытка обойти существующие линии заводит дорожку в область, окружённую другими дорожками, откуда до нужного колодца не добраться, не пересекая границу.

Интуитивно кажется, что дело в неудачном расположении точек, и стоит попробовать другую конфигурацию. Но это не так: результат не зависит ни от расположения домов и колодцев, ни от формы дорожек - прямые линии, дуги, ломаные не меняют исход. Чтобы понять почему, задачу нужно перевести с языка геометрии на язык теории графов, где расположение точек вообще перестаёт иметь значение.

От дорожек к графу: рёбра, вершины и K3,3

В теории графов дом или колодец становится вершиной, а дорожка между ними - ребром. Дома и колодцы образуют две группы вершин, при этом рёбра идут только между группами: дом не соединяется с домом, колодец - с колодцем. Такой граф называется двудольным, а если каждая вершина одной доли соединена с каждой вершиной другой, то это полный двудольный граф, обозначаемый $K_{m,n}$, где $m$ и $n$ - размеры долей. Задача о трёх колодцах - это в точности вопрос о том, можно ли нарисовать граф $K_{3,3}$ на плоскости так, чтобы рёбра не пересекались нигде, кроме как в вершинах. Граф, который можно так нарисовать, называется планарным.

У $K_{3,3}$ шесть вершин ($V = 6$) и девять рёбер ($E = 9$) - каждая из трёх вершин одной доли соединена с каждой из трёх вершин другой. Важное свойство двудольного графа: в нём нет циклов нечётной длины, а значит, нет и треугольников - самый короткий цикл состоит минимум из четырёх рёбер. Эта величина называется обхватом графа ($g$), и именно она входит в доказательство.

Формула Эйлера для плоских графов

Ключевой инструмент доказательства - формула Эйлера для связного плоского графа: если у графа $V$ вершин, $E$ рёбер и он разбивает плоскость на $F$ граней (включая внешнюю, бесконечную грань), то

$V - E + F = 2.$

Дальше нужен один геометрический факт: каждая грань плоского чертежа ограничена не менее чем $g$ рёбрами, где $g$ - обхват графа, а каждое ребро отделяет ровно две соседние грани. Значит, если просуммировать число рёбер по границе всех граней, получится не меньше $g \cdot F$, но при этом каждое ребро посчитано дважды - по разу для каждой из двух граней, которые оно разделяет:

$2E \ge g \, F \quad\Longrightarrow\quad F \le \frac{2E}{g}.$

Рассчитать для своей задачи

Подставив эту оценку в формулу Эйлера, $F = E - V + 2 \le \dfrac{2E}{g}$, и выразив $E$, получаем главное неравенство - необходимое условие планарности:

$E \;\le\; \frac{g}{g-2}\,(V-2).$

Для двудольных графов без треугольников обхват $g = 4$, и неравенство упрощается до $E \le 2V - 4$. Для произвольных графов, где могут быть треугольники, обхват $g = 3$, и граница строже: $E \le 3V - 6$. Это неравенство - необходимое, но не достаточное условие: если оно нарушено, граф точно непланарен, но выполнение неравенства само по себе планарность не гарантирует. Для $K_{3,3}$ и $K_5$, впрочем, разбираться в тонкостях достаточности не нужно - неравенство нарушается напрямую.

Почему K3,3 нельзя нарисовать без пересечений

Подставим числа графа $K_{3,3}$: вершин $V = 6$, обхват $g = 4$, значит граница планарности

$E \le 2V - 4 = 2 \cdot 6 - 4 = 8.$

А фактическое число рёбер у $K_{3,3}$ равно $E = 9$. Девять больше восьми, неравенство нарушено - значит, $K_{3,3}$ непланарен, и никакая укладка на плоскости без пересечений невозможна. Это и есть строгое доказательство того, что три дома нельзя соединить с тремя колодцами девятью непересекающимися дорожками, независимо от их расположения.

Можно посмотреть на то же противоречие через грани. Если бы граф был плоским, формула Эйлера потребовала бы $F = E - V + 2 = 9 - 6 + 2 = 5$ граней. Но при обхвате $4$ и девяти рёбрах граней не может быть больше, чем $\lfloor 2E/g \rfloor = \lfloor 18/4 \rfloor = 4$. Формуле нужно пять граней, а обхват допускает не больше четырёх - противоречие, из которого и следует непланарность.

Планарный пример без пересечений: K2,3 и формула Эйлера

Чтобы увидеть, что происходит в пограничном, планарном случае, полезно взять граф чуть меньше - $K_{2,3}$ (две вершины в одной доле, три в другой). У него $V = 5$ вершин и $E = 6$ рёбер, граница планарности $2V - 4 = 6$ - ровно совпадает с числом рёбер. Это означает, что граф укладывается на плоскости впритык к пределу, и формула Эйлера выполняется точно: $F = E - V + 2 = 6 - 5 + 2 = 3$ грани, и при обхвате 4 ровно $2E/g = 12/4 = 3$ - граница достигается без остатка.

Рассчитать для своей задачи

На этом чертеже видно, почему $K_{2,3}$ ещё держится на плоскости, а $K_{3,3}$ - уже нет: у $K_{2,3}$ ровно столько рёбер, сколько допускает предел, а у $K_{3,3}$ на одно ребро больше, чем предел позволяет. Разница в одно-единственное ребро - и чертёж становится геометрически невозможным.

Теорема Куратовского и обобщение на K5

Тот же приём с формулой Эйлера работает не только для двудольных графов. Возьмём полный граф $K_n$, в котором каждая из $n$ вершин соединена с каждой другой - циклы длины 3 (треугольники) здесь есть, поэтому обхват $g = 3$ и граница строже: $E \le 3V - 6$. Для $K_5$ вершин $V = 5$, рёбер $E = \binom{5}{2} = 10$, а граница $3 \cdot 5 - 6 = 9$. Десять больше девяти - $K_5$ тоже непланарен.

Рассчитать для своей задачи

$K_{3,3}$ и $K_5$ - не просто два отдельных примера, а, по теореме Куратовского, единственные два «неделимых» источника непланарности: любой непланарный граф обязательно содержит внутри себя копию одного из них (с точностью до подразбиения рёбер лишними вершинами). Поэтому задача о трёх колодцах - не курьёз, а частный случай общей теоремы о строении плоских графов.

Частые ошибки

• Пытаться найти «правильное» расположение точек. Непланарность $K_{3,3}$ не зависит от координат домов и колодцев и от формы линий - это топологическое свойство графа, а не геометрической картинки.
• Забывать про обхват при подстановке в формулу. Граница $E \le 2V - 4$ верна только для графов без треугольников (обхват 4 и больше); для произвольных графов нужно использовать $E \le 3V - 6$, иначе оценка получится неверной.
• Считать неравенство достаточным условием планарности. Если $E \le 2V - 4$ (или $E \le 3V - 6$) выполняется, это не доказывает планарность - оно лишь не опровергает её. Доказывать планарность нужно явной укладкой или другими критериями.
• Путать вершины и рёбра при подсчёте. Для $K_{m,n}$ вершин $V = m + n$, а рёбер $E = m \cdot n$ - потеря этого различия приводит к неверным числам в формуле Эйлера.
• Забывать про внешнюю грань. В формуле Эйлера $F$ включает и бесконечную внешнюю грань - её пропуск на единицу сдвигает весь расчёт.

FAQ

Почему нельзя провести девятую дорожку, если первые восемь получились без пересечений? Потому что восемь рёбер $K_{3,3}$ ещё укладываются в границу $E \le 8$, а девятое ребро её нарушает: после восьми рёбер плоскость уже разбита на грани так, что оставшаяся пара дом-колодец обязательно оказывается по разные стороны какой-то из границ.

Можно ли решить задачу, если разрешить линиям идти не по прямой, а изгибаться? Нет. Планарность - топологическое свойство: непрерывная деформация линий (без разрывов и без прохождения через другие вершины) не меняет, пересекаются рёбра или нет. Форма дорожек не влияет на результат.

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

Коротко

Задача о трёх домах и трёх колодцах сводится к вопросу о планарности графа $K_{3,3}$: шесть вершин, девять рёбер, обхват 4. Формула Эйлера $V - E + F = 2$ вместе с оценкой числа граней через обхват даёт необходимое условие планарности $E \le 2V - 4$ для двудольных графов и $E \le 3V - 6$ для произвольных. У $K_{3,3}$ девять рёбер против границы в восемь, у $K_5$ десять против девяти - оба неравенства нарушены, оба графа непланарны, и по теореме Куратовского это единственные два «неделимых» источника непланарности любого графа.