Карта → линии → сквозной сюжет

Нить кёнигсбергских мостов

одна прогулка — и два раздела карты, выросшие из неё

Одна воскресная прогулка по семи мостам (Кёнигсберг; решено в Петербурге, 1736) — и от неё расходятся два разных раздела карты. Эйлер это заметил сам: в задаче нет ни длин, ни углов, и он написал, что она относится к «геометрии положения», для которой ещё нет науки.

Топологическая ветвь. Через четырнадцать лет Эйлер получает второй результат того же жанра — формулу для многогранников (Петербург, 1750). Люилье находит тела, для которых она неверна, и у поверхности появляется род (Женева, 1813); Листинг даёт будущей науке имя за полвека до того, как у неё появится содержание (Гёттинген, 1847). Пуанкаре превращает коллекцию курьёзов в науку о форме (Париж, 1895) и в последнем дополнении к ней ставит вопрос, на который ответят только через девяносто восемь лет — в Санкт-Петербурге (2002), там же, где нить началась. По дороге Эмми Нётер замечает, что числа, которыми топологи считали дырки, — всего лишь ранги групп (Гёттинген, 1925): счёт Эйлера окончательно становится алгеброй.

Графовая ветвь. К мостам прибавляются раскраска карты графств (Лондон, 1852) и обход додекаэдра (Дублин, 1856); межвоенный Будапешт собирает головоломки в теорию графов (Кёниг, 1931). А в 1972-м в Беркли — и через год, ничего об этом не зная, в Москве — выясняется, что гамильтонов цикл и раскраска суть одна и та же NP-полная задача: вековые головоломки оказываются одним великим вопросом «легко ли найти то, что легко проверить?». Финал двойной: машина доказывает теорему о четырёх красках (Урбана, 1976), а другая машина проверяет это доказательство (Coq, Париж, 2005).

Обе развязки возвращаются к завязке. Топологическая — географически: гипотезу Пуанкаре доказывают в городе, где Эйлер разбирал мосты. Графовая — по существу: в формальном доказательстве о раскраске карт машина узнаёт плоскость по формуле Эйлера для многогранников.

Открыть на карте

1

Санкт-Петербург 1736
Семь мостов Кёнигсберга
Развилка: из одной прогулки выходят и топология, и теория графов

Можно ли пройти по всем семи мостам, не пройдя ни по одному дважды? Эйлер отвечает «нет» и объясняет почему — рассуждением, в котором нет ни одной длины и ни одного угла. Обычно отсюда отсчитывают начало и топологии, и теории графов.
2

Санкт-Петербург письмо Гольдбаху — 14 ноября 1750; кривизна поверхностей — Берлин, 1760
Эйлер: два результата, на которых стоит половина линии
Топологическая ветвь: тот же приём — считать, не измеряя

Формула $V-E+F=2$ — первый в истории топологический инвариант, найденный за девяносто семь лет до появления слова «топология». Главные кривизны поверхности — то, из чего Гаусс через шестьдесят семь лет сделает свою «замечательную теорему». Обе вещи используются дальше по карте постоянно, и обе введены здесь.
3

Женева 1813
Многогранник с дыркой
Формула даёт сбой — и у поверхности появляется род

Формула Эйлера $V-E+F=2$ неверна для многогранника со сквозной дыркой: там получается ноль. Люилье собирает целую коллекцию таких исключений — и из «поломки» вырастает понятие рода поверхности, первый настоящий топологический инвариант.
4

Гёттинген 1847
Слово «топология»
У науки, которой «ещё нет», появляется имя — за полвека до содержания

Иоганн Листинг, ученик Гаусса, печатает «Предварительные исследования по топологии» — дисциплина получает имя за полвека до того, как обзаведётся содержанием. С латинским «analysis situs» слово будет конкурировать до XX века, а сам Листинг останется в истории человеком, у которого дважды отняли первенство.
5

