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

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

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

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

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

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

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

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

Бурлеск Самбурской Бурлеск Самбурской

Актриса, певица, дива, Самбурская, Настасья – все это о ней

Maxim
Возможен ли счастливый брак, если нет общих интересов Возможен ли счастливый брак, если нет общих интересов

Можно ли создать счастливый союз, если нас не связывают общие интересы

Psychologies
Великое переселение лошадей Великое переселение лошадей

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

Наука и жизнь
Сергей Мироненко: 100 событий, которые изменили Россию Сергей Мироненко: 100 событий, которые изменили Россию

Отрывки из серии очерков о важных событиях в отечественной истории

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

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

Наука и жизнь
Выбираем эмоции: зачем нужна саморегуляция и как ей научиться Выбираем эмоции: зачем нужна саморегуляция и как ей научиться

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

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

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

Дилетант
Та самая девочка Та самая девочка

Ольга Бузова о том, почему не стесняется быть «девочкой из «Дома-2»

Домашний Очаг
Грозовой реактор Грозовой реактор

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

Наука и жизнь
Самый влюбчивый знак зодиака - кто он? Самый влюбчивый знак зодиака - кто он?

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

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

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

Наука и жизнь
7 главных российских вратарей из НХЛ 7 главных российских вратарей из НХЛ

Хоккеисты, которые доказывают, что наша вратарская школа – одна из лучших в мире

GQ
Почему светят звёзды? Почему светят звёзды?

Какие внутренние процессы заставляют звёзды излучать свет?

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

Иногда мы используем знакомые нам продукты не по назначению

Популярная механика
Универсальный актёр Универсальный актёр

Николай Черкасов мог сыграть кого угодно

Дилетант
Стиль милитари в мужской одежде: особенности, примеры и советы, как сочетать Стиль милитари в мужской одежде: особенности, примеры и советы, как сочетать

Приготовься к стильному уроку!

Playboy
Права сильных Права сильных

10 главных бизнес-историй 2019 года в спорте

Forbes
Заклятый враг Илона Маска: как 37-летний инженер бросил вызов Tesla и стал миллиардером Заклятый враг Илона Маска: как 37-летний инженер бросил вызов Tesla и стал миллиардером

Компании предстоит бороться с Tesla, и в этой борьбе у Rivian есть преимущества

Forbes
Биолог на Марсе Биолог на Марсе

Первый неамериканский марсоход: Rosalind Franklin в поисках воды и жизни

Популярная механика
«Женщина, которая бьется и страдает». Какой Марию Шарапову запомнит мир спорта «Женщина, которая бьется и страдает». Какой Марию Шарапову запомнит мир спорта

Рассказываем, чем запомнилась карьера самой известной российской спортсменки

Esquire
Одна вокруг света. Турецкий каучсерфинг и дорога через снежный перевал Одна вокруг света. Турецкий каучсерфинг и дорога через снежный перевал

Самый высокий перевал в Ливане,болезнь и переправа в Турцию на грузовом корабле

Forbes
«Спорт помогает мне быть счастливой и добиваться целей» «Спорт помогает мне быть счастливой и добиваться целей»

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

Psychologies
Ухудшилось ли ваше отношение к Украине за последнее время? Вопрос дня Ухудшилось ли ваше отношение к Украине за последнее время? Вопрос дня

Украинские и российские социологи зафиксировали ухудшение отношений

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

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

Forbes
Как секс влияет на успех в бизнесе Как секс влияет на успех в бизнесе

На ваше поведение в постели влияют те же факторы, что и на мотивацию на работе

Forbes
Тельца кормить, а Рака слушать: как влюбить в себя мужчину по гороскопу Тельца кормить, а Рака слушать: как влюбить в себя мужчину по гороскопу

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

Cosmopolitan
Больше сексуальности и блеска: как модный дом Saint Laurent впервые получил доход в €2 млрд Больше сексуальности и блеска: как модный дом Saint Laurent впервые получил доход в €2 млрд

В 2019 году выручка модного дома Saint Laurent выросла почти до €2,05 млрд

Forbes
Ребалансинг: как излечить тело с помощью телесных практик Ребалансинг: как излечить тело с помощью телесных практик

Когда официальная медицина бессильна, тяжело не сдаться и не смириться

Psychologies
Тупик Собянина: почему попытки повторить московскую реновацию обречены на провал Тупик Собянина: почему попытки повторить московскую реновацию обречены на провал

Российский проект реновации не может строиться по московской модели

Forbes
Вымойте руки: какие предметы опасны для здоровья Вымойте руки: какие предметы опасны для здоровья

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

Популярная механика
Открыть в приложении