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

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

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

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

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

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

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

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

Альянсы и союзы Альянсы и союзы

Вторая часть ответов на вопросы об альянсах союзников против нацистской Германии

Дилетант
8 полезных привычек долгожителей, которые продлят и твои года 8 полезных привычек долгожителей, которые продлят и твои года

Эти полезные привычки смогут улучшить качество твоей жизни

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

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

Psychologies
Прямой курс на облака: 2020 год как новый этап развития облачного гейминга Прямой курс на облака: 2020 год как новый этап развития облачного гейминга

Облачный гейминг заинтересовал крупнейшие технологические компании мира

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

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

Наука и жизнь
5 самых грозных боевых топоров 5 самых грозных боевых топоров

Какие топоры завоевали себе славу и были наиболее популярны у воинов

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

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

Наука и жизнь
Летчики, солдаты, геймеры: как работают операторы БПЛА Летчики, солдаты, геймеры: как работают операторы БПЛА

Сочетание «человек–машина» создает проблемы и вызывает ряд непростых вопросов

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

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

Наука и жизнь
Крепкий орешек Крепкий орешек

Наталья Давыдова — о досадных ошибках на пути к идеальным ягодицам

Vogue
Грозовой реактор Грозовой реактор

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

Наука и жизнь
Женщины vs мужчины: кто основные клиенты популярных онлайн-сервисов Женщины vs мужчины: кто основные клиенты популярных онлайн-сервисов

Нужно ли учитывать гендерный состав пользователей в маркетинговом продвижении

Forbes
«Проклятого чёрта брат» «Проклятого чёрта брат»

А существовало ли письмо запорожцев турецкому султану на самом деле?

Дилетант
Похудела в три раза: как американка весом 300 кг взяла себя в руки Похудела в три раза: как американка весом 300 кг взяла себя в руки

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

Cosmopolitan
Орловы Орловы

Орловы в короткий срок они смогли возвыситься и добиться влияния при дворе

Дилетант
Как стать бодипозитивной за 60 секунд (даже если ты против) Как стать бодипозитивной за 60 секунд (даже если ты против)

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

Cosmopolitan
Унгерн-Штернберги Унгерн-Штернберги

Баронский род Унгерн-Штернберг восходит к XIII веку

Дилетант
Якутия в эпицентре «собачьего» скандала Якутия в эпицентре «собачьего» скандала

Будет ли введен мораторий на закон об ответственном обращении с животными

Русский репортер
История болезни: двойная мораль История болезни: двойная мораль

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

Дилетант
«Лучшая возможность в жизни»: зачем миллиардер из Гонконга во время протестов скупил заброшенные фабрики «Лучшая возможность в жизни»: зачем миллиардер из Гонконга во время протестов скупил заброшенные фабрики

Тан Шинбо скупает заброшенные фабрики и входит в число богатейших миллиардеров

Forbes
Царь-птица Царь-птица

К этим гордым и боевым птицам мы относимся с поразительным пренебрежением

Популярная механика
Эпизод седьмой: предательство и подлог Эпизод седьмой: предательство и подлог

Кардинал Войелло обнаруживает неожиданного союзника, а папу предают

Esquire
P.S. Я себя люблю P.S. Я себя люблю

Носить то, что нравится, есть то, что любишь, быть собой — разве не это счастье

Вокруг света
Дамы, ваш выход Дамы, ваш выход

Мир искусства, дизайна и архитектуры был бы совсем другим, если бы не женщины

AD
Марион Котийяр, актриса Марион Котийяр, актриса

Что скрывается за шармом актрисы Марион Котийяр

Худеем правильно
Юра Борисов: «Я умею вставать на место любого человека» Юра Борисов: «Я умею вставать на место любого человека»

Актер Юра Борисов объяснил, почему главной ценностью в жизни считает любовь

Grazia
Как сформировать полезные пищевые привычки на каждый день Как сформировать полезные пищевые привычки на каждый день

Делимся лайфхаками, которые помогут изменить пищевой режим

РБК
Тотальный кризис доверия. Кто виноват и что делать? Тотальный кризис доверия. Кто виноват и что делать?

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

Psychologies
Беззащитный класс: почему в США курильщиков перестали брать на работу Беззащитный класс: почему в США курильщиков перестали брать на работу

Американские компании все чаще отказывают в работе курильщикам

Forbes
Портрет юродивой Ксении Петровой Портрет юродивой Ксении Петровой

О портрете Ксении Петровой (Ксении Петербургской) центра «Старая Деревня»

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