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

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

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

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

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

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

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

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

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

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

Наука и жизнь
What the fake: какие предметы дизайна чаще всего подделывают в России What the fake: какие предметы дизайна чаще всего подделывают в России

Подделки, фейки, реплики, заимствования — норма жизни современного общества

Forbes
Летающий мопед Летающий мопед

Автожиры: полет над вулканом и не только.

Популярная механика
Частицы Тунгусского метеорита начали искать в озёрах Частицы Тунгусского метеорита начали искать в озёрах

Возможно, элементы космического тела позволят восстановить сценарий катастрофы

Популярная механика
Грозовой реактор Грозовой реактор

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

Наука и жизнь
Кесарю — кесарево. Почему в Конституции не должно быть Бога Кесарю — кесарево. Почему в Конституции не должно быть Бога

В России вовсю идет обсуждение поправок в Конституцию

СНОБ
Чёрный передел: версия 1939 года Чёрный передел: версия 1939 года

Секретный протокол к Пакту о ненападении

Дилетант
Porsche Taycan. Создание новой реальности Porsche Taycan. Создание новой реальности

Что может пригодиться в условиях стремительно меняющейся реальности?

4x4 Club
Археология в 2019 году: несколько интересных находок Археология в 2019 году: несколько интересных находок

Интересные археологические находки 2019 года

Наука и жизнь
Девушка в саркофаге: как я живу с клаустрофобией и агорафобией Девушка в саркофаге: как я живу с клаустрофобией и агорафобией

Медиахудожница рассказывает о своей жизни с агорафобией и клаустрофобией

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

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

Наука и жизнь
Как выбрать правильное кольцо для помолвки Как выбрать правильное кольцо для помолвки

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

GQ
Виллами по воде. Экскурсия на озеро Комо Виллами по воде. Экскурсия на озеро Комо

Когда реальные путешествия невозможны, на помощь приходят виртуальные туры

Вокруг света
Синие волосы – оттенки, краски и тоники для волос Синие волосы – оттенки, краски и тоники для волос

Мода на яркие оттенки вызвала всплеск популярности ярких красок для волос

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

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

Forbes
Быть начеку: краткий гид по оружию самообороны Быть начеку: краткий гид по оружию самообороны

Есть два типа людей: одни с пистолетом, другие копают

Популярная механика
С зубром лицом к лицу С зубром лицом к лицу

Единственный из видов диких быков Европы, уцелевший до наших дней

Наука и жизнь
Закон и порядок Закон и порядок

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

AD
Марсианские хроники 2020 Марсианские хроники 2020

Для межпланетарной космонавтики будущее лето станет особенно жарким

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

Ключ к успеху находится у вас не в руках, а в ногах

GQ

Герои нашей подборки стали жертвами чужих злых шуток

Cosmopolitan
Правила жизни Кирка Дугласа Правила жизни Кирка Дугласа

Актер, Нью-Йорк. Скончался 5 февраля 2020 в возрасте 103 лет

Esquire
Сезонное предложение Сезонное предложение

Зима – идеальное время для проведения пилингов

Лиза
Гений эшафота: история самого знаменитого палача XX века Гений эшафота: история самого знаменитого палача XX века

Жил-был обычный палач, который сначала стал суперзвездой, а затем изгоем

Maxim
Владимир Гусев: «Люди не должны идти в музей за сенсацией» Владимир Гусев: «Люди не должны идти в музей за сенсацией»

Почему Русский музей — это место для созерцания

Эксперт
5 писателей-дебоширов 5 писателей-дебоширов

Скандальные выходки знаменитых писателей

Maxim
Поколение девяностых: особенности и пунктики Поколение девяностых: особенности и пунктики

Кто они, дети Интернета, мобильника и безоблачного кондиционера над головой?

Maxim
Чем женский японский язык отличается от мужского Чем женский японский язык отличается от мужского

Отрывок из книги Гастона Доррена о языках «Вавилон: Вокруг света за 20 языков»

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

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

РБК
5 книг про ВИЧ и СПИД: самая важная информация 5 книг про ВИЧ и СПИД: самая важная информация

Подборку 5 книг, в которых вы найдете ответы на все вопросы о ВИЧ

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