Разбор головоломок: графы – фигуры одним росчерком и поиск пути

С давних пор известны и пользуются популярностью головоломки, которые можно объединить под общим названием «одним росчерком». В таких задачах предлагается начертить какую-либо фигуру одним росчерком (одной линией), не отрывая карандаша от бумаги, и не проводя дважды по одной линии. Классическими примерами являются задачи, в которых одним росчерком нужно нарисовать разные варианты конверта или квадрат с диагоналями и четырьмя дугами:

Нарисуйте фигуры одним росчерком, не отрывая карандаша от бумаги, и не проводя по одной линии дважды

Вариантом задачи является поиск пути по дорогам или мостам, который будет проходить по всем дорогам (мостам) ровно по одному разу. Классическим примером является задача о семи кёнигсбергских мостах, которая опубликована на этой неделе под номером 5.

Также известна старая задача о доме из пяти комнат, каждая из которых соединена с другой и с улицей дверьми. Необходимо найти такой путь по комнатам, который проходил бы по всем 16 дверям ровно по одному разу (начинать и заканчивать можно в любой комнате или вне дома):

Соедините все 16 дверей одной линией, не пересекая ни одну из дверей дважды

Независимо от условий задачи (начертить фигуру одной линией или найти непрерывный путь), ее решением является граф – математический объект, объединяющий в себе множество вершин и ребер. Причем как само понятие графа, так и раздел математики, изучающий данные объекты (он назван теорией графов), родились как раз из решения такой задачи. А именно – из решения задачи о семи кёнигсбергских мостах, которой в 1736 году занялся великий математик Леонард Эйлер. Правда, само понятие «граф» было предложено в 1878 году английским математиком Джеймсом Джозефом Сильвестром. Однако «отцом» теории графов по праву считается Эйлер, и здесь мы проследим за некоторыми его рассуждениями.

Правила Эйлера

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

Карте Кёнигсберга преобразуется в граф с четырьмя вершинами

Вот так Эйлер получил граф – абстрактный математический объект, состоящий из вершин, попарно соединенных ребрами. Вершины обозначены здесь красными точками, а ребра – черными линиями. А что за цифры стоят у вершин? О, это – как раз то, что и помогает решать любые (повторяю – любые) задачи о рисовании фигур одним росчерком! Это – обозначение четности/нечетности вершины, которое указывает на число ребер, которое выходит из данной вершины. Если из вершины выходит четное число ребер – значит она четная, а если нечетное – она нечетная. Все очень просто.

В ходе работы над задачей Эйлер вывел несколько заключений, в которых ключевую роль играет четность/нечетность вершин. Мы приведем здесь только те заключения, которые потребуются для решения головоломок:

• Если все вершины графа четные, то его можно начертить одним росчерком, не отрывая карандаша от бумаги. При этом можно начинать с любой вершины графа, а завершаться он будет в этой же точке;
• Если ровно две вершины графа нечетные, то его можно начертит одним росчерком, не отрывая карандаша от бумаги. При этом начать следует с одной из нечетных вершин, а завершать – во второй нечетной вершине;
• Если в графе три и больше нечетных вершин, то его невозможно начертить одним росчерком, не отрывая карандаша от бумаги, и не проводя по одному ребру дважды.

Итак, вновь посмотрим на граф задачи мостов Кёнигсберга: здесь четыре вершины, и все они нечетные. Значит, задача не имеет решения – пройти по всем семи мостам, посетив каждый из них ровно по одному разу, невозможно. Задача становится разрешимой только при добавлении одного моста (что в 1905 году и было сделано в реальности). Это можно сделать подобным образом (дополнительный мост указан пунктирной линией):

При добавлении одного моста задача о мостах Кёнигсберга имеет решение

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

Анализ и решение задач

Теперь проанализируем фигуры, приведенные в начале статьи – конверты и квадрат с дугами:

Преобразование конвертов в графы

Преобразование квадрата с диагоналями и дугами в граф

Как видим, левый конверт содержит ровно две нечетных вершины, значит его можно начертить одним росчерком, причем следует начать и закончить в нижних вершинах. Правый конверт и квадрат с дугами имеют по четыре нечетных вершины, значит начертить их одним росчерком невозможно.

Таким же образом проанализируем задачу о пяти комнатах. Но не будем чертить граф, а только укажем число дверей в каждой комнате – это и будут ребра графа:

Цифры в комнатах - число дверей, а заодно и четность/нечетность вершин графа

Очевидно, что при наличии трех нечетных вершин граф невозможно начертить одной линией, а значит эта задача не имеет решения.

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

Итог: правила решения головоломок «одним росчерком»

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

1. Определить четность/нечетность всех вершин графа;
2. Если все вершины четные – нарисовать фигуру можно, начав с любой вершины;
3. Если две вершины нечетные – нарисовать фигуру можно, но начинать и завершать нужно в этих вершинах;
4. Если три и более вершины нечетные – нарисовать фигуру одним росчерком невозможно.

Теперь вы можете взять любые задачи на рисование фигур одним росчерком (их много в сборниках Дьюдени, Перельмана и других авторов, а также в интернете), и испытать приведенные здесь правила. Также вы можете придумывать подобные задачи самостоятельно, заранее решая, какие из них будут иметь решение, а какие – нет.

Литература

1. Дьюдени Г. Э. 520 головоломок. Сост. и ред. амер. изд. М. Гарднер. Пер. с англ. Ю. Н. Сударева. М.: Мир. – 1975. – 342 с., ил. – с. 154 – 155, 305 – 306.
2. Задача о кенигсбергских мостах // Химия и жизнь. – 2006. - №3. – с. 44 – 45.
3. Энциклопедический словарь юного математика / Сост. А. П. Савин. – М.: Педагогика, 1989. – 352 с.: ил. – с. 85 – 88.
4. Irina Gribkovskaia, Øyvind Halskau sr, Gilbert Laporte. The bridges of Königsberg — A historical perspective // Networks. — 2007. — Т. 49. — С. 199 — 203.