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

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

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

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

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

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

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

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

Гены под влиянием Гены под влиянием

Нобелевская премия 2024: открытие микроРНК и её влияние на регуляцию генов

Наука и жизнь
Михаил Мишустин и его семья заработали около $36 миллионов в инвесткомпании UFG. Премьер работал там в 2008-2010 годах Михаил Мишустин и его семья заработали около $36 миллионов в инвесткомпании UFG. Премьер работал там в 2008-2010 годах

Мишустин перешел в бизнес с госслужбы и стал владельцем 25% в фондах UFG

Esquire
Наука в фантастике: эпизоды истории Наука в фантастике: эпизоды истории

Основы советской фантастики закладывались ещё до революции

Наука и жизнь
Пищевые добавки с омега-3: как, зачем и кому их принимать Пищевые добавки с омега-3: как, зачем и кому их принимать

Так ли полезны пищевые добавки с омега-3, как мы думаем?

Psychologies
Предисловие Предисловие

В чем особенности процессов колонизации и как превратить мечту в перспективу

Вокруг света
Александр Белькович: Надо искать вкус в простоте Александр Белькович: Надо искать вкус в простоте

Разговор с обаятельным и остроумным теле-поваром Александром Бельковичем

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

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

Esquire
Царь-пушка Царь-пушка

По случаю выхода фильма «Калашников» мы решили разобрать Калашникова

Maxim
Ойинкан Брейтуэйт: Моя сестрица — серийная убийца Ойинкан Брейтуэйт: Моя сестрица — серийная убийца

Книга «Моя сестрица — серийная убийца» вошла в лонг-лист Букеровской премии

СНОБ
Анна Дубровская: «Справедливости в театре не существует» Анна Дубровская: «Справедливости в театре не существует»

После схода ледника и пропажи съемочной группы мне приснился Бодров...

Караван историй
На трибунах становится тише На трибунах становится тише

Воспоминания о противоречивом человеке Юрии Лужкове

Tatler
Мистер конгениальность. Где искать профессиональных менторов и наставников Мистер конгениальность. Где искать профессиональных менторов и наставников

Основатель U Skillz рассказывает, где и чему учиться у конгениальных людей

Forbes
Амазонки из Воронежа Амазонки из Воронежа

О чем рассказали женские захоронения с оружием

Огонёк
Лучше черной пятницы. Как за 100 евро купить оригиналы картин самых модных и дорогих художников Лучше черной пятницы. Как за 100 евро купить оригиналы картин самых модных и дорогих художников

Не обязательно платить тысячи, а то и сотни тысяч долларов за искусство

Forbes
Анна Плетнева: Анна Плетнева:

Анна Плетнева - о том, как она находит баланс между работой и личной жизнью

Cosmopolitan
Влияние Меган: жена внука королевы подала на развод и захотела уехать в Канаду Влияние Меган: жена внука королевы подала на развод и захотела уехать в Канаду

Старший внук Елизаветы II расстался со своей супругой Отэм Келли

Cosmopolitan
Два бриллианта в три карата: у кого из звезд были самые дорогие  украшения на «Оскаре-2020» Два бриллианта в три карата: у кого из звезд были самые дорогие  украшения на «Оскаре-2020»

На 92-й церемонии вручения наград Американской академии бал правили бриллианты

Forbes
«С возрастом уходит эгоизм» «С возрастом уходит эгоизм»

Почему режиссер Анатолий Васильев выбирает педагогику

Огонёк
Где кататься на горных лыжах в 2020 году Где кататься на горных лыжах в 2020 году

Курорты для любителей экстремальной езды и новичков

GQ
Пять самых дальнобойных супер-винтовок в мире Пять самых дальнобойных супер-винтовок в мире

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

Популярная механика
Хорошая девочка Лида Хорошая девочка Лида

Директор детского хосписа Лида Мониава и ее добрые дела

Tatler
Cекс-эрудит, колесо страсти и еще 28 самых горячих секс-игр Cекс-эрудит, колесо страсти и еще 28 самых горячих секс-игр

Секс — это весело!

Cosmopolitan
В ЦОДД предложили ввести 50 км/ч в городе. К чему это приведет? В ЦОДД предложили ввести 50 км/ч в городе. К чему это приведет?

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

РБК
Екатерина Климова: Сейчас чувствую себя счастливой чаще, чем в юности Екатерина Климова: Сейчас чувствую себя счастливой чаще, чем в юности

Где Климова — там улыбки, движение и жесткий тайминг

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

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

Playboy
Как я живу с булимией Как я живу с булимией

Наша героиня рассказывает о непростом пути к себе настоящей

Домашний Очаг
«Гедонист наслаждается жизнью во всех её проявлениях» «Гедонист наслаждается жизнью во всех её проявлениях»

Чтобы упорядочить отношения с едой и похудеть, станьте гедонистом

Худеем правильно
5 сериалов для тех, кто мечтает работать в модной индустрии 5 сериалов для тех, кто мечтает работать в модной индустрии

О самых интересных сериалах, рассказывающих о модной индустрии

Cosmopolitan
Ликвидность искусства – миф: акции оборачиваются быстрее Пикассо Ликвидность искусства – миф: акции оборачиваются быстрее Пикассо

Арт-дилер Кенни Шахтер рассказывает, как инстаграм меняет арт-рынок

Forbes
Что стало основой для костюмов в «Маленьких женщинах» Что стало основой для костюмов в «Маленьких женщинах»

Новая экранизация романа Луизы Олкотт выкидывает сразу два козыря из рукава

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