такой же, как для исходного графа.
Впоследствии доказательство Коши было подвергнуто критике. Как Эйлер попал впросак, не дав четких инструкций по порядку удаления пирамид, так и Коши не привел надежных указаний, в каком порядке отрезать треугольники. Если действовать неаккуратно, то можно, следуя алгоритму Коши, получить несвязный граф, для которого доказываемое соотношение не выполняется. Например, на рис. 12.5 мы удаляли треугольники в неправильном порядке и в результате получили несвязный граф, не удовлетворяющий формуле Эйлера (V = 10, E = 14, F = 6). Тем не менее всегда возможно, воспользовавшись методом Коши, упростить граф, не сталкиваясь с такой ситуацией.
Рис. 12.5. Метод Коши может приводить к вырожденным многоугольникам
Как мы уже отмечали, Коши поставил рекорд по доказательству теорем, не осознавая их важности и не доводя до логического завершения. Яркий пример — его доказательство формулы Эйлера. В своей статье он явно утверждает, что его доказательство применимо к выпуклым многогранникам. Это правда, но на самом деле оно применимо к гораздо более общему классу многогранников. Ключевой шаг доказательства Коши — удаление грани и перенос оставшейся части многогранника на плоскость удаленной грани, так чтобы никакие грани не пересекались. Это можно сделать для любого выпуклого многогранника, но также и для многих других.
Например, доказательство Коши проходит без каких-либо изменений для невыпуклого многогранника на рис. 12.6. Чтобы убедиться в этом, просто расположим камеру Лакатоса рядом с нижней гранью куба.
Рис. 12.6. Куб с вырезанным уголком и его граф
Лакатос и математик Эрнст Штайниц (1871–1928) считают, что Коши знал, что его доказательство применимо к некоторым, а быть может, и ко всем невыпуклым многогранникам. Недоразумение проистекает из небрежного употребления Коши слова «выпуклый». Оно отсутствует в формулировке теоремы, но в доказательстве он говорит о «выпуклой поверхности многогранника». Он так никогда и не развеял это недоразумение, поэтому невозможно сказать, что он знал и чего не знал.
Независимо от того, понимал ли Коши, что его результат можно распространить и на некоторые невыпуклые многогранники, другие это быстро заметили. В 1813 году, в тот же год, когда была опубликована статья Коши, Жергонн дал свое доказательство формулы Эйлера. Впоследствии он писал: «И все же кто-то может предпочесть — и не без причины — красивое доказательство г-на Коши, обладающее тем драгоценным преимуществом, что в нем не предполагается выпуклость многогранника»100.
При некотором воображении доказательство Коши можно применить и к еще более широкому классу многогранников. В современных вариантах этого доказательства многогранник предполагается сделанным из резины. Если после удаления грани оставшуюся часть многогранника можно растянуть на плоскости без перекрытий и складывания, то доказательство Коши применимо. В главе 15 мы увидим патологические примеры многогранников, не обладающих этим свойством — после удаления грани остаток нельзя разложить на плоскости. Оказывается, что ключевым свойством является то, что многогранник имеет «форму сферы». Мы подробно обсудим это кажущееся расплывчатым свойство в главе 16. Коши был буквально в шаге от осознания этого важнейшего свойства. Если бы он обратил на него внимание, то сделал бы важный вклад в только зарождавшуюся дисциплину — топологию, или analysis situs, как ее тогда называли. Как писал Жак Адамар (1865–1963) в 1907 году:
Я считаю одним из самых удивительных событий в истории науки ошибку, которую допустил Коши, полагавший, что доказал теорему Эйлера, но не сделавший никаких предположений о природе изучаемого многогранника. От его внимания ускользнул принцип огромной важности, открытие которого он оставил Риману: фундаментальная роль analysis situs в математике101.
Коши недооценил весь потенциал своего доказательства не только для многогранников, но и для графов. Например, Артур Кэли (1821–1895) в 1861 году заметил, что доказательство Коши применимо также к графам с криволинейными ребрами (этот факт был независимо отмечен Листингом в 1861 году и Камилем Жорданом [1838–1922] в 1866 году)102. В формулировке своей теоремы Коши предполагал, что граф — это совокупность многоугольников внутри многоугольной области. В следующей главе мы увидим, что о графах можно высказывать гораздо более общие утверждения, но для этого нужно сначала ввести современную терминологию.
Приложения к главе
94. Abel (1881), 259.
95. Freudenthal (1971).
96. Там же.
97. Simmons (1992), 186.
98. Cauchy (1813a).
99. Lhuilier (1813).
100. Там же.
101. Hadamard (1907).
102. Listing (1861-62); Jordan (1866b).
Глава 13
Планарные графы, математические планшеты и брюссельская капуста
В большинстве наук одно поколение разрушает созданное предыдущим и отменяет установленное ранее. Только в математике каждое поколение добавляет новый этаж к прежней конструкции.
— Герман Ганкель103
В предыдущей главе мы видели, какую остроумную технику применил Коши для доказательства формулы Эйлера. Он взял многогранник, удалил одну грань и спроецировал все, что осталось, на плоскость этой грани. Затем он доказал, что для получившегося многоугольника имеет место формула V — E + F = 1, а значит, для исходного многогранника — формула V — E + F = 2. Связь с теорией графов бросается в глаза. На первый взгляд кажется, что было бы тривиально обобщить формулу Эйлера на графы, которые не являются проекциями многогранников и имеют криволинейные ребра.
Но трудность обобщения формулы Эйлера состоит в том, что это проходит не для всех графов. Подсчитать вершины и ребра просто — это те элементы, из которых граф и состоит, но вот граней у графа может и не быть. Даже в том случае, когда граф нарисован на бумаге, ребра необязательно разбивают область на грани. Например, ребро PR в левом графе на рис. 13.1 пересекает ребро QS, поэтому не может быть границей никакой грани. Однако этот граф можно нарисовать по-другому (как в правой части), так что пересечений не будет, и тогда область разбивается на грани. Граф, который можно нарисовать, так что ребра не пересекаются, называется планарным.
В многограннике грань — это область, ограниченная многоугольником. Для графов определение не такое строгое. Грань может быть ограничена одним ребром, как петля из P в P на рис. 13.1. Или двумя ребрами, как в случае пары ребер, соединяющих вершины Q и R. (Два ребра между одной и той же парой вершин называются параллельными.) Возможно даже, что ребро заходит внутрь грани, как ребро между S и T.
Рис. 13.1. Два представления одного и того же графа
Многие специалисты
