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

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

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

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

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

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

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

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

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

Операция «Мавзолей» Операция «Мавзолей»

Как из вождя мирового пролетариата, атеиста и сторонника кремации сделали мумию?

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

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

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

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

Наука и жизнь
Звезда родилась Звезда родилась

Всегда ли альтернативные роды — это лучшее решение для мамы и ребенка

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

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

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

Аист? Пеликан? Нет – китоглав!

National Geographic
Картонная инженерия Даниеля Агдага Картонная инженерия Даниеля Агдага

Австралийский художник Даниель Агдаг делает скульптуры из картона

Популярная механика
Амиран Муцоев: Самые успешные парки в мире находятся внутри городов Амиран Муцоев: Самые успешные парки в мире находятся внутри городов

Интервью с создателем тематического парка «Остров мечты»

СНОБ
Сети 6G позволят создать киборгов Сети 6G позволят создать киборгов

Следующий, финальный шаг — терагерцовая связь

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

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

Psychologies
Вечный Олег Вечный Олег

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

Esquire
Зловредные мертвецы: 15 легендарных завещаний Зловредные мертвецы: 15 легендарных завещаний

Мы решили изучить лучшие образцы остроумных завещаний

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

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

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

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

CHIP
Бронетехника Гражданской войны: собственные разработки Белой гвардии Бронетехника Гражданской войны: собственные разработки Белой гвардии

Бронетехника Белой гвардии во времена Гражданской войны

Популярная механика
Общественную дипломатию предлагают подчинить МИДу Общественную дипломатию предлагают подчинить МИДу

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

РБК
Микробные фармацевты внутри нас Микробные фармацевты внутри нас

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

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

Наши люди наконец стали регулярно красоваться в зарубежных хит-парадах

Maxim
Одна вокруг света. Как трижды проехать до иранской границы и обратно Одна вокруг света. Как трижды проехать до иранской границы и обратно

Ирина Сидоренко пробралась через заснеженный перевал и посетила крепость Баязет

Forbes
Горячий, бесплатный, чей? Горячий, бесплатный, чей?

Во что обойдутся бесплатные школьные обеды

Огонёк
Электронные сигареты Электронные сигареты

Электронные сигареты, вейпы – все "за" и "против"

Здоровье
Определение бога в философии Спинозы Определение бога в философии Спинозы

Книга Энтони Готтлиба «Мечта о просвещении. Рассвет философии нового времени»

СНОБ
Дневники Берлинале-2020: Джонни Депп борется с экологическими преступниками, а итальянский художник страдает Дневники Берлинале-2020: Джонни Депп борется с экологическими преступниками, а итальянский художник страдает

Пролетели первые дни с начала Берлинского кинофестиваля

Forbes
Коронавирус, свиной грипп и другие болезни: так ли опасна новая эпидемия Коронавирус, свиной грипп и другие болезни: так ли опасна новая эпидемия

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

Популярная механика

Повесть Дарьи Дацук "Голос" о девочке, пережившей террористический акт

Esquire
Центробанк отстал от жизни: почему он продолжает зажимать экономику вопреки своим заявлениям Центробанк отстал от жизни: почему он продолжает зажимать экономику вопреки своим заявлениям

Банк России снизил ставку до 6%, но это все еще слишком высокая ставка

Forbes
Транзит по-сталински Транзит по-сталински

Как за полгода до смерти Сталин затеял радикальную реформу управления

Огонёк
«Я танцевала с Фиделем Кастро». Жители пансионата ветеранов труда о своей жизни «Я танцевала с Фиделем Кастро». Жители пансионата ветеранов труда о своей жизни

Жизнь в доме престарелых многим представляется унылой и скучной, но это не так

СНОБ
«Мир стал более жесток к женщинам». Главная писательница Израиля о том, почему быть хорошей матерью уже недостаточно «Мир стал более жесток к женщинам». Главная писательница Израиля о том, почему быть хорошей матерью уже недостаточно

Израильская писательница №1 об антисемитизме, косых взглядах и любви к детям

Forbes
Как создавали костюмы к «Ирландцу» Как создавали костюмы к «Ирландцу»

«Ирландец» Мартина Скорсезе — учебник истории мужской моды

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