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

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

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

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

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

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

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

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

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

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

Дилетант
Как собрать компьютер самому из комплектующих: пошаговая инструкция Как собрать компьютер самому из комплектующих: пошаговая инструкция

Со сборкой компьютера может справиться даже ребенок

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

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

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

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

Добрые советы
Стая товарищей Стая товарищей

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

Наука и жизнь
Три мужа и 50 книг: мистическая история Мэри Хиггинс Кларк длиной в 92 года Три мужа и 50 книг: мистическая история Мэри Хиггинс Кларк длиной в 92 года

Каждый из 51 романов Мэри Хиггинс Кларк неоднократно переиздавался

Cosmopolitan
Алюминиевый век Алюминиевый век

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

Наука и жизнь
Делай, как Адель Делай, как Адель

Упражнения пилатеса и сиртфуд-диета – два секрета стройности певицц Адель

Худеем правильно
В поиске космических катастроф. Вахта телескопов-роботов В поиске космических катастроф. Вахта телескопов-роботов

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

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

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

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

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

Наука и жизнь
Похищение, катастрофа и суицид: трагедии детей советских экстрасенсов Похищение, катастрофа и суицид: трагедии детей советских экстрасенсов

Как складываются отношения с партнерами и детьми, экстрасенсы не раскрывали

Cosmopolitan
Фонтан «Плюющиеся лидеры». Парк Презикхааф, Арнем, Нидерланды Фонтан «Плюющиеся лидеры». Парк Презикхааф, Арнем, Нидерланды

Испанец Фернандо Санчес Кастильо не смог установить этот фонтан у себя на родине

Дилетант
«Мы все дофаминовые алкоголики»: Герман Греф — о счастье, смартфонах и страхе перед Uber «Мы все дофаминовые алкоголики»: Герман Греф — о счастье, смартфонах и страхе перед Uber

Самые интересные высказывания Германа Грефа об искусственном интеллекте

Forbes
Подарок молодым хозяйкам Подарок молодым хозяйкам

История книги Елены Молоховец, научившей общество питаться дешево и вкусно

Вокруг света
Ты тоже можешь: история восьми гениальных изобретений Ты тоже можешь: история восьми гениальных изобретений

У всех нас есть набор кухонной техники, существенно упрощающий жизнь

Популярная механика
Знай наших Знай наших

Уникальные достижения отечественных ученых

Популярная механика
Не уйти от «Сети». Почему пензенское дело важно для будущего России Не уйти от «Сети». Почему пензенское дело важно для будущего России

Суд над анархистами в Пензе поставил перед обществом трудные вопросы

СНОБ
Рыжебородый против Льва Рыжебородый против Льва

XII век — период расцвета рыцарства, грандиозных походов и великолепных турниров

Дилетант
Обещал на руках носить: 7 мужчин, решившие увековечить на своих телах женские имена (и их истории) Обещал на руках носить: 7 мужчин, решившие увековечить на своих телах женские имена (и их истории)

Семеро мужчин рассказывают, как они увековечили на своих телах женские имена

Esquire
Два одиночества Два одиночества

«Встретились два одиночества» — так можно пересказать сюжет фильма «Два папы»

Дилетант
Каменная стена: 5 имен, которые носят самые надежные мужчины Каменная стена: 5 имен, которые носят самые надежные мужчины

Как зовут мужчин, за которыми можно спрятаться, как за каменной стеной

Cosmopolitan
Дальние родственники. Азиатские наследники Jeep Дальние родственники. Азиатские наследники Jeep

Все легендарные модели азиатских внедорожников — потомки Jeep

4x4 Club
Как эквадорец с русскими корнями перезапустил шаткий стартап с нуля, сделав его «единорогом» Как эквадорец с русскими корнями перезапустил шаткий стартап с нуля, сделав его «единорогом»

Как эквадорец с русскими корнями запустил бизнес стоимостью более $1 млрд

Forbes
Что не так с фильмом «Скандал» Что не так с фильмом «Скандал»

Видимо, иногда лучше не снимать кино вовсе, чем осторожничать до последнего

GQ
«Неизбранные дороги» с Хавьером Бардемом и Эль Фаннинг — неуклюжая история, спасенная прекрасными актерами «Неизбранные дороги» с Хавьером Бардемом и Эль Фаннинг — неуклюжая история, спасенная прекрасными актерами

На Берлинском кинофестивале показали новый фильм Салли Поттер

Esquire
9 условий, которые нужно соблюдать, чтобы не раздражать своего кота 9 условий, которые нужно соблюдать, чтобы не раздражать своего кота

Что нужно делать, чтобы жизнь твоего кота была счастливой?

Maxim
«Мир стал более жесток к женщинам». Главная писательница Израиля о том, почему быть хорошей матерью уже недостаточно «Мир стал более жесток к женщинам». Главная писательница Израиля о том, почему быть хорошей матерью уже недостаточно

Израильская писательница №1 об антисемитизме, косых взглядах и любви к детям

Forbes
Самооценка или самоценность — что выбираете? Самооценка или самоценность — что выбираете?

О том, что такое самоценность и в чем ее отличие от самооценки

Psychologies
Стоит ли ожидать благодарности от внуков за денежные подарки? Стоит ли ожидать благодарности от внуков за денежные подарки?

Почему внуки не благодарят бабушек и дедушек за денежные подарки?

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