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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Мода на страхование частей тела появилась в Голливуде в начале 80-х годов

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

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

Наука и жизнь
Как найти новое поколение антибиотиков — ответ получен Как найти новое поколение антибиотиков — ответ получен

Нам необходимы новые антибиотики, ученые их найдут — это только вопрос времени

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

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

Дилетант
«Хищные птицы: Потрясающая история Харли Квинн» как работа над ошибками «Хищные птицы: Потрясающая история Харли Квинн» как работа над ошибками

Условное продолжение провального «Отряда самоубийц» оказалось очень даже ничего

GQ
Грозовой реактор Грозовой реактор

Физики обнаружили, что грозы порождают в атмосфере позитроны и изотопы

Наука и жизнь
Сладких снов! Сладких снов!

Треть жизни мы проводим во сне, поэтому качество постельного белья очень важно

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

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

Наука и жизнь
«Я рисковый человек: лечу на край света без оглядки!» «Я рисковый человек: лечу на край света без оглядки!»

Актриса Наталья Рудова дебютирует в роли телеведущей реалити «Место под солнцем»

OK!
Русские в Берлине весной 1945 г. Русские в Берлине весной 1945 г.

События Великой Отечественной войны в воспоминаниях и рассказах участников боёв

Наука и жизнь
Управляющий партнер UFG рассказала о доходах Мишустина и его семьи от бизнеса Управляющий партнер UFG рассказала о доходах Мишустина и его семьи от бизнеса

Сколько зарабатывал Михаил Мишустин, когда он ушел на госслужбу

Forbes
Каменные джунгли Каменные джунгли

Мальдивцы стараются спасти свои леса от глобального потепления, сажая кораллы

Вокруг света
Смерть сына, секс-скандал и самолеты: захватывающая биография Джона Траволты Смерть сына, секс-скандал и самолеты: захватывающая биография Джона Траволты

По биографии Джона Траволты можно снять необычное кино

Cosmopolitan
Песнь льда и пломбира Песнь льда и пломбира

Лиза Туктамышева – просто красивая девушка, которая любит мороженое!

Maxim
Безнадежный тупик: почему страна богатеет, а доходы граждан падают Безнадежный тупик: почему страна богатеет, а доходы граждан падают

Госбюджет России в превосходной форме, а вот в экономике все неладно

Forbes
Цивилизация Цивилизация

Они одними из первых освоили инженерию, завели армию, монархию и дипломатию

Вокруг света
Почему Джей Ло и Шакира отказались от многомиллионных гонораров за шоу на Супербоуле Почему Джей Ло и Шакира отказались от многомиллионных гонораров за шоу на Супербоуле

Знаменитые певицы бесплатно выступили в перерыве Супербоула

Forbes
Потому что любим Потому что любим

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

Лиза
Завербованная страна. О трудностях переходного периода в осажденной крепости Завербованная страна. О трудностях переходного периода в осажденной крепости

Как заканчивать холодную войну и то делать с долгами по ЮКОСу и по «Боингу»?

СНОБ
Анти-Грета: в Германии появилась противница климатического алармизма Анти-Грета: в Германии появилась противница климатического алармизма

Наоми Зайбт, в противоположность Грете Тунберг, отрицает серьезность кризиса

РБК
Как выдать ремонт за лофт Как выдать ремонт за лофт

Как жить и принимать гостей в квартире с недоделанным ремонтом?

Maxim
Дело к войне? Эксперты о том, чем кончится обострение ситуации в Идлибе Дело к войне? Эксперты о том, чем кончится обострение ситуации в Идлибе

Чем грозит развитие конфликта в Идлибе, и о возможных выходах из ситуации

СНОБ
«Дорогие штучки»: десять самых дорогих картин из коллекций миллиардеров мира «Дорогие штучки»: десять самых дорогих картин из коллекций миллиардеров мира

Кому по карману бессмертные и почти бесценные творения мастеров?

Forbes
Закон и порядок Закон и порядок

Потомственный юрист показала квартиру своей семьи на Котельнической набережной

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

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

Forbes
Когда я стану кошкой. Как общаться с подростком, который ничего не хочет и вот-вот разрушит семью Когда я стану кошкой. Как общаться с подростком, который ничего не хочет и вот-вот разрушит семью

И в психологии есть чему поучиться у братьев наших меньших

СНОБ
Как заработать на ЗД принтере: 5 лучших способов Как заработать на ЗД принтере: 5 лучших способов

3D-принтер вполне можно назвать универсальным инструментом

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