Это база: Зачем нужна математика в повседневной жизни

Эйлер переехал в Россию, в Санкт-Петербург, в 1727 году, когда в России правила императрица Екатерина I, чтобы стать придворным математиком. Муж Екатерины император Петр I основал Санкт-Петербургскую академию (Academia Scientiarum Imperialis Petropolitinae) в 1724–1725 годах, но умер прежде, чем она успела полностью сформироваться и заработать. Эйлер представил свою работу в Академии в 1735 году, и через год она была опубликована. Будучи математиком, причем, по мнению многих, самым плодовитым в истории, Эйлер извлек из головоломки так много, как только смог: он нашел необходимые и достаточные условия для существования решения, не только для кёнигсбергских мостов, но и для любой задачи подобного рода. Вы можете взять 50 000 мостов, связывающих друг с другом 40 000 островов гигантского комплекса, и теорема Эйлера без проблем скажет вам, существует ли для них решение. Если как следует вникнуть в доказательство, оно даже скажет, как это решение найти, – правда, после некоторой возни. Свое доказательство Эйлер изложил довольно схематично, и прошло почти 150 лет, прежде чем кто-то разобрался во всех его деталях, хотя само по себе доказательство не было слишком сложным.

В настоящее время многие книги по теории графов говорят о том, что Эйлер доказал отсутствие у головоломки решения, сведя ее к более простому вопросу о графах. Граф в этом смысле – это множество точек (называемых вершинами), соединенных линиями (их называют ребрами), и все это вместе образует своего рода сеть{34}. Переформулирование с использованием графов превращает головоломку кёнигсбергских мостов в задачу нахождения пути на конкретном графе, в котором каждое ребро используется ровно один раз. Именно так мы решаем эту задачу сегодня, но Эйлер делал не совсем так. В истории это случается часто. Историки математики с удовольствием рассказывают о том, как все происходило на самом деле, в отличие от общепринятого варианта. В реальности Эйлер решил задачу символически{35}.

Он обозначил каждый участок суши (остров или берег реки) и каждый мост буквой. Суше достались заглавные буквы A, B, C, D, а мостам – строчные a, b, c, d, e, f, g. Каждый мост соединяет друг с другом два участка суши, например, мост f соединяет A и D. Прогулка начинается в некоторой области и может быть описана последовательным перечислением преодоленных участков и мостов до последнего участка суши. В большей части статьи Эйлер описывает маршруты словесно и в основном работает с последовательностью участков суши. Не имеет значения, по какому мосту вы перейдете с A на B, если число сочетаний AB будет равно числу таких мостов. Или можно, наоборот, использовать последовательность мостов – достаточно обозначить точку начала и подсчитать, сколько раз вы посетите заданный участок. Не исключено, что так было бы проще. Ближе к концу статьи Эйлер использует те и другие символы и приводит пример последовательности

EaFbBcFdAeFfCgAhCiDkAmEnApBoElD,

соответствующий более сложной схеме{36}.

В такой формулировке конкретный путь, по которому идет пешеход на каждом участке или по каждому мосту, не имеет значения. Единственное, за чем нужно следить, – это последовательность, в которой посещаются участки и проходятся мосты. Проход по мосту подразумевает, что «две заглавные буквы с обеих его сторон различны». Это исключает возможность зайти на мост и возвратиться на ту же сторону. Решение – последовательность чередующихся заглавных и строчных букв A–D и a–g, в которой каждая строчная буква появляется ровно один раз, а заглавные буквы до и после любой заданной строчной соответствуют тем двум участкам берега, которые связаны данным мостом.

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

Допустим, мы начинаем с участка B. Три моста связывают B с другими участками: a, b и f. Предположим, мы выбираем f, тогда наша последовательность начинается с Bf. На другом конце моста f находится участок D, так что мы получаем Bf D. У нас имеются два неиспользованных моста, связывающие D с другими участками: e и g. (Мы не можем использовать f второй раз.) Попробуем g, и наш маршрут будет выглядеть как BfDg. На другом конце g находится C, что дает нам BfDgC. Теперь единственная возможность для продолжения у нас – мосты c и d (вновь по g мы идти не можем). Возможно, мы попробуем мост c, что приведет нас к BfDgCc, а затем к BfDgCcA. От участка A идут четыре возможных моста: a, b, d и e (мост c мы уже использовали).