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

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

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

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

Город Кёнигсберг (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 — пяти.

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

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

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

Почему Генрих — не Генрих, а Людовик — не Людовик? Почему Генрих — не Генрих, а Людовик — не Людовик?

О проблеме перевода или огласовки иностранных имён собственных

Наука и жизнь
Как полюбить себя и свою нестандратную внешность: 4 истории реальных женщин Как полюбить себя и свою нестандратную внешность: 4 истории реальных женщин

Истории четырех героинь с внешними особенностями

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

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

Наука и жизнь
Жизнь без насилия (страха, боли, ненависти) Жизнь без насилия (страха, боли, ненависти)

Как быть, если вы столкнулись с насилием в отношениях? Где искать помощи?

Домашний Очаг
В поиске космических катастроф. Вахта телескопов-роботов В поиске космических катастроф. Вахта телескопов-роботов

Оптические телескопы системы МАСТЕР помогают астрономам разных стран

Наука и жизнь
Фабрика миллиардеров: сервис, помогающий малому бизнесу бороться с Amazon, подорожал на 1800% за пять лет Фабрика миллиардеров: сервис, помогающий малому бизнесу бороться с Amazon, подорожал на 1800% за пять лет

Сервис Shopify утверждает, что вооружает повстанцев в борьбе против Amazon

Forbes
Щит от гиперзвука Щит от гиперзвука

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

Популярная механика
Записались в актив Записались в актив

Надежда Оболенцева о том, стоит ли делить людей на сильных и слабых

Grazia
Эйнштейн против Бора. Квантовая механика Эйнштейн против Бора. Квантовая механика

Со смертью Эйнштейна мир стал другим

Наука и жизнь
Почему мерзнут руки и ноги — не только из-за холода Почему мерзнут руки и ноги — не только из-за холода

Рассказываем, почему мерзнут руки и ноги и как с этим бороться

Cosmopolitan
Мой Сталинград Мой Сталинград

Когда началась война, я была студенткой мединститута

Наука и жизнь
Мой остров больше Мой остров больше

У сестры Ричарда Брэнсона тоже есть частный райский остров

Tatler
Город бомбы Город бомбы

Из истории американского атомограда

Вокруг света
“Предсказание Терминатора”: как видит мир автопилот машины “Предсказание Терминатора”: как видит мир автопилот машины

Автопилота легкового автомобиля выглядят впечатляюще и пугающе

Популярная механика
Вооружение Вооружение

Первая часть ответов на вопросы о вооружении стран времен Второй мировой войны

Дилетант
Мой секрет семейного счастья: я больше не обижаюсь на близких Мой секрет семейного счастья: я больше не обижаюсь на близких

Принято считать, что в браке надо открыто обсуждать обиды

Psychologies
Берлин, 22 июня… Берлин, 22 июня…

В тот день футбол интересовал немцев больше, чем сообщения о военных действиях

Дилетант
Писсуар Дюшана за $2 млн. Как выглядит универсальная формула успеха Писсуар Дюшана за $2 млн. Как выглядит универсальная формула успеха

Альберт-Ласло Барабаши применил научные методы, чтобы вывести формулу успеха

Forbes
Монарх под видом демократа Монарх под видом демократа

Октавиан Август не стал повторять ошибок Цезаря

Дилетант
7 вопросов Наталье Поповой, режиссеру и психологу. Об инклюзивном театре 7 вопросов Наталье Поповой, режиссеру и психологу. Об инклюзивном театре

О том, чему может научить особый театр актеров и зрителей

Русский репортер
Алюминиевый век Алюминиевый век

История учит нас, что человечество достигло настоящей цивилизации

Наука и жизнь
Мерс Каннингем: жизнь в 3D Мерс Каннингем: жизнь в 3D

Главный редактор «Сноба»посмотрел фильм и пообщался с его автором

СНОБ
Мария Пиотровская — о том, как помочь детям с дислексией Мария Пиотровская — о том, как помочь детям с дислексией

Мария Пиотровская рассказала нам, почему двоечники могут оказаться гениями

РБК
Как включить блок питания без компьютера? Как включить блок питания без компьютера?

Рассказываем, как элементарно проверить работоспособность блока питания

CHIP
Как превратить обычную собаку в личного фитнес-инструктора Как превратить обычную собаку в личного фитнес-инструктора

В основе уникальной программы тренировок — обычная собака

Maxim
Первый украинский губернатор Первый украинский губернатор

В истории портретов случаются удивительные метаморфозы

Дилетант
Как сделать, чтобы живот не урчал: 8 простых лайфхаков Как сделать, чтобы живот не урчал: 8 простых лайфхаков

Всем известно чувство неловкости, когда живот издаёт бурлящие звуки

Cosmopolitan
История одной фотографии: Маргарет Кин доказывает авторство своих картин, 1970 год История одной фотографии: Маргарет Кин доказывает авторство своих картин, 1970 год

Ее бывший муж, присвоивший себе авторство, даже не пришел

Maxim
«Бороться все равно надо»: почему звезда легкой атлетики Мария Ласицкене может пропустить Олимпиаду-2020 «Бороться все равно надо»: почему звезда легкой атлетики Мария Ласицкене может пропустить Олимпиаду-2020

Как «нейтральный статус» повлиял на карьеру, мотивацию и доходы Марии Ласицкене

Forbes
Безупречный мерзавец Безупречный мерзавец

Гётевский Мефистофель изящен, остроумен, парадоксален

Дилетант
Открыть в приложении