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

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

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

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

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

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

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

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

Анна Седокова Анна Седокова

Наверное, она уже привыкла к эпитетам «горячая», «аппетитная», «сочная»

Playboy
Самый влюбчивый знак зодиака - кто он? Самый влюбчивый знак зодиака - кто он?

Читай наш рейтинг самых влюбчивых знаков!

Cosmopolitan
Археология в 2019 году: несколько интересных находок Археология в 2019 году: несколько интересных находок

Интересные археологические находки 2019 года

Наука и жизнь
Каково это — побывать на миланской неделе моды, не имея никакого отношения к миру моды Каково это — побывать на миланской неделе моды, не имея никакого отношения к миру моды

Мир моды — он правда такой загадочный?

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

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

Наука и жизнь
Левон Оганезов. Концертмейстер Левон Оганезов. Концертмейстер

Я попал в Мосэстраду в девятнадцать и прослужил сорок один год

Караван историй
Мой Сталинград Мой Сталинград

Когда началась война, я была студенткой мединститута

Наука и жизнь
«Вся страна знает, что я курю травку»: как наркотики разрушили жизнь Гуфа «Вся страна знает, что я курю травку»: как наркотики разрушили жизнь Гуфа

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

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

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

Наука и жизнь
Переехать, жениться и не заводить детей: 9 парадоксальных научных советов, как стать счастливым Переехать, жениться и не заводить детей: 9 парадоксальных научных советов, как стать счастливым

Как поддерживать уровень удовольствия от жизни

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

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

Наука и жизнь
Крестовый психоз бедноты Крестовый психоз бедноты

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

Дилетант
Тест: Чего вы хотите на самом деле, когда мечтаете о деньгах? Тест: Чего вы хотите на самом деле, когда мечтаете о деньгах?

А какая у вас мотивация зарабатывать? Пройдя тест, вы узнаете ответ

Psychologies
Диетические хлебцы для похудения: польза и вред Диетические хлебцы для похудения: польза и вред

Хлеб и диета — несовместимые понятия?

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

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

Вокруг света
Приставка — корень Приставка — корень

Пока мы читали книги и обсуждали фильмы, видеоигры стали новым видом искусства

GQ
Десять значимых событий 2022 Десять значимых событий 2022

Что произошло в науке за 2022 год

Наука и жизнь
Смена вех Смена вех

Апартаменты, расположенные в переоборудованном корпусе бывшей табачной фабрики

SALON-Interior
Поддержать своих Поддержать своих

Рак был всегда: о нем было известно и древнеегипетским врачам, и Гиппократу

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

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

РБК
Suzuki Jimny. Возврат к эпохе «Самураев» Suzuki Jimny. Возврат к эпохе «Самураев»

На рынке появился новый Suzuki Jimny: не какой-то рестайлинговый, а all new

4x4 Club
История Page Six — главного ресурса сплетен и инсайдов в США История Page Six — главного ресурса сплетен и инсайдов в США

Page Six — влиятельный ресурс, который задал правила игры более 40 лет назад

Esquire
Синяк – не пустяк Синяк – не пустяк

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

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

Есть два типа людей: одни с пистолетом, другие копают

Популярная механика
Кто не без греха? Кто не без греха?

Пора узнать врагов в лицо – и выяснить, как с ними бороться

Cosmopolitan
#инструктаж: как снять квартиру за рубежом #инструктаж: как снять квартиру за рубежом

Несколько советов, как искать жилье за границей, от Австрии до Японии

РБК
Королева против: самые громкие скандалы Елизаветы II с членами семьи Королева против: самые громкие скандалы Елизаветы II с членами семьи

Отношения внутри королевской семьи никогда не были простыми

Cosmopolitan
Как пользоваться часами — лайфхаки, о которых вы не знали Как пользоваться часами — лайфхаки, о которых вы не знали

Как правильно пользоваться механическими часами и как их носить

Cosmopolitan
Доисторическая ископаемая слизь удивила ученых: гость из прошлого Доисторическая ископаемая слизь удивила ученых: гость из прошлого

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

Популярная механика
Кейт vs Меган: кто станет «Королевой сердец» Кейт vs Меган: кто станет «Королевой сердец»

Война в благородном семействе может разгореться нешуточная

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