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

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

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

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

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

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

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

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

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

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

Наука и жизнь
Мария Порошина: «Выстраиваю работу так, чтобы была возможность чаще общаться с детьми» Мария Порошина: «Выстраиваю работу так, чтобы была возможность чаще общаться с детьми»

Актриса рассказала как совмещает карьеру и воспитание пятерых детей

Здоровье
Анна Седокова Анна Седокова

Наверное, она уже привыкла к эпитетам «горячая», «аппетитная», «сочная»

Playboy
Renault Arkana. Сидя на диване, её не понять Renault Arkana. Сидя на диване, её не понять

Купе-кроссовер Renault Arkana создавался специально для России

4x4 Club
От чего умер Ленин? От чего умер Ленин?

На момент смерти Ленину было всего 53 года. На здоровье он никогда не жаловался

Дилетант
Пример для подражания: Юлия Темникова Пример для подражания: Юлия Темникова

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

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

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

Наука и жизнь
Тест-драйв Audi A8L. Три мнения об автомобиле, греющем ступни Тест-драйв Audi A8L. Три мнения об автомобиле, греющем ступни

Рассказываем об одном из самых дорогих седанов рынка — Audi A8L

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

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

Наука и жизнь
Как мучились мы музыкой в СССР Как мучились мы музыкой в СССР

Воспоминания о том, с какой допотопной аудиотехникой приходилось сосуществовать

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

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

Наука и жизнь
Тупик Собянина: почему попытки повторить московскую реновацию обречены на провал Тупик Собянина: почему попытки повторить московскую реновацию обречены на провал

Российский проект реновации не может строиться по московской модели

Forbes
Человек, который слишком много знал: 9 мифов об Альфреде Хичкоке Человек, который слишком много знал: 9 мифов об Альфреде Хичкоке

Правда и мифы о мастере саспенса

Вокруг света
История любви Вивьен Ли и Лоуренса Оливье: соперничество, которое разрушило брак История любви Вивьен Ли и Лоуренса Оливье: соперничество, которое разрушило брак

Они были одной из самых красивых пар Голливуда, но любовь не выдержала испытаний

Cosmopolitan
Сергей Шойгу: Неприлично не знать собственную страну Сергей Шойгу: Неприлично не знать собственную страну

Сергей Шойгу — об особенностях сибирской охоты и России

Вокруг света
5 привычек, опасных для влажных волос 5 привычек, опасных для влажных волос

Влажные локоны — самые уязвимые. Рассказываем, каких действий стоит избегать

РБК
Одомашнивание: новый цикл Одомашнивание: новый цикл

До конца нынешнего десятилетия произойдет очередная революция

Популярная механика
Вместо бюстгальтеров? Что такое тейпы и как их носить – рассказывает эксперт Вместо бюстгальтеров? Что такое тейпы и как их носить – рассказывает эксперт

Тейпирование – мини-революция в индустрии красоты

Cosmopolitan
Монарх под видом демократа Монарх под видом демократа

Октавиан Август не стал повторять ошибок Цезаря

Дилетант
Отряд Дамбл… Давора Отряд Дамбл… Давора

Как родители и дети решили отстоять директора школы

Русский репортер
Уставшие банкиры: почему многие банки оказались перед сложным выбором — или отказ от работы, или сдача лицензии? Уставшие банкиры: почему многие банки оказались перед сложным выбором — или отказ от работы, или сдача лицензии?

Российские банки в этом году продемонстрируют минимальный рост

Forbes
Король, отказавшийся от короны Король, отказавшийся от короны

Наиболее известным лидером крестоносцев считается Готфрид Бульонский

Дилетант
Вам пора всерьез задуматься (и позаботиться) о своих стопах Вам пора всерьез задуматься (и позаботиться) о своих стопах

Ключ к успеху находится у вас не в руках, а в ногах

GQ
Крепкий орешек Крепкий орешек

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

Vogue
Как выбрать гимнастический обруч Как выбрать гимнастический обруч

На что стоит обратить внимание, выбирая гимнастический обруч?

Cosmopolitan
В поисках утраченной промоакции В поисках утраченной промоакции

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

Maxim
Повестка Греты Тунберг: при чем здесь экономика Повестка Греты Тунберг: при чем здесь экономика

О том, как сделать дискуссию содержательной

Русский репортер
Российский паспорт советской бабушки. Почему новые инициативы Кремля по гражданству ни к чему не приведут Российский паспорт советской бабушки. Почему новые инициативы Кремля по гражданству ни к чему не приведут

Российская верхушка сделает всё, лишь бы ничего не менять в самой России

СНОБ
Боксёрские перчатки узника №136954 Боксёрские перчатки узника №136954

Саламо Арух, уроженец Салоники, был схвачен нацистами в мае 1943 года

Дилетант
Самая опасная бабочка: анатомия балисонга Самая опасная бабочка: анатомия балисонга

В советское время нож-бабочка ассоциировался с городскими хулиганами

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