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

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

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

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

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

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

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

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

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

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

Наука и жизнь
Проект сверхтяжелого танка: каким бывает оружие пропаганды Проект сверхтяжелого танка: каким бывает оружие пропаганды

Первая мировая война стала ареной для испытаний различных видов нового оружия

Популярная механика
Бурлеск Самбурской Бурлеск Самбурской

Актриса, певица, дива, Самбурская, Настасья – все это о ней

Maxim
Что происходит с мозгом, когда ты переживаешь из-за денег: 5 опасных последствий Что происходит с мозгом, когда ты переживаешь из-за денег: 5 опасных последствий

Может, после этих новостей ты изменишь свое отношение к деньгам

Playboy
Чёрный передел: версия 1939 года Чёрный передел: версия 1939 года

Секретный протокол к Пакту о ненападении

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

Чего мужчина не должен стыдиться?

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

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

Наука и жизнь
Идеальный домашний помощник: как выбрать вертикальный беспроводной пылесос «2 в 1» Идеальный домашний помощник: как выбрать вертикальный беспроводной пылесос «2 в 1»

Хотите эффективно убираться в квартире и при этом не зависеть от проводов?

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

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

Наука и жизнь
«Инвестклимат в России определяется ФСБ»: Сергей Гуриев о новом правительстве и «конституционном самоперевороте» «Инвестклимат в России определяется ФСБ»: Сергей Гуриев о новом правительстве и «конституционном самоперевороте»

Экономист Сергей Гуриев дал оценку новому составу правительства и реформе

Forbes
В поиске космических катастроф. Вахта телескопов-роботов В поиске космических катастроф. Вахта телескопов-роботов

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

Наука и жизнь
Наши «Сети». Как статья в «Медузе» убеждает протестовать против приговора в Пензе Наши «Сети». Как статья в «Медузе» убеждает протестовать против приговора в Пензе

Дилемма защитников фигурантов «Сети» вряд ли сложнее проблем Black lives matter

СНОБ
Великий комбинатор Великий комбинатор

Знаменитый аферист времен великой депрессии Виктор Люстиг

Вокруг света
Нил Фергюсон: Тайная встреча Анны Ахматовой, разозлившая Сталина Нил Фергюсон: Тайная встреча Анны Ахматовой, разозлившая Сталина

Глава книги «Площадь и башня» журналиста Нила Фергюсона

СНОБ
Наука побеждать Наука побеждать

По требованию Сталина сняли целый цикл картин про русских военачальников

Дилетант
4 шага к успешным диалогам в приложениях для знакомств (это проще, чем кажется) 4 шага к успешным диалогам в приложениях для знакомств (это проще, чем кажется)

Это просто, если делать все правильно

Playboy
Не жалея ни женщин, ни детей Не жалея ни женщин, ни детей

Процесс по делу об айнзацгруппах в Нюрнберге

Дилетант
8 частей тела, которые ты моешь недостаточно тщательно (угадали?) 8 частей тела, которые ты моешь недостаточно тщательно (угадали?)

Ты не грязнуля, мы все так делаем!

Playboy
Память — главная функция мозга Память — главная функция мозга

Отвечает директор Научного центра неврологии РАН академик Михаил Пирадов

Наука и жизнь
Секретный Oasis для TikTok: как самый дорогой стартап в мире ищет новые источники дохода Секретный Oasis для TikTok: как самый дорогой стартап в мире ищет новые источники дохода

Владелец TikTok хочет снизить зависимость от своего самого известного творения

Forbes
Как создатель Angry Birds планирует воспитать поколение гениев Как создатель Angry Birds планирует воспитать поколение гениев

Программа для детей, которая в буквальном смысле готовит их к полету в космос

РБК
Тест-драйв Audi A8L. Три мнения об автомобиле, греющем ступни Тест-драйв Audi A8L. Три мнения об автомобиле, греющем ступни

Рассказываем об одном из самых дорогих седанов рынка — Audi A8L

РБК
5 аксессуаров,  которые сделают твой гардероб более стильным 5 аксессуаров,  которые сделают твой гардероб более стильным

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

Cosmopolitan
Закатать в биобанку Закатать в биобанку

Кто и зачем в России собирает биологические материалы людей и животных

Русский репортер
Великое переселение лошадей Великое переселение лошадей

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

Наука и жизнь
Однажды в Голливуде Однажды в Голливуде

Дизайнер Келли Уирстлер для своей книги обновила дом в Беверли-Хиллз

AD
Цвет и мозг: какие оттенки выбрать для счастливой жизни Цвет и мозг: какие оттенки выбрать для счастливой жизни

Цвет может влиять на самочувствие, настроение и желания человека

РБК
«Железные» леди 50+ «Железные» леди 50+

Эти героини доказывают: после 50 можно добиться серьезных результатов в спорте

Здоровье
Синие волосы – оттенки, краски и тоники для волос Синие волосы – оттенки, краски и тоники для волос

Мода на яркие оттенки вызвала всплеск популярности ярких красок для волос

Cosmopolitan
Малыш, а как же я? Малыш, а как же я?

Рождение ребенка само по себе не гарантия счастья, тем более мгновенного

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