Искусство мыслить рационально. Шорткаты в математике и в жизни - Маркус Дю Сотой Страница 73

Сперва задача о кёнигсбергских мостах была для Эйлера не более чем безделкой, позволявшей отвлечься от всех тех сложных вычислений, которыми он занимался. В 1736 году он изложил свои соображения об этой задаче в письме к придворному астроному в Вене Джованни Маринони: «Вопрос этот в высшей степени банален, но мне показалось достойным внимания то обстоятельство, что для его разрешения оказалось не достаточно ни геометрии, ни алгебры, ни даже искусства счета. В связи с этим мне случалось задумываться, не принадлежит ли он к сфере позиционной геометрии, к которой в свое время так стремился Лейбниц. Итак, после некоторых размышлений я получил простое, но совершенно обоснованное правило, применение коего помогает немедленно установить в любых примерах этого рода, возможен ли такой обход».

Важное концептуальное новшество, введенное Эйлером, сводилось к идее о том, что физические размеры города не имеют никакого значения. Важна лишь схема соединений между мостами. Тот же принцип лежит в основе схемы лондонского метро: в отличие от физически точной карты в ней сохранена лишь информация о соединениях между станциями. Если проанализировать карту Кёнигсберга, четыре участка суши, соединенные мостами, можно представить точками, а мосты – линиями, соединяющими эти точки, точно так же, как точки на схеме лондонского метро обозначают разные места Лондона. Тогда задача о возможности или невозможности существования маршрута, проходящего по всем мостам, сводится к вопросу о возможности или невозможности начертить такую же схему, не отрывая карандаш от бумаги и не проводя никакую из линий дважды.

Почему же это невозможно? Хотя Эйлер, вероятно, никогда не чертил такого графического представления Кёнигсберга, его анализ показывает, что маршрут возможен только в том случае, когда в его каждой промежуточной точке на каждую входящую линию приходится одна исходящая. Если вы снова оказываетесь в этой же точке, должен быть новый мост, по которому в нее можно попасть, и новый мост, по которому ее можно покинуть. Единственные исключения из этого правила – начальная и конечная точки маршрута. От точки, из которой вы начинаете движение, отходит одна линия. К точке, в которой маршрут заканчивается, тоже ведет одна линия. Маршрут обхода любого графа может существовать только тогда, когда в этом графе есть не более двух точек (вершин), к которым подходит нечетное количество линий (ребер), – начальная и конечная точки.

Рис. 9.3. Сеть кёнигсбергских мостов

Но если посмотреть на план семи кёнигсбергских мостов, в каждой его точке соединено нечетное количество линий. Такое большое число точек, от которых отходит нечетное число мостов, означает, что составить маршрут прогулки по городу, проходящий по каждому из мостов только по одному разу, невозможно.

Это один из моих любимых примеров шортката. Вместо перебора разных вариантов прокладки маршрута по карте предлагается простой анализ числа точек, от которых отходит нечетное количество мостов, и он сразу же показывает, что проложить такой маршрут невозможно.

Главное достоинство анализа Эйлера состоит в том, что он применим не только к Кёнигсбергу. Эйлер доказал: о какой бы сети, изображенной точками и соединяющими их линиями, ни шла речь, если из всех вершин исходит четное количество ребер, всегда можно составить маршрут, проходящий по всем линиям один, и только один, раз. Кроме того, такой маршрут возможен, если есть ровно две вершины с нечетным количеством ребер, при условии, что эти вершины являются начальной и конечной точками маршрута. Какой бы сложной ни была карта, такой простой подсчет количества нечетных вершин дает нам шорткат к пониманию возможности или невозможности ее обхода.