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

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

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

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

Город Кёнигсберг (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 года

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

Дилетант
Точки зрения: почему мы не видим себя такими, какие мы есть Точки зрения: почему мы не видим себя такими, какие мы есть

Мы ищем себя в отражении или в размышлениях о себе

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

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

Наука и жизнь
Что происходит с мозгом, когда ты переживаешь из-за денег: 5 опасных последствий Что происходит с мозгом, когда ты переживаешь из-за денег: 5 опасных последствий

Может, после этих новостей ты изменишь свое отношение к деньгам

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

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

Наука и жизнь
Владельцы агентства «Аппетитный маркетинг» — о ресторанах и трендах Владельцы агентства «Аппетитный маркетинг» — о ресторанах и трендах

Интервью с главными PR-лицами российского ресторанного рынка

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

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

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

поручни, деньги и другие предметы, после которых нужно обязательно мыть руки

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

Это был лидер страны, у которого из средств общения осталась только мимика

Дилетант
6 типов неверности: какие из них мы можем простить? 6 типов неверности: какие из них мы можем простить?

Рано или поздно измена появляется в жизни 25% пар, которые считались крепкими

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

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

Наука и жизнь
4 шага к успешным диалогам в приложениях для знакомств (это проще, чем кажется) 4 шага к успешным диалогам в приложениях для знакомств (это проще, чем кажется)

Это просто, если делать все правильно

Playboy
Физика с разоблачением Физика с разоблачением

Опыты и фокусы: проверяем физику через 130 лет

Наука и жизнь
Suzuki Jimny. Возврат к эпохе «Самураев» Suzuki Jimny. Возврат к эпохе «Самураев»

На рынке появился новый Suzuki Jimny: не какой-то рестайлинговый, а all new

4x4 Club
Ну ты и дятел! Ну ты и дятел!

Невероятным достоинствам дятлов можно позавидовать

Вокруг света
В ЦОДД предложили ввести 50 км/ч в городе. К чему это приведет? В ЦОДД предложили ввести 50 км/ч в городе. К чему это приведет?

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

РБК
Уроки на экваторе Уроки на экваторе

Месяц в деревне в Кении глазами волонтера-учительницы из России

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

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

Популярная механика
Лена Горностаева Лена Горностаева

Какую часть мужского тела Лена Горностаева считает самой сексуальной?

Playboy
Зеленый шум Зеленый шум

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

Добрые советы
Гагарины Гагарины

Род князей Гагариных существует с XIII века, хотя положения добились не сразу

Дилетант
Виталий Лехциер: Гейдельбергский человек Виталий Лехциер: Гейдельбергский человек

Новые тексты Виталия Лехциера — поэта и эссеиста

СНОБ
Больше чем Джокер: блестящие роли лауреата Больше чем Джокер: блестящие роли лауреата

Помимо Джокера в фильмографии Хоакина Феникса есть и другие отличные роли

Cosmopolitan
Сальвадор Дали. Затворник Сальвадор Дали. Затворник

Иногда он закрывал глаза и шествовал по своему легендарному дворцу

Караван историй
Травма красоты: как любители идеальных женщин портят нам жизнь Травма красоты: как любители идеальных женщин портят нам жизнь

Кто и зачем внушает нам, что мы недостаточно красивы

Cosmopolitan
Петербургская писательница Ксения Букша — о гениальности «Отцов и детей» Тургенева, прозе Гюнтера Грасса и любимых русских поэтах Петербургская писательница Ксения Букша — о гениальности «Отцов и детей» Тургенева, прозе Гюнтера Грасса и любимых русских поэтах

Интервью с писательницей Ксенией Букшей

Esquire
Лучшие фильмы о любви с разницей в возрасте: 16 незабываемых картин Лучшие фильмы о любви с разницей в возрасте: 16 незабываемых картин

Говорят, возраст — это всего лишь число

Playboy
Как полюбить себя и свою нестандратную внешность: 4 истории реальных женщин Как полюбить себя и свою нестандратную внешность: 4 истории реальных женщин

Истории четырех героинь с внешними особенностями

Cosmopolitan
Юра Борисов Юра Борисов

Юре достаются самые брутальные роли. Особенно удаются огнестрельные профессии

Maxim
2+2. Как выпускницы мехмата сделали учебное приложение для детей и покорили азиатский рынок 2+2. Как выпускницы мехмата сделали учебное приложение для детей и покорили азиатский рынок

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

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