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

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

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

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

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

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

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

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

Анна Седокова Анна Седокова

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

Playboy
Кристофер Бакли: Охотник за судьями Кристофер Бакли: Охотник за судьями

«Сноб» публикует первую главу романа

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

Кто самый великий физик?

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

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

Популярная механика
Алюминиевый век Алюминиевый век

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

Наука и жизнь
Розовая пантера Розовая пантера

Кристина Челестино балансирует между дизайном и картинками для Instagram

AD
От чего умер Ленин? От чего умер Ленин?

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

Дилетант
Как помыть СВЧ-печь быстро и легко Как помыть СВЧ-печь быстро и легко

Несколько советов о том, как помыть микроволновку подручными средствами

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

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

Наука и жизнь
Приговор из 1937 года: о чем говорит жестокость по делу «Сети» Приговор из 1937 года: о чем говорит жестокость по делу «Сети»

Приговор фигурантов дела «Сети» напоминает приговоры сталинских времен

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

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

Наука и жизнь
Антиутопия в бирюзовых тонах Антиутопия в бирюзовых тонах

Если «бирюзовый» стиль управления так хорош, почему он не распространен?

Psychologies
Алмазные решения для квантовых задач Алмазные решения для квантовых задач

За синтетическими алмазами будущее!

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

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

РБК
Наука побеждать Наука побеждать

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

Дилетант
10 знаменитостей, которых опасно искать в интернете 10 знаменитостей, которых опасно искать в интернете

Рассказываем, кого следует искать с наибольшей осторожностью

РБК
Исчезающая пища Исчезающая пища

К середине XXI века бананы и кофе снова могут оказаться деликатесами

Вокруг света
Ловушки мышления. Почему проблемы с деньгами возникают даже у умных людей Ловушки мышления. Почему проблемы с деньгами возникают даже у умных людей

Какие иллюзии мешают вам жить и какие существуют способы противостоять им

Forbes
Из Дубая – на Марс Из Дубая – на Марс

Оригинальная российская технология конструкторов пробивает себе дорогу

Популярная механика
Матери-героини! Самые эффектные выходы звёзд сразу после родов Матери-героини! Самые эффектные выходы звёзд сразу после родов

После рождения ребёнка эти женщины не стали отсиживаться дома

Cosmopolitan
Вслед за косачами Вслед за косачами

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

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

С чего началась и чем завершилась самая романтическая история прошлого века

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

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

Cosmopolitan
Блондинка и ее законы Блондинка и ее законы

Вера Брежнева – о стереотипах, критике, домашнем хозяйстве и отношениях с мужем

Cosmopolitan
Воспоминания внука Константина Рокоссовского о деде Воспоминания внука Константина Рокоссовского о деде

Журналистка Ариадна Рокоссовская написала книгу «Утро после Победы»

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

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

Playboy
Ликвидность искусства – миф: акции оборачиваются быстрее Пикассо Ликвидность искусства – миф: акции оборачиваются быстрее Пикассо

Арт-дилер Кенни Шахтер рассказывает, как инстаграм меняет арт-рынок

Forbes
Реальный Ретт Батлер бил жену: как Митчелл сделала из мужа-абьюзера героя романа Реальный Ретт Батлер бил жену: как Митчелл сделала из мужа-абьюзера героя романа

Она написала красивую сказку об идеальном мужчине

Cosmopolitan
Женщины предпочитают бородатых? Женщины предпочитают бородатых?

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

Psychologies
Летчики, солдаты, геймеры: как работают операторы БПЛА Летчики, солдаты, геймеры: как работают операторы БПЛА

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

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