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

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

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

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

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

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

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

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

От чего умер Ленин? От чего умер Ленин?

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

Дилетант
Сама нежность Сама нежность

Анна Шемуратова и Юлия Ли привносят в классику стиль лёгкость и свежее дыхание

SALON-Interior
Алюминиевый век Алюминиевый век

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

Наука и жизнь
История одной фотографии: Маргарет Кин доказывает авторство своих картин, 1970 год История одной фотографии: Маргарет Кин доказывает авторство своих картин, 1970 год

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

Maxim
Эйнштейн против Бора. Квантовая механика Эйнштейн против Бора. Квантовая механика

Со смертью Эйнштейна мир стал другим

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

Социологи и экономисты не зря пристально анализируют демографические показатели

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

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

Playboy
Google начнет блокировать рекламу. Даже собственную Google начнет блокировать рекламу. Даже собственную

Невыносимо омерзительное количество рекламы в интернете утомило даже Google

Популярная механика
Великое переселение лошадей Великое переселение лошадей

Эту историю я обнаружил, изучая подшивку журнала «Нива» за 1901 год

Наука и жизнь
Княгиня или актриса? Удивительные факты о трагической судьбе Грейс Келли Княгиня или актриса? Удивительные факты о трагической судьбе Грейс Келли

Грейс Келли - одна из легендарных актрис, которая затем стала княгиней Монако

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

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

Наука и жизнь
«Подлинная история банды Келли»: как реальная биография 25-летнего австралийского разбойника превратилась в рассказ о травмированном матерью Робине Гуде «Подлинная история банды Келли»: как реальная биография 25-летнего австралийского разбойника превратилась в рассказ о травмированном матерью Робине Гуде

Этот фильм больше похож на трехактный спектакль

Esquire
Злачное место Злачное место

Московский район Неглинки и Трубной площади далеко не всегда был респектабельным

Дилетант
«Бороться все равно надо»: почему звезда легкой атлетики Мария Ласицкене может пропустить Олимпиаду-2020 «Бороться все равно надо»: почему звезда легкой атлетики Мария Ласицкене может пропустить Олимпиаду-2020

Как «нейтральный статус» повлиял на карьеру, мотивацию и доходы Марии Ласицкене

Forbes
Крестовый психоз бедноты Крестовый психоз бедноты

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

Дилетант
10 лучших комедий ко Дню святого Валентина 10 лучших комедий ко Дню святого Валентина

Лёгкие комедии для свидания в День всех влюбленных

РБК
Плохое электрическое равновесие Плохое электрическое равновесие

Недореформированная российская энергетика живет по запутанному клубку правил

Эксперт
Эмоциональная трезвость. Как грамотно оценить свои силы в работе Эмоциональная трезвость. Как грамотно оценить свои силы в работе

В бизнесе женщине довольно часто приходится защищать свою правду и интересы

Forbes
«У владельцев есть искушение превратить компании в кеш-машину» «У владельцев есть искушение превратить компании в кеш-машину»

Почему Forbes выбрал первого вице-премьера Андрея Белоусова регулятором года?

Forbes
Развод, измены, Олимпиада: потрясающая история принцессы Анны – дочери королевы Развод, измены, Олимпиада: потрясающая история принцессы Анны – дочери королевы

Принцесса Анна - единственная дочь из четверых детей королевы

Cosmopolitan
«Соболезную вашей утрате»: можно ли найти правильные слова «Соболезную вашей утрате»: можно ли найти правильные слова

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

Psychologies
Ноам Хомский: Часы судного дня Ноам Хомский: Часы судного дня

Отрывок из книги Ноама Хомского «Кто правит миром?»

СНОБ
Тотальный кризис доверия. Кто виноват и что делать? Тотальный кризис доверия. Кто виноват и что делать?

В мире разворачивается еще один глобальный кризис — кризис потери доверия

Psychologies
10 правил планирования кухни - советы специалиста 10 правил планирования кухни - советы специалиста

Планирование кухни - дело непростое и весьма ответственное

Cosmopolitan
Плата за успех Плата за успех

Как не попасться на удочку мошенника?

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

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

Наука и жизнь
Хочешь всегда быть в постели «на высоте»? 6 главных правил Хочешь всегда быть в постели «на высоте»? 6 главных правил

Следуй этим рекомендациям, и все будет просто отлично

Playboy
Деревню могут эвакуировать на 10 лет из-за бомб времен ВМВ Деревню могут эвакуировать на 10 лет из-за бомб времен ВМВ

Нейтралитет в войне не означает отсутствия оружия в арсеналах

Популярная механика
Жизнь без насилия (страха, боли, ненависти) Жизнь без насилия (страха, боли, ненависти)

Как быть, если вы столкнулись с насилием в отношениях? Где искать помощи?

Домашний Очаг
Как научиться быстро печатать на клавиатуре: правильная методика и эффективные тренажеры Как научиться быстро печатать на клавиатуре: правильная методика и эффективные тренажеры

Быстрая печать - необходимый навык в современном мире

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