Граф – это не столбчатая диаграмма, а набор точек, соединённых линиями. Точки называют вершинами, линии – рёбрами. Такой рисунок позволяет убрать несущественные подробности и оставить только связи: какие берега соединяет мост, какие города связаны дорогами, какие участки карты соседствуют. Некоторые задачи, которые сейчас лежат в основе компьютерных сетей и маршрутизации, начинались как простые вопросы о прогулке или раскрашивании карты.
| Место | Задача | Что требуется найти |
|---|---|---|
| 5 | Раскраска графа | Минимум цветов без одинаковых у соседей |
| 4 | Гамильтонов цикл | Маршрут через каждую вершину ровно один раз |
| 3 | Задача китайского почтальона | Кратчайший замкнутый маршрут по всем рёбрам |
| 2 | Задача коммивояжёра | Самый короткий круг через заданные города |
| 1 | Семь мостов Кёнигсберга | Возможно ли пройти каждый мост один раз |
5. Раскраска графа
Задача о четырёх цветах начинается с карты: можно ли раскрасить её так, чтобы соседние страны имели разные цвета, используя не больше четырёх красок? Каждую область представляют вершиной, а общую границу двух областей – ребром. Тогда картографическая задача превращается в задачу раскраски вершин графа.
Гипотезу сформулировали в XIX веке, а доказали Кеннет Аппель и Вольфганг Хакен в 1976 году при существенной помощи компьютерных вычислений. Это был поворотный момент в математике: доказательство опиралось на проверку множества конфигураций, неподъёмную для ручного перебора. Задача стоит пятой не из-за малой важности, а потому что её исходный вопрос уже стал теоремой; остальные позиции описывают оптимизацию маршрута или принципиальную возможность пути.
4. Гамильтонов цикл
Гамильтонов цикл проходит через каждую вершину графа ровно один раз и возвращается в начало. Его удобно представить как маршрут, который должен посетить каждый город, не повторяя ни одного. В отличие от задачи о семи мостах, здесь важны вершины – места назначения, а не каждое соединение между ними.
Похожие головоломки обсуждали ещё в XIX веке, в том числе в игре Уильяма Гамильтона «Икосианская игра». Для произвольного графа нет простого универсального способа быстро определить наличие такого цикла; задача относится к классу вычислительно трудных. Она стоит выше раскраски за прямую связь с поиском маршрутов, но ниже двух оптимизационных задач, где нужно не только понять, существует ли маршрут, но и сравнить его длины.
3. Задача китайского почтальона
Почтальону нужно пройти по каждой улице района хотя бы один раз и вернуться в почтовое отделение. На графе улицы становятся рёбрами, а перекрёстки – вершинами. Если все вершины имеют чётное число выходящих рёбер, существует замкнутый маршрут без повторов; если нет, часть улиц придётся пройти повторно. Задача требует подобрать повторные участки так, чтобы общий путь был как можно короче.
В отличие от задачи коммивояжёра, здесь цель – покрыть каждую дорогу, а не посетить каждый город. Это делает модель подходящей для уборки улиц, проверки дорожной разметки и обслуживания коммунальных сетей. Она занимает третье место за практичность и ясное правило решения: сначала граф проверяют на чётность степеней, а затем минимизируют неизбежные возвраты.
2. Задача коммивояжёра
Коммивояжёр должен посетить каждое заданное место ровно один раз и вернуться в начальную точку, выбрав кратчайший маршрут. Города образуют вершины, расстояния между ними – веса рёбер. Число возможных порядков посещения растёт очень быстро с добавлением новых городов, поэтому полный перебор становится непригоден даже для сравнительно небольших наборов.
Эта задача важна для доставки, планирования производства и проектирования микросхем. Не всегда нужен математически идеальный ответ: в больших случаях полезны алгоритмы, быстро находящие маршрут, который достаточно близок к оптимальному. Коммивояжёр выше задачи почтальона по сложности и универсальности формулировки: дороги можно не покрывать все, но порядок посещения целого набора пунктов нужно выбрать среди огромного числа вариантов.
1. Семь мостов Кёнигсберга
В XVIII веке жители Кёнигсберга задавались вопросом, можно ли пройти по городу так, чтобы пересечь каждый из семи мостов ровно один раз. Леонард Эйлер заменил участки суши вершинами, а мосты – рёбрами. Он заметил, что маршрут такого рода возможен лишь при определённых условиях на число мостов, сходящихся в каждой области. В задаче Кёнигсберга четыре вершины имели нечётную степень, поэтому прогулка была невозможна.
Эйлер не просто решил местную головоломку: он показал, что география берега несущественна, если важны только связи. Этот шаг считается началом теории графов. Задача занимает первое место за фундаментальное последствие: она превратила житейский вопрос о прогулке в общий математический язык сетей.
От карты и мостов до почтовых маршрутов графы помогают отделить структуру задачи от её декораций. В одних случаях они отвечают «можно ли?», в других ищут самый короткий или самый дешёвый путь. Именно смена простого рисунка на модель связей сделала теорию графов полезной далеко за пределами математики.