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

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

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

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

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

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

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

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

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

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

Наука и жизнь
Эпизод шестой: Шантаж и римский вопрос Эпизод шестой: Шантаж и римский вопрос

Папа ошибается с изданием Библии и шантажирует премьер-министра Италии

Esquire
Стая товарищей Стая товарищей

Повесть о том, что значит быть собакой, и о том, что значит быть человеком

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

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

Популярная механика
Альянсы и союзы Альянсы и союзы

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

Дилетант
Короли криптобиржи: как получить доходность 143% на сделках с цифровыми валютами, сомневаясь во всем Короли криптобиржи: как получить доходность 143% на сделках с цифровыми валютами, сомневаясь во всем

Как IT-предприниматели увлеклись блокчейн-технологиями и заработали $100 млн

Forbes
Техпарад Техпарад

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

Популярная механика
Как заработать 120 млн рублей на разряженных телефонах. Бизнес-план «Бери заряд!» Как заработать 120 млн рублей на разряженных телефонах. Бизнес-план «Бери заряд!»

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

Forbes
Алюминиевый век Алюминиевый век

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

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

Кто из российских персон и компаний претендует на антипремию «Сексист года»

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

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

Наука и жизнь
Черная водолазка. Отрывок из книги Черная водолазка. Отрывок из книги

«Сноб» публикует первые главы сборника рассказов журналистки Полины Санаевой

СНОБ
Строганина по-немецки Строганина по-немецки

В Германии любят тартар из сырого мяса

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

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

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

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

Дилетант
Их союз выдержал испытание Их союз выдержал испытание

Мы можем дружить годами и семьями, а потом происходит что-то и связь обрывается

Psychologies
Настоящий полковник Настоящий полковник

Строительный и вещевой рынки сделали Владимира Лещикова миллиардером

Forbes
Близкие, которых мы выбираем Близкие, которых мы выбираем

Друзья-товарищи – опоры нашей жизни, в гораздо большей степени, чем мы сознаем

Psychologies
Ее светлость Ее светлость

Эрика проделала длинный путь из закарпатской деревушки до этой волнующей обложки

Maxim
Код независимости Код независимости

Александр Лукашенко пытается снизить влияние России на Белоруссию

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

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

Cosmopolitan
7 способов снять тревогу без успокоительных 7 способов снять тревогу без успокоительных

Мы можем справиться с беспокойством, не прибегая к помощи лекарств

Psychologies
Бабочка огня: откуда пришли женщины «янь» Бабочка огня: откуда пришли женщины «янь»

Есть женщины, из которых энергия бьет ключом

Psychologies
Территории кормления. Захочет ли президент создать новую опричнину Территории кормления. Захочет ли президент создать новую опричнину

Предложения в Конституцию, способные заинтересовать власть

СНОБ
Три возраста красоты Три возраста красоты

Увы, эликсира вечной молодости пока не существует

Лиза
«В НАСА никому нет дела до твоего пола». Как астронавт Анна Фишер стала одной из первых женщин, полетевших в космос «В НАСА никому нет дела до твоего пола». Как астронавт Анна Фишер стала одной из первых женщин, полетевших в космос

Анна Фишер о том, почему ключевые посты в управлении НАСА заняли именно женщины

Forbes
5 самых грозных боевых топоров 5 самых грозных боевых топоров

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

Популярная механика
Как избежать конфликтов из-за наследства. 5 советов Как избежать конфликтов из-за наследства. 5 советов

Реальные кейсы и несколько вариантов разрешения конфликтов вокруг наследства

СНОБ
Большое весеннее похудение: как знаки зодиака сбрасывают вес к лету Большое весеннее похудение: как знаки зодиака сбрасывают вес к лету

Магический шар рассказывает, как знаки зодиака сбрасывают вес к лету

Cosmopolitan
Суперстар Суперстар

В итальянской деревне Ачароли живут до ста лет

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