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

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

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

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

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

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

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

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

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

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

Наука и жизнь
«Инспектор мне не верил». Автомобилистов обвиняют в чужих ДТП «Инспектор мне не верил». Автомобилистов обвиняют в чужих ДТП

Из-за утечки данных из каршеринговых сервисов пострадали десятки водителей

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

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

Наука и жизнь
Униженные и оскорбленные в эфире политического телевещания Униженные и оскорбленные в эфире политического телевещания

Телевидение в последнее время все чаще демонстрирует образцы высоких отношений

СНОБ
Летающий мопед Летающий мопед

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

Популярная механика
7 самых распространенных ошибок, которые мы совершаем во время занятий любовью 7 самых распространенных ошибок, которые мы совершаем во время занятий любовью

Эти промахи портят твою интимную жизнь

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

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

Наука и жизнь
10 лучших автоматов и пулемётов мира 10 лучших автоматов и пулемётов мира

Война никогда не меняется в отличие от её инструментов

Популярная механика
Грозовой реактор Грозовой реактор

Физики обнаружили, что грозы порождают в атмосфере позитроны и изотопы

Наука и жизнь
Простая сложная история Простая сложная история

Харизматичная артистка Ксана Сергиенко пока еще ищет себя на сцене

OK!
6 признаков глупого человека 6 признаков глупого человека

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

Psychologies
Как работает светозвуковое оружие Как работает светозвуковое оружие

Зло ничего не видит, зло ничего не слышит — и поэтому я защищен от него

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

От чего избавились животные в ходе эволюции

Вокруг света
Рождение, венчание, ложная тревога и еще 4 невероятных случая в самолете Рождение, венчание, ложная тревога и еще 4 невероятных случая в самолете

Несколько удивительных историй не только о людях на борту, но и об одной кошке

РБК
Искаженные инвестиции Искаженные инвестиции

Какие активы принесли инвесторам тысячи и миллионы процентов и что это означает

Forbes
«Я готов к большим переменам» «Я готов к большим переменам»

Макс Барских о новых альбомах, самопознании и одиночестве

OK!
Пришел Кутузов бить французов: 7 мифов о легендарном генерал-фельдмаршале Пришел Кутузов бить французов: 7 мифов о легендарном генерал-фельдмаршале

Масон, заговорщик, бездарный полководец, «выезжавший» за счет чужих достижений?

Вокруг света
Что читать: отрывок из романа «Восточно-западная улица. Происхождение терминов геноцид и преступление против человечества» Что читать: отрывок из романа «Восточно-западная улица. Происхождение терминов геноцид и преступление против человечества»

Новая книга Филиппа Сэндса — интересный и живой рассказ о человеческих судьбах

Esquire
Пот, кровь, слёзы и крест Пот, кровь, слёзы и крест

В конце XI века десятки тысяч людей отправились освобождать Иерусалим

Дилетант
Грозный-2000: не город-герой Грозный-2000: не город-герой

20-летие штурма: реконструкция и новые свидетельства

Русский репортер
Маленькая страна Маленькая страна

Словения миниатюрна и прекрасна, как изящная статуэтка

Добрые советы
Как работает огнеметная система «Солнцепек» Как работает огнеметная система «Солнцепек»

«Солнцепек» тяжелая огнеметная система, обладающая незаурядной мощью

Популярная механика
Билли Айлиш: без взрослого дяди Билли Айлиш: без взрослого дяди

Что на самом деле объединяет подростков и буржуазный мир

Русский репортер
Тельцы ленивые, а Раки чувствительные: самая слабая сторона знаков зодиака Тельцы ленивые, а Раки чувствительные: самая слабая сторона знаков зодиака

Если ты в чем-то не сильна, не отчаивайся

Cosmopolitan
Почему потеют ладони рук у мужчин: основные причины и способы решения проблемы Почему потеют ладони рук у мужчин: основные причины и способы решения проблемы

Потные ладони — проблема некритичная, но очень досадная

Playboy
Дорого и нет времени. Почему россияне не любят спорт и что с этим делать Дорого и нет времени. Почему россияне не любят спорт и что с этим делать

Есть ли в России ЗОЖ и сколько людей в стране реально занимаются спортом

Forbes
ТУ-95МС: ракетоносец ядерной триады ТУ-95МС: ракетоносец ядерной триады

ТУ-95МС часто называют «Медведем»

Популярная механика
Вишневый сад Вишневый сад

Прима-балерина Мариинского театра показала AD свою петербургскую квартиру

AD
Создан новый «детонирующий» ракетный двигатель Создан новый «детонирующий» ракетный двигатель

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

Популярная механика
Верные друзья Верные друзья

Елизавета Голубцова и Марина Бирюкова оформили квартиру для семьи старого друга

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