Знаете ли вы, что подтолкнуло Леонарда Эйлера к созданию основ теории графов

Наука и жизньНаука

Пути и маршруты

Дмитрий Максимов

Город Кёнигсберг (Matthäus Merian 1650), Zedlers Universal-Lexicon, Band XV (K). Иллюстрация: www.hs-augsburg.de/bibliotheca Augustana

Мосты Кёнигсберга и Эйлеров путь

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

Кёнигсберг (ныне Калининград) возник в XIII веке как три независимых поселения на островах и берегах реки Преголи. Он расположен между Польшей и Литвой на берегу Балтийского моря. Постепенно между поселениями налаживались активные торговые связи (хотя не обходилось и без военных конфликтов), поэтому возникла необходимость более тесного взаимодействия. В XIV веке началось строительство сразу нескольких мостов, и к концу XV столетия их было уже семь. Во многом благодаря мостам три независимых поселения слились в один большой город. Мосты стали его достопримечательностью, на них устраивали празднования, карнавалы, религиозные шествия.

Однажды местный житель, имени которого мы не знаем, задался вопросом: можно ли совершить прогулку по всему городу, пройдя по каждому мосту ровно один раз? Задача приобрела большую популярность, её задавали прибывшим в Кёнигсберг туристам и обязательно говорили о том, что такой маршрут есть — нужно только очень постараться его найти. Горожане, конечно, знали, что побывать во всех частях города, пройдя по каждому мосту всего один раз, невозможно. В этом легко было убедиться, просто перебирая разные маршруты.

Я. Э. Хандманн. Портрет Леонарда Эйлера. 1756 год. Иллюстрация: Wikimedia Commons/PD

В 1730 году задачей про мосты Кёнигсберга заинтересовался Леонард Эйлер (1707—1783), который решил её обобщить и найти ответ на вопрос: при каком условии мосты и острова образуют такую конфигурацию, что посетить каждый мост всего один раз можно, а при каком — нельзя? Эйлер задумался: о каком, собственно, математическом объекте идёт речь в этой задаче? Подходящих объектов, описывающих подобные ситуации, он не знал и придумал новый — граф.

Что такое граф? Это набор точек (они называются вершинами графа), некоторые из которых соединены линиями (не обязательно прямолинейными отрезками), называемыми рёбрами графа. Отметим, что геометрические свойства этих линий — прямые они или кривые, пересекаются или нет — не влияют на свойства графа. Важно лишь то, какие именно вершины с какими соединены.

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

Полный граф с четырьмя вершинами в виде: квадрата с диагоналями (слева) и треугольника с точкой внутри (справа).

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

Но вернёмся к решению задачи о мостах. Эйлер представил карту мостов в виде графа: рёбра — мосты, а острова и берега — вершины. Правда, некоторые пары вершин получившегося графа оказались соединены двумя рёбрами (такие рёбра называются кратными), но это не важно. Для каждой вершины — вслед за Эйлером — посчитаем количество выходящих из неё рёбер. Такое число называется степенью вершины. У вершин B, C и D степень равна трём, а у вершины A — пяти.

Авторизуйтесь, чтобы продолжить чтение. Это быстро и бесплатно.

Регистрируясь, я принимаю условия использования

Рекомендуемые статьи

Летающий мопед Летающий мопед

Автожиры: полет над вулканом и не только.

Популярная механика
Российский паспорт советской бабушки. Почему новые инициативы Кремля по гражданству ни к чему не приведут Российский паспорт советской бабушки. Почему новые инициативы Кремля по гражданству ни к чему не приведут

Российская верхушка сделает всё, лишь бы ничего не менять в самой России

СНОБ
Стая товарищей Стая товарищей

Повесть о том, что значит быть собакой, и о том, что значит быть человеком

Наука и жизнь
Техпарад Техпарад

Новости мира науки и техники

Популярная механика
6 признаков глупого человека 6 признаков глупого человека

Как понять, кого нужно избегать? Да и нужно ли на самом деле?

Psychologies
Как правильно просить помощи в интернете: 7 простых советов Как правильно просить помощи в интернете: 7 простых советов

