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

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

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

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

Город Кёнигсберг (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 вещей, за которые мужчине не должно быть стыдно

Чего мужчина не должен стыдиться?

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

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

Наука и жизнь
17 главных заграничных песен о России 17 главных заграничных песен о России

Все самые знаменитые песни о России, придуманные иностранными артистами

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

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

Наука и жизнь
Куртка из бананов, сумка из грибов: как растения превращаются в одежду Куртка из бананов, сумка из грибов: как растения превращаются в одежду

Каким образом получают экоматериалы и какие бренды их применяют

РБК
Чёрный передел: версия 1939 года Чёрный передел: версия 1939 года

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

Дилетант
Семиместный Mitsubishi Outlander. Ты бы меня ещё о внуках спросил… Семиместный Mitsubishi Outlander. Ты бы меня ещё о внуках спросил…

Mitsubishi Outlander получил очередную порцию обновлений и третий ряд сидений

4x4 Club
Алюминиевый век Алюминиевый век

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

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

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

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

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

Наука и жизнь
Пот, кровь, слёзы и крест Пот, кровь, слёзы и крест

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

Дилетант
Цой жив Цой жив

Виктор Цой погиб в автокатастрофе в Юрмале 15 августа 1990 года

Esquire
Шагреневая кожа Шагреневая кожа

Как же худеть, чтобы не пострадала кожа

Худеем правильно
Дело Дело

Отрывки из книг Кирилла Серебренникова и Алексея Малобродского

СНОБ
Кристин Лёнинс: Птица в клетке Кристин Лёнинс: Птица в клетке

Йоханнес Бетцлер — главный герой книги Кристин Лёнинс «Птица в клетке»

СНОБ
Ассорти для героя Ассорти для героя

Большой шоколадный квест по Бельгии

Вокруг света
Уйти нельзя остаться: чего хотят россияне от Путина после 2024 года Уйти нельзя остаться: чего хотят россияне от Путина после 2024 года

Россияне боятся ухода Путина в отставку. И не напрасно

СНОБ
Можно ли приручить землетрясение? Можно ли приручить землетрясение?

Что мы знаем о землетрясениях?

Наука и жизнь
История жизни гениального инженера-электрика ростом 130 см История жизни гениального инженера-электрика ростом 130 см

Чарльз Протей Штейнмец долгие годы возглавлял General Electric

Maxim
Попрощались: предсмертные посты звезд в соцсетях – от Началовой до Брайанта Попрощались: предсмертные посты звезд в соцсетях – от Началовой до Брайанта

Что хотели сказать этому миру знаменитости, чьи жизни неожиданно оборвались

Cosmopolitan
Куда все плывет: как круизные суда начали развивать экотехнологии Куда все плывет: как круизные суда начали развивать экотехнологии

Как мода на круизные путешествия угрожает жизни

Forbes
8 скандальных шуток политиков 8 скандальных шуток политиков

Случаи, когда за шутку одного человека приходилось краснеть всей стране

Maxim
«ПМ» тестирует легендарный Desert Eagle «ПМ» тестирует легендарный Desert Eagle

«ПМ» не используют ни в одном подразделении ни одной силовой структуры мира

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

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

Psychologies
Плохая девочка Билли Айлиш: как нарушить все правила и заработать $8 млн к 18 годам Плохая девочка Билли Айлиш: как нарушить все правила и заработать $8 млн к 18 годам

Музыкальный критик Антон Макарский разбирается с феноменом Билли Айлиш

Forbes
Зачем нужна научная фантастика и почему она актуальна сейчас Зачем нужна научная фантастика и почему она актуальна сейчас

В наш век научная фантастика может показаться забытым жанром, но это не так

РБК
Скорпионы — соблазнительницы, Девы — умницы: какому качеству завидуют окружающие Скорпионы — соблазнительницы, Девы — умницы: какому качеству завидуют окружающие

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

Cosmopolitan
Почему нельзя регулярно менять пароли к интернет-аккаунтам: рекомендации экспертов и софт Почему нельзя регулярно менять пароли к интернет-аккаунтам: рекомендации экспертов и софт

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

CHIP
Эмилия Кларк: горячие фото матери драконов из «Игры престолов» Эмилия Кларк: горячие фото матери драконов из «Игры престолов»

Перед тобой Дейнерис во всей красе

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