лометров проволоки, которые двое ученых протянули по крышам Геттингена. Более того, она стала настолько сложной, что поиск шорткатов в сетях стал одной из основных задач современной математики. Эти сети могут состоять не только из проводов, но и из мостов, как я выяснил во время недавней поездки в Россию.
Читайте Эйлера. Читайте Эйлера. Он всем нам учитель
Несколько лет назад, когда я летел в Калининград, я постарался сделать так, чтобы на короткий перелет из Санкт-Петербурга у меня было место у окна. Я совершал паломничество в город, ставший местом действия одного из рассказов, на которых воспитываются все математики, – рассказа об одном из самых изобретательных шорткатов во всей истории математики.
Подлетая к Калининграду, маленькому эксклаву Российской Федерации, отделенному от ее основной территории Литвой и Польшей, я видел реку Преголю, протекающую через город. У реки есть два рукава, сходящиеся в Калининграде; от этого места она течет дальше на запад, к месту впадения в Балтийское море. В центре города расположен остров, обтекаемый рукавами реки. В самом сердце математической истории, прославившей Калининград, как раз и находятся мосты, соединяющие берега реки друг с другом и с этим островом.
История эта относится к XVIII веку, когда у города было другое название – Кёнигсберг. Он был родиной Иммануила Канта и знаменитого математика Давида Гильберта. В то время он входил в состав Пруссии, и через Преголю были перекинуты семь мостов[117]. Одним из любимых занятий обитателей города стало следующее развлечение: по воскресеньям после обеда они пытались найти такой маршрут, который проходил бы по всем мостам, но только по одному разу. Но как бы они ни старались, всегда находился один мост, до которого они добраться не могли. В самом ли деле это было невозможно, или все же был какой-нибудь способ, позволявший перейти через все семь мостов, до которого горожане просто не додумались?
Жителям Кёнигсберга казалось, что нет никакого способа избежать утомительной ходьбы по городу, пробуя поочередно все маршруты, проходящие по мостам, пока не будут исчерпаны все возможные варианты. При этом всегда оставалось подспудное ощущение, что, возможно, какой-нибудь хитроумный путь, дающий решение этой задачи, так и остался незамеченным.
Рис. 9.2. Семь мостов через реку Прегель в Кёнигсберге XVIII века
Раз и навсегда эта головоломка была разгадана только после явления одного из моих математических героев, Леонарда Эйлера: перейти через все мосты по одному, и только одному, разу было невозможно. Эйлер пришел к этому выводу, открыв шорткат, избавляющий от необходимости перебирать все возможные маршруты обхода мостов.
В главе 2 я уже познакомил вас со швейцарским математиком Леонардом Эйлером, когда показывал открытую им поразительную формулу, связывающую пять величин из числа самых главных в математике. «Читайте Эйлера. Читайте Эйлера. Он всем нам учитель», – писал о значении Эйлера в математике один из самых выдающихся математиков Франции Пьер-Симон Лаплас. Большинство математиков согласились бы с этой оценкой; его считают одним из величайших наравне с Гауссом. Был его поклонником и сам Гаусс: «Изучение работ Эйлера останется лучшей школой в разных отделах математики, и ничто не сможет его заменить».
Свершения Эйлера были многочисленны и разнообразны; к ним относится и шорткат к решению задачи о мостах Кёнигсберга, о которой он впервые узнал, когда служил профессором российской Императорской академии наук в Санкт-Петербурге. Эйлер не был коренным петербуржцем: он приехал туда из своего родного Базеля, в котором ему не удалось найти работу для математика. По-видимому, все подходящие должности уже были заняты. В этом небольшом городе наблюдался удивительный избыток математиков. Что еще удивительнее, все они происходили из одного и того же семейства – семейства Бернулли.
Более того, в Базеле не помещались даже все Бернулли. Даниил Бернулли перебрался в Санкт-Петербург еще раньше; именно его приглашение и обеспечило Эйлеру работу в академии. Перед отъездом Эйлера в Петербург Даниил прислал ему письмо с перечнем благ цивилизации, которых там недоставало: «Привезите, пожалуйста, пятнадцать фунтов кофе, фунт самого лучшего зеленого чая, шесть бутылок бренди, двенадцать дюжин отменных курительных трубок и несколько дюжин колод игральных карт».
Отягощенный всеми этими припасами, Эйлер отправился из Базеля в Петербург и, проделав семинедельный путь на корабле, в почтовой карете и пешком, прибыл туда и вступил в должность в мае 1727 года.
Кёнигсбергские мосты
Сперва задача о кёнигсбергских мостах была для Эйлера не более чем безделкой, позволявшей отвлечься от всех тех сложных вычислений, которыми он занимался. В 1736 году он изложил свои соображения об этой задаче в письме к придворному астроному в Вене Джованни Маринони: «Вопрос этот в высшей степени банален, но мне показалось достойным внимания то обстоятельство, что для его разрешения оказалось не достаточно ни геометрии, ни алгебры, ни даже искусства счета. В связи с этим мне случалось задумываться, не принадлежит ли он к сфере позиционной геометрии, к которой в свое время так стремился Лейбниц. Итак, после некоторых размышлений я получил простое, но совершенно обоснованное правило, применение коего помогает немедленно установить в любых примерах этого рода, возможен ли такой обход».
Важное концептуальное новшество, введенное Эйлером, сводилось к идее о том, что физические размеры города не имеют никакого значения. Важна лишь схема соединений между мостами. Тот же принцип лежит в основе схемы лондонского метро: в отличие от физически точной карты в ней сохранена лишь информация о соединениях между станциями. Если проанализировать карту Кёнигсберга, четыре участка суши, соединенные мостами, можно представить точками, а мосты – линиями, соединяющими эти точки, точно так же, как точки на схеме лондонского метро обозначают разные места Лондона. Тогда задача о возможности или невозможности существования маршрута, проходящего по всем мостам, сводится к вопросу о возможности или невозможности начертить такую же схему, не отрывая карандаш от бумаги и не проводя никакую из линий дважды.
Почему же это невозможно? Хотя Эйлер, вероятно, никогда не чертил такого графического представления Кёнигсберга, его анализ показывает, что маршрут возможен только в том случае, когда в его каждой промежуточной точке на каждую входящую линию приходится одна исходящая. Если вы снова оказываетесь в этой же точке, должен быть новый мост, по которому в нее можно попасть, и новый мост, по которому ее можно покинуть. Единственные исключения из этого правила – начальная и конечная точки маршрута. От точки, из которой вы начинаете движение, отходит одна линия. К точке, в которой маршрут заканчивается, тоже ведет одна линия. Маршрут обхода любого графа может существовать только тогда, когда в этом графе есть не более двух точек (вершин), к которым подходит нечетное количество линий (ребер), – начальная и конечная точки.
Рис. 9.3. Сеть кёнигсбергских мостов
Но если посмотреть на план семи кёнигсбергских мостов, в каждой его точке соединено нечетное количество линий. Такое большое число точек, от которых отходит нечетное число мостов, означает, что составить маршрут прогулки по городу, проходящий по каждому из мостов только по одному разу, невозможно.
Это один из моих любимых примеров шортката. Вместо перебора разных вариантов прокладки маршрута по карте предлагается простой анализ числа точек, от которых отходит нечетное количество мостов, и он сразу же показывает, что проложить такой маршрут невозможно.
Главное достоинство анализа Эйлера состоит в том, что он применим не только к Кёнигсбергу. Эйлер доказал: о какой бы сети, изображенной точками и соединяющими их линиями, ни шла речь, если из всех вершин исходит четное количество ребер, всегда можно составить маршрут, проходящий по всем линиям один, и только один, раз. Кроме того, такой маршрут возможен, если есть ровно две вершины с нечетным количеством ребер, при условии, что эти вершины являются начальной и конечной точками маршрута. Какой бы сложной ни была карта, такой простой подсчет количества нечетных вершин дает нам шорткат к пониманию возможности или невозможности ее обхода.
В Кёнигсберге было всего семь мостов. Однако не так давно бристольские математики применили шорткат Эйлера к 45 мостам, пересекающим сложную систему рек и каналов, протекающих через этот город. Если в Кёнигсберге было два острова, в Бристоле их три – Спайк-айленд, Сент-Филипс и Редклифф.
На первый взгляд совершенно неясно, можно ли проложить маршрут обхода всех 45 мостов, но при помощи шортката Эйлера можно увидеть, что число нечетных вершин на схеме, которая изображает участки суши, соединенные мостами, достаточно мало, чтобы такой маршрут мог существовать. Первый маршрут обхода открытых для пешеходов мостов Бристоля составил в 2013 году доктор Тило Гросс, бывший преподаватель прикладной математики Бристольского университета. «Когда я нашел решение, я, естественно, не мог не пройти по этому маршруту, – говорит он. – Первая прогулка по мостам заняла 11 часов; длина маршрута была около 53 километров».
Собственно говоря, шорткат Эйлера помог и мне, когда я в молодости сдавал психометрический тест при поступлении на работу. В тесте было несколько сетей, которые соискатель должен был начертить, не отрывая карандаш от бумаги и не проводя ни одной линии больше одного раза. Подразумевалось, что это возможно, и создавалось впечатление, что составители теста хотели проверить способность соискателей справляться с такими заданиями. На самом же деле проверялась честность соискателей, потому что начертить одну из трех сетей было невозможно. Как и в схеме кёнигсбергских мостов, в ней было больше двух вершин, от которых отходило нечетное число ребер.
Разумеется, написанное мной рядом с заданием заумное сочинение, рассказывающее о шорткате Эйлера и причинах, по которым это задание невозможно выполнить, не имело большого успеха. Работу я не получил.