Как собрать денег в Интернете на операцию по удалению злокачественного пупка

Maxim
Великое переселение лошадей Великое переселение лошадей

Эту историю я обнаружил, изучая подшивку журнала «Нива» за 1901 год

Наука и жизнь
Почему вам обязательно нужен кардиган Почему вам обязательно нужен кардиган

Эта вещь стала объектом внимания абсолютного большинства дизайнеров

GQ
Трагедия Эйнштейна, или счастливый Сизиф Трагедия Эйнштейна, или счастливый Сизиф

Очерк второй. Эйнштейн против Паули. Единая теория поля

Наука и жизнь
Женатые и одиночки: новый взгляд на стереотипы Женатые и одиночки: новый взгляд на стереотипы

Как же изменилось мнение общества о женатых и одиноких?

Psychologies
Археология в 2019 году: несколько интересных находок Археология в 2019 году: несколько интересных находок

Интересные археологические находки 2019 года

Наука и жизнь
Сергей Мироненко: 100 событий, которые изменили Россию Сергей Мироненко: 100 событий, которые изменили Россию

Отрывки из серии очерков о важных событиях в отечественной истории

СНОБ
В свете полной луны… В свете полной луны…

...происходят странные вещи с поведением животных

Вокруг света
Новая мода: прийти в сознание Новая мода: прийти в сознание

Самый современный тренд в фэшн-индустрии сегодня – осознанная мода

Лиза
Женский орден на мужской груди Женский орден на мужской груди

Система орденов Российской империи отличалась от советского времени и наших дней

Дилетант
Щит от гиперзвука Щит от гиперзвука

Они быстро настигнут врага в любой точке мира

Популярная механика
Завтра была война… Завтра была война…

Резкий поворот во внешней политике Советского Союза

Дилетант
Пять раз отмерь Пять раз отмерь

Главные ошибки филантропов и основателей частных благотворительных фондов

Forbes
Кто является автором термина «Великая Отечественная война»? Кто является автором термина «Великая Отечественная война»?

Кем впервые было произнесено название войны, которую предстояло пройти СССР

Дилетант
Suzuki Jimny. Возврат к эпохе «Самураев» Suzuki Jimny. Возврат к эпохе «Самураев»

На рынке появился новый Suzuki Jimny: не какой-то рестайлинговый, а all new

4x4 Club
Так ли опасен хеликобактер? Так ли опасен хеликобактер?

Виноват ли хеликобактер в проблемах с желудком?

Здоровье
Видеоигры с упорством ломятся на киноэкраны. Но зачем? Видеоигры с упорством ломятся на киноэкраны. Но зачем?

Кажется, экранизация видеоигр – не самый важный элемент для развития индустрии

GQ
Юра Борисов: «Я умею вставать на место любого человека» Юра Борисов: «Я умею вставать на место любого человека»

Актер Юра Борисов объяснил, почему главной ценностью в жизни считает любовь

Grazia
Ребалансинг: как излечить тело с помощью телесных практик Ребалансинг: как излечить тело с помощью телесных практик

Когда официальная медицина бессильна, тяжело не сдаться и не смириться

Psychologies
Обыкновенная история Обыкновенная история

Агрессия подростков – крайне неприятное, но закономерное и естественное явление

Лиза
Екатерина Климова: Сейчас чувствую себя счастливой чаще, чем в юности Екатерина Климова: Сейчас чувствую себя счастливой чаще, чем в юности

Где Климова — там улыбки, движение и жесткий тайминг

Добрые советы
Одиночки не одиноки Одиночки не одиноки

Нам часто кажется, что те, у кого нет семьи, страдают от одиночества

Psychologies
Ярче Луны Ярче Луны

Если вы вдруг не узнали девушку на фото, рекомендуем набрать Lizzo в iTunes

Glamour
Очень полезная fishka Очень полезная fishka

Лучшее время для рыбной диеты – зима

Лиза
Где водятся инопланетяне — названо новое место Где водятся инопланетяне — названо новое место

Чтобы найти инопланетную жизнь, мы должны сосредоточиться на белых карликах

Популярная механика
Открыть в приложении