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

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

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

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

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

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

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

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

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

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

Наука и жизнь
Куратор рубильника Рунета: что известно о кандидате на пост главы Роскомнадзора Куратор рубильника Рунета: что известно о кандидате на пост главы Роскомнадзора

Кто сменит главу Роскомнадзора?

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

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

Наука и жизнь
8 частей тела, которые ты моешь недостаточно тщательно (угадали?) 8 частей тела, которые ты моешь недостаточно тщательно (угадали?)

Ты не грязнуля, мы все так делаем!

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

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

Наука и жизнь
«Достигли точки перегиба»: что ждет Россию после проигранного суда с ЮКОСом на $50 млрд «Достигли точки перегиба»: что ждет Россию после проигранного суда с ЮКОСом на $50 млрд

Апелляционный суд в присудил экс-акционерам ЮКОСа $50 млрд компенсации от России

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

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

Наука и жизнь
Мортенс А. Стрекнесс: Времена моря Мортенс А. Стрекнесс: Времена моря

Начало романа норвежского писателя Мортенса Андреаса Стрекнесса

СНОБ
От чего умер Ленин? От чего умер Ленин?

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

Дилетант
Надежда Михалкова о фильме “Лед-2”, отношениях с детьми и премии “Оскар” Надежда Михалкова о фильме “Лед-2”, отношениях с детьми и премии “Оскар”

Актриса Надежда Михалкова о том, чего не хватает российскому кинематографу

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

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

Наука и жизнь
Не царственное чувство. Осталась ли магия в портретах Владимира Путина Не царственное чувство. Осталась ли магия в портретах Владимира Путина

Портрет правителя — серьезная штука

СНОБ
Что общего между гвоздём и Парижем? Что общего между гвоздём и Парижем?

Откуда появились выражение «гвоздя не хватило»?

Наука и жизнь
«Придут и затопчут»: почему стартапы не выдерживают конкуренции с «Яндексом», Mail.Ru Group и Сбербанком «Придут и затопчут»: почему стартапы не выдерживают конкуренции с «Яндексом», Mail.Ru Group и Сбербанком

Почему конкурировать с гигантами оказалось не под силу независимым игрокам?

Forbes
В зиму на выходные В зиму на выходные

Зимой мне очень хочется зимы — настоящей, морозной и снежной

Наука и жизнь
Роберт Патинссон: «Моя главная слабость – это пиво» Роберт Патинссон: «Моя главная слабость – это пиво»

Какие у Роберта Патинссона дальнейшие планы и легко ли ему было быть танцором

GQ
Земля переезжает Земля переезжает

Когда Солнце начнет затухать, корабль «Земля» уже прибудет к новой звезде

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

Хозяева этого дома в Алма–Аты — большая дружная семья

SALON-Interior
Завтра была война… Завтра была война…

Резкий поворот во внешней политике Советского Союза

Дилетант
Калибрище: как немцы построили грозную и бестолковую пушку Калибрище: как немцы построили грозную и бестолковую пушку

"Дора" - впечатляющая царь-пушка на железнодорожном ходу невиданных размеров

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

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

Cosmopolitan
Самый большой секрет на Уолл-стрит: как мормонская церковь в тайне создала фонд на $100 млрд Самый большой секрет на Уолл-стрит: как мормонская церковь в тайне создала фонд на $100 млрд

Мормонская церковь в США в тайне от всех создала один крупный инвестфонд

Forbes
Как работает огнеметная система «Солнцепек» Как работает огнеметная система «Солнцепек»

«Солнцепек» тяжелая огнеметная система, обладающая незаурядной мощью

Популярная механика
Погреба с вином Путина: где хранятся личная коллекция российского президента Погреба с вином Путина: где хранятся личная коллекция российского президента

Винные погреба в молдавском городе Криково входят в число самых больших в мире

Forbes
Король, отказавшийся от короны Король, отказавшийся от короны

Наиболее известным лидером крестоносцев считается Готфрид Бульонский

Дилетант
Как уменьшить бёдра и ягодицы в домашних условиях: лучшие лайфхаки Как уменьшить бёдра и ягодицы в домашних условиях: лучшие лайфхаки

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

Cosmopolitan
По следам детских болезней По следам детских болезней

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

Здоровье
Тест-драйв БМП-3: Тест-драйв БМП-3:

БМП-3 принимала участие в парадах и демонстрациях перед специалистами и публикой

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

Специально для «Сноба» писатель и журналист Алексей Беляков написал рассказ

СНОБ
Крестовый психоз бедноты Крестовый психоз бедноты

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

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