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

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

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

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

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

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

Наука и жизнь
Успокоительное прошлое: почему нас никак не отпустит ностальгия? Успокоительное прошлое: почему нас никак не отпустит ностальгия?

Почему в 2010-е общество пережило XX век и что заставляет нас возвращаться

РБК
Большая ракета Илона Маска Большая ракета Илона Маска

Сверхтяжелая ракета Big Falcon Rocket готовится вытеснить все прошлые разработки

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

Надежда Оболенцева о том, стоит ли делить людей на сильных и слабых

Grazia
Летающий мопед Летающий мопед

Автожиры: полет над вулканом и не только.

Популярная механика
Микробные фармацевты внутри нас Микробные фармацевты внутри нас

Микробиом может влиять на многие важнейшие процессы в организме хозяина

Наука и жизнь
Краткий курс перезагрузки Краткий курс перезагрузки

Курская область стремится к лидерству по инвестиционной привлекательности

РБК
Близорукий мозг: почему мы зря обесцениваем свое будущее Близорукий мозг: почему мы зря обесцениваем свое будущее

Фрагмент из книги «Сила эмоций» издательства «Манн, Иванов и Фербер»

Forbes
От Оливье до оливье От Оливье до оливье

Здание по адресу улица Неглинная, 29/14 имеет богатое прошлое

Дилетант
Не делай так: 12 ошибок в стиле, которые прибавят лишних 10–20 лет Не делай так: 12 ошибок в стиле, которые прибавят лишних 10–20 лет

Составили для тебя топ того, что прибавит возраст кому угодно

Cosmopolitan
Идлибский капкан Идлибский капкан

Как «заклятые» друзья Россия и Турция оказались на грани военного конфликта

Эксперт
Великое злодеяние: психология геноцида Великое злодеяние: психология геноцида

Что заставляет один народ истреблять другой?

Naked Science
Наедине с волками Наедине с волками

Тридцать часов со стаей полярных волков

National Geographic
Стратосферный турист Стратосферный турист

Звездное небо над головой и далекая Земля внизу – вид из стратосферы

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

Эти 12 кроссоверов большинство из вас увидит впервые

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

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

GQ
Как расизм и дискриминация в детстве Тима Кука повлияли на бизнес Apple Как расизм и дискриминация в детстве Тима Кука повлияли на бизнес Apple

Тим Кук — человек, который рискнул заменить незаменимого

Forbes
Эгоистка и грубиянка. Как общественные ожидания развивают у девочек тревожность Эгоистка и грубиянка. Как общественные ожидания развивают у девочек тревожность

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

Forbes
Как познакомиться с новым мужем Как познакомиться с новым мужем

Технику пикапа – не на одну ночь, а на долгую счастливую жизнь

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

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

Cosmopolitan
Акции в небесах, нефть на дне Акции в небесах, нефть на дне

Мировые фондовые рынки решили, что вопрос коронавируса исчерпан

Эксперт
Зачем бактерии-каннибалы уничтожают сородичей Зачем бактерии-каннибалы уничтожают сородичей

«Аллолизис» — что это за явление?

National Geographic
Нежная промзона. Как женщины делают карьеру в тяжелой промышленности Нежная промзона. Как женщины делают карьеру в тяжелой промышленности

Женщин на позициях среднего и высшего уровня в российской промышленности — 30%

Forbes
Эмоциональная трезвость. Как грамотно оценить свои силы в работе Эмоциональная трезвость. Как грамотно оценить свои силы в работе

В бизнесе женщине довольно часто приходится защищать свою правду и интересы

Forbes
Залог успеха Залог успеха

Дизайнер Екатерина Барашева оформила интерьер апартаментов с эффектными приёмами

SALON-Interior
Оказывается, стресс на работе может быть полезен: 7 доказательств Оказывается, стресс на работе может быть полезен: 7 доказательств

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

Playboy
Конституционная неопределенность Конституционная неопределенность

Можно ли усовершенствовать Основной закон страны по закону и здравому смыслу

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

У авиакомпаний появился новый тренд: они отказываются от привычных баров

Forbes
Жизнь без насилия (страха, боли, ненависти) Жизнь без насилия (страха, боли, ненависти)

Как быть, если вы столкнулись с насилием в отношениях? Где искать помощи?

Домашний Очаг
Как пользоваться акриловой пудрой для укрепления ногтей Как пользоваться акриловой пудрой для укрепления ногтей

Тонкие поврежденные ногти быстро ломаются и не держат маникюр?

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