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

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

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

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

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

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

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

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

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

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

Наука и жизнь
Только без рук! Только без рук!

Невероятной популярности Венеры Милосской никак не мешает отсутствие рук

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

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

Наука и жизнь
Черногорская революция и предательство России Черногорская революция и предательство России

О вступлении в НАТО и «попытке государственного переворота» с участием россиян

Русский репортер
Пожиратели бюджетов Пожиратели бюджетов

Почему иногда строить дороги не нужно

Forbes
«Без любви и без музыки жизнь была бы ошибкой» «Без любви и без музыки жизнь была бы ошибкой»

Впервые в истории шоу «Холостяк» главным героем стал немедийный человек

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

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

Наука и жизнь
Почему российские футболисты почти не играют в Европе Почему российские футболисты почти не играют в Европе

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

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

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

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

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

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

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

Наука и жизнь
Успеть за 40 секунд: как разобрать и собрать автомат Калашникова Успеть за 40 секунд: как разобрать и собрать автомат Калашникова

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

Популярная механика
Робот – лучший повар Робот – лучший повар

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

Популярная механика
MAXIM рецензирует удалой бандитский байопик «Подлинная история банды Келли» MAXIM рецензирует удалой бандитский байопик «Подлинная история банды Келли»

«Подлинную историю банды Келли» невзлюбили те, кто взлюбил самого Неда Келли

Maxim
Земля переезжает Земля переезжает

Когда Солнце начнет затухать, корабль «Земля» уже прибудет к новой звезде

Популярная механика
Suzuki Jimny. Возврат к эпохе «Самураев» Suzuki Jimny. Возврат к эпохе «Самураев»

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

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

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

Forbes
Как просмотреть программы в автозагрузке Windows 10, если заблокирован Диспетчер задач Как просмотреть программы в автозагрузке Windows 10, если заблокирован Диспетчер задач

Что делать, если вирус заблокировал Диспетчер задач

CHIP
Яйцо высшей категории Яйцо высшей категории

Мистика и символика пасхального яйца — писанки

Вокруг света
Отряд Дамбл… Давора Отряд Дамбл… Давора

Как родители и дети решили отстоять директора школы

Русский репортер
Зачекиниться на выставке: почему поколение Z ходит в музеи и разбирается в современном искусстве Зачекиниться на выставке: почему поколение Z ходит в музеи и разбирается в современном искусстве

Музеи снова стали местом притяжения интеллигенции всех возрастов и форматов

Forbes
Как Наталья Водянова помогает детям с особенностями развития: реальные истории Как Наталья Водянова помогает детям с особенностями развития: реальные истории

Истории ребят, которым помогла Наталья Водянова и ее фонд "Обнаженные сердца"

Cosmopolitan
Эпизод третий: бремя Бога, сигареты и Бродский Эпизод третий: бремя Бога, сигареты и Бродский

Курят ли в Ватикане, почему Ленни цитирует Бродского и как низложить кардинала

Esquire
Застраховали: сколько стоит грудь Водонаевой и другие звездные части тела Застраховали: сколько стоит грудь Водонаевой и другие звездные части тела

Мода на страхование частей тела появилась в Голливуде в начале 80-х годов

Cosmopolitan
Мой Сталинград Мой Сталинград

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

Наука и жизнь
«Ангелы в аду»: NYT рассказала о культуре запугиваний и домогательств в Victoria’s Secret «Ангелы в аду»: NYT рассказала о культуре запугиваний и домогательств в Victoria’s Secret

Новые факты о культовом бренде, испытывающем большие проблемы

Forbes
Почему одни люди счастливее других Почему одни люди счастливее других

Пенсионеры счастливей молодых, люди с высшим образованием — людей со средним

СНОБ
Подумай хорошенько Подумай хорошенько

Как нейросети читают мысли

Популярная механика
Убийца с мороженым: жуткая история женщины, которая мечтала стать матерью Убийца с мороженым: жуткая история женщины, которая мечтала стать матерью

Эстибализ Карранца — одна из самых хладнокровных серийных женщин-убийц

Cosmopolitan
#инструктаж: как правильно выбрать зубную щетку и пасту #инструктаж: как правильно выбрать зубную щетку и пасту

Что нужно знать, чтобы подобрать щетку себе и ребенку

РБК
Открыть в приложении