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

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

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

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

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

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

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

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

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

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

Наука и жизнь
Нездоровые отношения: как нарушаются связи с собственным телом Нездоровые отношения: как нарушаются связи с собственным телом

Как «починить» нарушенные отношения с собственным телом

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

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

Популярная механика
Одна вокруг света. Как проехать через самый опасный перевал в Ливане Одна вокруг света. Как проехать через самый опасный перевал в Ливане

60-я серия о кругосветном путешествии москвички Ирины Сидоренко и ее собаки

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

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

Наука и жизнь
Надежда Михалкова о фильме “Лед-2”, отношениях с детьми и премии “Оскар” Надежда Михалкова о фильме “Лед-2”, отношениях с детьми и премии “Оскар”

Актриса Надежда Михалкова о том, чего не хватает российскому кинематографу

Cosmopolitan
Пожиратели бюджетов Пожиратели бюджетов

Почему иногда строить дороги не нужно

Forbes
Каршеринг начали угонять: кто, как и зачем это делает Каршеринг начали угонять: кто, как и зачем это делает

Незавершенная поездка на каршеринге может обернуться угоном

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

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

Наука и жизнь
Вкусные водоросли, счастливые коровы и супермясорубки. Обсуждение фильма «2040: Будущее ждет» Вкусные водоросли, счастливые коровы и супермясорубки. Обсуждение фильма «2040: Будущее ждет»

Как может выглядеть наш мир, если мы будем развивать уже существующие технологии

СНОБ
Великое переселение лошадей Великое переселение лошадей

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

Наука и жизнь
Хитрые военные тактики: 9 исторических примеров Хитрые военные тактики: 9 исторических примеров

История — это не набор дат и фамилий, а в первую очередь опыт

Популярная механика
О чём пишут научно-популярные журналы мира О чём пишут научно-популярные журналы мира

Интересные исследования и новости научного мира

Наука и жизнь
Тест-драйв Renault Arkana. Лед и турбо Тест-драйв Renault Arkana. Лед и турбо

Зимняя проверка для мотора 1,3 с вариатором и полным приводом

РБК
Декоративный кустарник с витаминными плодами Декоративный кустарник с витаминными плодами

Хеномелес японский давно известен многим садоводам под названием «японская айва»

Наука и жизнь
Когда сигары недостаточно: чем правильно закусывать виски, чтобы не убить образ эстета Когда сигары недостаточно: чем правильно закусывать виски, чтобы не убить образ эстета

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

Playboy
Генри Дарджер Генри Дарджер

Судьба Генри Дарджера трагична или триумфальна?

Дилетант
С места – в полет: возможен ли безаэродромный взлет самолета С места – в полет: возможен ли безаэродромный взлет самолета

Как родилась идея самолетов с укороченным взлетом?

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

За сетями 5G уже проступают контуры следующего поколения связи

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

С выгоранием сотрудников можно и нужно бороться

Playboy
Михаил Мишустин и его семья заработали около $36 миллионов в инвесткомпании UFG. Премьер работал там в 2008-2010 годах Михаил Мишустин и его семья заработали около $36 миллионов в инвесткомпании UFG. Премьер работал там в 2008-2010 годах

Мишустин перешел в бизнес с госслужбы и стал владельцем 25% в фондах UFG

Esquire
Цифровая независимость Цифровая независимость

Диджитал-детокс необходим не меньше, чем избавление от токсинов в клинике

Robb Report
Водителей разделят на плохих и хороших Водителей разделят на плохих и хороших

Разбираем самые важные изменения в проекте нового КоАП

РБК
Владислав Листьев Владислав Листьев

Правила жизни телеведущего и журналиста Владислава Листьева

Esquire
Розовая пантера Розовая пантера

Кристина Челестино балансирует между дизайном и картинками для Instagram

AD
Приговор из 1937 года: о чем говорит жестокость по делу «Сети» Приговор из 1937 года: о чем говорит жестокость по делу «Сети»

Приговор фигурантов дела «Сети» напоминает приговоры сталинских времен

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

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

РБК
Их союз выдержал испытание Их союз выдержал испытание

Мы можем дружить годами и семьями, а потом происходит что-то и связь обрывается

Psychologies
15 фотографий Синтии, манекена-звезды 1930-х 15 фотографий Синтии, манекена-звезды 1930-х

Манекен Синтия вела такую насыщенную жизнь, что ей позавидовала бы любая девушка

Maxim
Письма счастья Письма счастья

Объясняем, как правильно писать завещания

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