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

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

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

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

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

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

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

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

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

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

Наука и жизнь
«У меня ничего не получится»: 5 шагов, чтобы изменить будущее «У меня ничего не получится»: 5 шагов, чтобы изменить будущее

Многие люди не уверены в собственных силах, и дело не во внешних помехах

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

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

Наука и жизнь
Родила для себя и не считаю это эгоизмом Родила для себя и не считаю это эгоизмом

Она родила без постоянного партнера и считает, что приняла лучшее решение

Psychologies
Почему Генрих — не Генрих, а Людовик — не Людовик? Почему Генрих — не Генрих, а Людовик — не Людовик?

О проблеме перевода или огласовки иностранных имён собственных

Наука и жизнь
Тележка для перевозки телескопа и другие гиганты на колесах Тележка для перевозки телескопа и другие гиганты на колесах

Серьезные механизмы, предназначенные для выполнения серьезной работы

Популярная механика
От чего умер Ленин? От чего умер Ленин?

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

Дилетант
Новая экранизация «Пиноккио» от режиссера «Догмэна» Маттео Гарроне — немного дубовая, но очень человечная версия сказки Карло Коллоди Новая экранизация «Пиноккио» от режиссера «Догмэна» Маттео Гарроне — немного дубовая, но очень человечная версия сказки Карло Коллоди

"Пиноккио" Маттео Гарроне: рецензия

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

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

Наука и жизнь
Кристин Лёнинс: Птица в клетке Кристин Лёнинс: Птица в клетке

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

СНОБ
В поиске космических катастроф. Вахта телескопов-роботов В поиске космических катастроф. Вахта телескопов-роботов

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

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

Технику пикапа – не на одну ночь, а на долгую счастливую жизнь

Tatler
Мельницы богов Мельницы богов

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

Вокруг света
Мерс Каннингем: жизнь в 3D Мерс Каннингем: жизнь в 3D

Главный редактор «Сноба»посмотрел фильм и пообщался с его автором

СНОБ
Унгерн-Штернберги Унгерн-Штернберги

Баронский род Унгерн-Штернберг восходит к XIII веку

Дилетант
Теневое правительство «Барселоны»: как Лионель Месси влияет на свой клуб Теневое правительство «Барселоны»: как Лионель Месси влияет на свой клуб

Переоценить влияние Лионеля Месси на игру «Барселоны» просто невозможно

GQ
Тайна гибели академика Легасова Тайна гибели академика Легасова

В апреле 1988 года был обнаружен повесившимся Валерий Легасов

Дилетант
Основатель сети отелей «Подушкин» Юрий Краснорутский: У меня вызывает отвращение все, что связано с физиологической грязью Основатель сети отелей «Подушкин» Юрий Краснорутский: У меня вызывает отвращение все, что связано с физиологической грязью

О любви. От романтических литературных историй до часовых свиваний в отеле

СНОБ
Гагарины Гагарины

Род князей Гагариных существует с XIII века, хотя положения добились не сразу

Дилетант
Знак качества Знак качества

Мы встретились с Шурой Би-2 и Лёвой Би-2 во время фестиваля Live Fest

OK!
Ваше идеальное тело: Программа лояльности Ваше идеальное тело: Программа лояльности

Цифра на весах — больше не показатель ваших успехов в спортзале

Glamour
Алишер Усманов оказался покупателем рукописи основателя олимпийского движения за $8,8 млн Алишер Усманов оказался покупателем рукописи основателя олимпийского движения за $8,8 млн

Российский миллиардер оказался покупателем рукописи манифеста Пьера де Кубертена

Forbes
Новые «Ходячие мертвецы» и не только: 6 лучших жанровых сериалов 2020 года Новые «Ходячие мертвецы» и не только: 6 лучших жанровых сериалов 2020 года

Готовься найти новый любимый сериал

Playboy
Три миллиона за частную школу: где и за сколько учатся дети звезд Три миллиона за частную школу: где и за сколько учатся дети звезд

Знаменитости не экономят на обучении своих детей

Cosmopolitan
Как выбрать правильное кольцо для помолвки Как выбрать правильное кольцо для помолвки

Как изменилась мода на помолвочные кольца?

GQ
Как IT-компания стоимостью $2 млрд готовится к IPO после того, как ее основателя обвинили в афере Как IT-компания стоимостью $2 млрд готовится к IPO после того, как ее основателя обвинили в афере

Разработчик шпионского софта стал одним из самых востребованных стартапов

Forbes
Поля Полякова: «Полюбите себя. Я пришла к этому не сразу» Поля Полякова: «Полюбите себя. Я пришла к этому не сразу»

Актриса Поля Полякова делится своими секретами красоты

Худеем правильно
Роберт Паттинсон: «Перестань себя ограничивать» Роберт Паттинсон: «Перестань себя ограничивать»

Роберт Паттинсон – о настоящих чувствах и уроках соблазна

Cosmopolitan
Хозяйка замка Хозяйка замка

Марси Холтес открывает для публики французское шато с 250-летней историей

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

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

СНОБ
Открыть в приложении