Задача о мостах Кёнигсберга: как родилась теория графов
Жители прусского города придумали себе головоломку: пройти по всем семи мостам, не ступив ни на один дважды. Никто не справился — а потом пришёл Эйлер и доказал, что это невозможно. Так родилась целая наука.
Представь старинный город, разрезанный рекой на четыре куска, и семь мостов, что их сшивают. Горожане спорили: можно ли прогуляться так, чтобы пройти по каждому мосту ровно один раз и ни по одному дважды? Они не знали, что эта прогулка-головоломка скоро взорвёт математику и подарит миру целую новую науку.
Город, разрезанный рекой
В XVIII веке существовал город Кёнигсберг — сегодня это российский Калининград. Через него текла река Прегель, и текла она хитро: огибала остров посреди города, а потом раздваивалась. В итоге суша распадалась на четыре части — два больших берега, остров Кнайпхоф и ещё один кусок земли между рукавами реки.
Чтобы люди не сидели запертыми на своих клочках суши, эти четыре части соединили семью мостами. И вот среди горожан родилась забава, от которой никто не мог отделаться: можно ли пройти по всему городу так, чтобы пересечь каждый мост ровно один раз — и ни один не перейти дважды?
Звучит просто, правда? Бери и иди. Люди пробовали снова и снова — в выходные, после работы, споря в трактирах. Кто-то клялся, что почти получилось. Но «почти» не считается: каждый раз оставался один непройденный мост или приходилось возвращаться по уже пройденному. Задача словно издевалась.
Эйлер смотрит на карту иначе
В 1736 году за головоломку взялся Леонард Эйлер — швейцарский математик, один из самых великих в истории. И сделал он нечто гениальное в своей простоте: он выбросил карту.
Эйлер понял, что для этой задачи совершенно неважно, какой мост длинный, а какой короткий, где красивая набережная, а где грязный переулок. Важно только одно: какие куски суши с какими соединены и сколькими мостами. Всё остальное — лишний шум.
Форма города не имеет значения. Значение имеет лишь то, что с чем связано.
Это как со схемой метро. На настоящей карте линии петляют, станции стоят на разном расстоянии, поезда едут под землёй мимо рек и домов. Но на схеме метро всё это стёрто: остались только кружочки-станции и линии между ними. И чтобы понять, как доехать с одной станции на другую, тебе настоящая география не нужна — нужна только схема связей. Вот ровно так Эйлер и посмотрел на Кёнигсберг.
Точки и линии вместо мостов
Эйлер заменил каждый кусок суши точкой, а каждый мост — линией между точками. Получилась простая картинка: четыре точки и семь линий. Сегодня мы называем такую конструкцию графом: точки в нём зовутся вершинами, а линии — рёбрами.
И тут Эйлер задал ключевой вопрос: сколько мостов сходится к каждому куску суши? Число рёбер, выходящих из вершины, математики называют её степенью. Посчитаем для Кёнигсберга:
- остров Кнайпхоф — к нему ведёт 5 мостов;
- остальные три части суши — по 3 моста каждая.
Теперь — самое красивое рассуждение. Представь, что ты идёшь по маршруту и проходишь через какой-то кусок суши, не начиная и не заканчивая на нём. Значит, ты по одному мосту пришёл и по другому ушёл. Мосты у такой «промежуточной» земли всегда расходуются парами: вошёл — вышел. А раз парами, то и общее число мостов у неё должно быть чётным.
Почему пройти невозможно
Вот в этом вся разгадка. Если кусок суши не является ни началом, ни концом твоей прогулки, число его мостов обязано быть чётным — иначе один мост останется «лишним», без пары. Нечётное число мостов допустимо только у старта и у финиша маршрута. А значит, точек с нечётной степенью в удачном маршруте может быть не больше двух.
Теперь посмотри на Кёнигсберг: степени его частей — это 5, 3, 3 и 3. Все четыре — нечётные! Четыре нечётные вершины при дозволенных двух. Маршрут невозможен в принципе. Не потому, что горожане плохо старались или были недостаточно сообразительны, — а потому, что так устроена сама связь мостов. Эйлер не просто не нашёл путь. Он доказал, что пути нет и быть не может.
Сегодня маршрут, проходящий по каждому ребру графа ровно один раз, в честь Эйлера называют эйлеровым путём. И правило простое: такой путь существует, только если в графе нечётных вершин ноль или ровно две. В Кёнигсберге их было четыре — приговор окончательный.
Как из прогулки выросла наука
Самое поразительное в этой истории — не сама головоломка, а то, что из неё выросло. Решая задачу о мостах, Эйлер придумал способ думать о мире как о сети связей: что с чем соединено, сколько у чего соседей, можно ли откуда-то куда-то добраться. Так родилась теория графов — целый раздел математики.
И она оказалась повсюду. Карта метро, по которой ты ищешь пересадку, — это граф. Социальная сеть, где друзья связаны друг с другом, — граф. Навигатор, который прокладывает дорогу через перекрёстки, интернет с его маршрутами между серверами, схема авиарейсов между городами — всё это графы. Каждый раз, когда программа ищет кратчайший путь или проверяет, всё ли связано между собой, она опирается на идеи, которые начались с прогулки по семи мостам.
В этом и есть главный урок Кёнигсберга. Иногда, чтобы решить задачу, нужно перестать смотреть на лишние детали и разглядеть скелет связей под ними. Эйлер стёр с карты дома, реку и сами мосты — и увидел чистую структуру, которую можно посчитать. Маленькая городская забава обернулась инструментом, без которого сегодня не работали бы ни навигаторы, ни интернет. Неплохо для прогулки, которую так никто и не смог пройти.