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

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

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

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

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

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

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

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

Смерть бессильного вождя Смерть бессильного вождя

Это был лидер страны, у которого из средств общения осталась только мимика

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

Чем отличаются мультипекари и на что обращать внимание при покупке

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

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

Наука и жизнь
Злейший враг танка - быстролетящий лом: история военных разработок Злейший враг танка - быстролетящий лом: история военных разработок

Лучшим противотанковым боеприпасом остается быстролетящий лом

Популярная механика
Алюминиевый век Алюминиевый век

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

Наука и жизнь
«Грязь может запутать камеры». Как распознают нечитаемые номера «Грязь может запутать камеры». Как распознают нечитаемые номера

Зимой камеры часто ошибаются, но надеяться на слой грязи на номерах не стоит

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

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

Дилетант
Начните уже использовать ускорители свиданий Начните уже использовать ускорители свиданий

Это звучит как новое изобретение Рика Санчеза, но все намного проще

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

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

Наука и жизнь
«Я разделяю комфорт и ненужные понты». Правила потребления сооснователя CarPrice Эдуарда Гуриновича «Я разделяю комфорт и ненужные понты». Правила потребления сооснователя CarPrice Эдуарда Гуриновича

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

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

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

Наука и жизнь
Почему на тебе плохо сидит одежда и как это исправить — отвечает стилист Почему на тебе плохо сидит одежда и как это исправить — отвечает стилист

Как носить главные вещи весны-2020 девушкам с разным телосложением

Cosmopolitan
Как модель для сборки Как модель для сборки

Шварцвальд: времена меняются, но не все в мире спешит меняться вместе с ними

Вокруг света
4 главных страха, которые мешают вам жить на максимуме 4 главных страха, которые мешают вам жить на максимуме

В чем причина нашей пассивности, почему мы не можем сделать шаг к успеху?

Psychologies
50 — это новые 30? 50 — это новые 30?

Еще недавно в 50 мы готовились к пенсии, а сегодня — в ожидании новой жизни

Psychologies
10 «Жигулей», среди которых нет ни одних «Жигулей» 10 «Жигулей», среди которых нет ни одних «Жигулей»

Не верь глазам своим — этот автомобиль с обводами не «Жигули»

Maxim
С зубром лицом к лицу С зубром лицом к лицу

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

Наука и жизнь
Снимите белое пальто: как сохранить хорошую должность после 40 лет Снимите белое пальто: как сохранить хорошую должность после 40 лет

Кому я нужен после 40?

Forbes
Во все легкие Во все легкие

Жители хорватского полуострова Истрия нашли путь к счастью

Вокруг света
«Лучшая версия меня»: почему поколение Z удаляет фотографии из Instagram через несколько часов после публикации «Лучшая версия меня»: почему поколение Z удаляет фотографии из Instagram через несколько часов после публикации

Современные подростки — первое поколение, взрослеющее в эпоху социальных сетей

Forbes
Это фейк: 6 случаев, когда вместо звёзд вышли их двойники и спалились Это фейк: 6 случаев, когда вместо звёзд вышли их двойники и спалились

Некоторые звезды отправляют вместо себя на важные мероприятия двойников

Cosmopolitan
Forbes впервые оценил продажи в Рунете Forbes впервые оценил продажи в Рунете

Как изменились онлайн-магазины за последние несколько лет

Forbes
Кивать, воровать и молиться: легко ли выходцу из России начать свой бизнес на Сицилии Кивать, воровать и молиться: легко ли выходцу из России начать свой бизнес на Сицилии

Некоторые особенности сицилийской национальной бюрократии

Forbes
Брось нелюбимую! Брось нелюбимую!

Как решиться отказаться от стабильной работы с хорошей зарплатой

Лиза
Американский перевал Дятлова: пятеро парней, потерянных в снегах Американский перевал Дятлова: пятеро парней, потерянных в снегах

В 1978 году пятеро парней пропали в городе Чико по пути с баскетбольного матча

Cosmopolitan
Последний суд. Кто будет решать судьбу российского спорта Последний суд. Кто будет решать судьбу российского спорта

Об организации, от которой зависят олимпийские перспективы российских атлетов

Forbes
Как выбрать и пользоваться блендером — инструкция для новичков Как выбрать и пользоваться блендером — инструкция для новичков

Делимся советами, как правильно выбрать блендер и пользоваться им

Cosmopolitan
Водителей разделят на плохих и хороших Водителей разделят на плохих и хороших

Разбираем самые важные изменения в проекте нового КоАП

РБК
Когда возраст берет нас в заложники Когда возраст берет нас в заложники

Старение часто становится испытанием

Psychologies
Почему диеты не работают, а люди годами ходят в спортзал и не меняются? Почему диеты не работают, а люди годами ходят в спортзал и не меняются?

Юлия Вихрева поделилась эффективной стратегией похудения

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