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

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

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

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

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

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

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

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

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

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

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

Госбюджет России в превосходной форме, а вот в экономике все неладно

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

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

Наука и жизнь
Сколько стоит человек: от волос до почек и скелета Сколько стоит человек: от волос до почек и скелета

Cчитаем, сколько стоит Homo sapiens, 1 штука

Популярная механика
Чёрный передел: версия 1939 года Чёрный передел: версия 1939 года

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

Дилетант
Маленькая страна Маленькая страна

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

Добрые советы
Бурлеск Самбурской Бурлеск Самбурской

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

Maxim
Семиместный Mitsubishi Outlander. Ты бы меня ещё о внуках спросил… Семиместный Mitsubishi Outlander. Ты бы меня ещё о внуках спросил…

Mitsubishi Outlander получил очередную порцию обновлений и третий ряд сидений

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

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

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

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

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

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

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

Как сделать волосы густыми и сильными в домашних условиях?

Cosmopolitan
Изобрести колесо Изобрести колесо

Люди шли к изобретению колеса не одно тысячелетие

Вокруг света
Техпарад Техпарад

Новости мира науки и техники

Популярная механика
Наши высочества Наши высочества

Интервью с высокими и талантливыми актрисами сериала «Дылды»

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

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

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

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

Дилетант
Директор по наследию Vacheron Constantin — о собрании Les Cabinotiers Директор по наследию Vacheron Constantin — о собрании Les Cabinotiers

Кристиан Сельмони рассказал об услуге bespoke в моде и часовом деле

РБК
Правила жизни Правила жизни

Правила жизни величайшего актера Кирка Дугласа

Playboy
Как часто нужно менять постельное белье — точно не раз в месяц Как часто нужно менять постельное белье — точно не раз в месяц

Как часто нужно менять постельное белье, чтобы оно оставалось безопасным?

Cosmopolitan
Холод не помеха: как правильно бегать зимой Холод не помеха: как правильно бегать зимой

Мороз — не повод отменять беговую тренировку на улице

Популярная механика
Huawei показал складной смартфон с 5G и обновление экосистемы Huawei показал складной смартфон с 5G и обновление экосистемы

Huawei показала компоненты собственной цифровой интеллектуальной экосистемы

Популярная механика
Рост прибыли на 1900%, будущий кризис и подготовка к смерти: что Баффет написал инвесторам в ежегодном письме Рост прибыли на 1900%, будущий кризис и подготовка к смерти: что Баффет написал инвесторам в ежегодном письме

Пересказ традиционного письма Уоррена Баффета инвесторам Berksihre Hathaway

Forbes
Жизнь по собственным правилам: каким был Кирк Дуглас Жизнь по собственным правилам: каким был Кирк Дуглас

Ярослав Забалуев вспоминает историю жизни актера Кирка Дугласа

РБК
Как устроен зенитный ракетно-пушечный комплекс «Тунгуска» Как устроен зенитный ракетно-пушечный комплекс «Тунгуска»

ЗРПК «Тунгуска» способен отбиться и от стройбатовца, и от боевых вертолетах

Maxim
Виктория Исакова: «Я во всем ищу смыслы» Виктория Исакова: «Я во всем ищу смыслы»

Мы попытались выяснить, чего хочет от жизни актриса Виктория Исакова

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

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

Популярная механика
Железная логика Железная логика

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

Добрые советы
Методичка для методологов. Поможем администрации завлечь людей на «добровольное голосование» Методичка для методологов. Поможем администрации завлечь людей на «добровольное голосование»

41% жителей России никогда не читали Конституцию

СНОБ
10 провальных американских истребителей 10 провальных американских истребителей

Благодаря чему самолёт становится успешным?

Популярная механика
Открыть в приложении