Лондон 1852
Четыре краски: 124-летний сериал
Графовая ветвь: вторая головоломка — раскрасить карту

Студент, раскрашивая карту английских графств, замечает, что четырёх цветов всегда хватает. Доказательство Кемпе одиннадцать лет считалось верным, потом рухнуло — и из обломков спасли теорему о пяти красках. Настоящая развязка придёт через 124 года и будет машинной.
6

Дублин 1856–1859
Икосианская игра
Третья головоломка: обойти все вершины

Гамильтон придумывает головоломку: обойти все вершины додекаэдра по одному разу. Права продаёт издателю за 25 фунтов, игра проваливается. Через 115 лет задача о гамильтоновом цикле окажется среди первых NP-полных — и обнаружится, что от эйлеровой её отделяет пропасть.
7

Париж 1895–1904
Пуанкаре: «Analysis Situs»
Курьёзы становятся наукой о форме — и получают главный вопрос

Топология создаётся за одну работу и пять дополнений к ней: фундаментальная группа, гомологии, числа Бетти, двойственность. В последнем дополнении Пуанкаре строит контрпример к собственной догадке — и формулирует вопрос, на который ответят через девяносто восемь лет.
8

Гёттинген 1925–1926
Гомологии становятся группами
Счёт Эйлера становится алгеброй: числа Бетти — всего лишь ранги групп

Эмми Нётер замечает: числа Бетти, которыми топологи считали дыры, — всего лишь ранги некоторых групп, и работать надо с самими группами. Замечание, сделанное на чужом семинаре, превращает топологию в алгебраическую и задаёт способ работы на весь XX век.
9

Будапешт 1931–1936
Будапешт: дисциплина получает имя
Головоломки становятся дисциплиной

Теорема о паросочетаниях в двудольных графах — и первая в истории монография по теории графов. Столетие разрозненных головоломок кончается: у предмета появляются имя, учебник и метод. Судьба автора трагична: он покончил с собой в октябре 1944 года, за несколько дней до депортаций.
10

Беркли 1972
NP-полнота: 21 задача — одна проблема
Все головоломки — одна задача (NP-полнота)

Гамильтонов цикл, раскраска карты, укладка рюкзака, расписание — двадцать одна задача из разных областей оказалась одной задачей в разных костюмах. Быстрый алгоритм для любой из них дал бы быстрый алгоритм для всех. Есть ли он — вопрос, стоящий в списке задач тысячелетия.
11

Москва 1973
Левин: универсальные задачи перебора
То же самое, независимо и на двух страницах — Москва не знала о Беркли

Две страницы в «Проблемах передачи информации» — и то же самое, что за океаном заняло две большие статьи. Формулировка при этом другая и, пожалуй, более естественная: не «есть ли решение», а «найдите решение». А в придачу — теорема о том, что оптимальный алгоритм существует всегда.
12

Урбана (Иллинойс) 21 июня 1976
Урбана: четыре краски доказаны машиной
Первая великая теорема, доказанная машиной

1936 конфигураций, около 1200 часов машинного времени — и гипотеза, простоявшая 124 года, доказана. Вместе с ней пришёл вопрос, которого математика прежде не знала: что считать доказательством, если ни один человек не может его прочитать?
13

Санкт-Петербург 2002–2003
Гипотеза Пуанкаре доказана
Развязка топологической ветви — в городе, где нить началась

Григорий Перельман тремя препринтами закрывает гипотезу Пуанкаре и более общую гипотезу геометризации Тёрстона. Метод — риччиев поток с хирургией: метрика эволюционирует так, чтобы кривизна выравнивалась, а возникающие особенности вырезаются. Топологическая задача решена средствами геометрии и анализа. Все премии отклонены.
14

Кембридж доказательство закончено в декабре 2004, объявлено в апреле 2005
Машина проверяет математику
Развязка графовой ветви: машина проверяет машину

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