Коши недооценил весь потенциал своего доказательства не только для многогранников, но и для графов. Например, Артур Кэли (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
Планарные графы, математические планшеты и брюссельская капуста
В большинстве наук одно поколение разрушает созданное предыдущим и отменяет установленное ранее. Только в математике каждое поколение добавляет новый этаж к прежней конструкции.
В предыдущей главе мы видели, какую остроумную технику применил Коши для доказательства формулы Эйлера. Он взял многогранник, удалил одну грань и спроецировал все, что осталось, на плоскость этой грани. Затем он доказал, что для получившегося многоугольника имеет место формула V — E + F = 1, а значит, для исходного многогранника — формула V — E + F = 2. Связь с теорией графов бросается в глаза. На первый взгляд кажется, что было бы тривиально обобщить формулу Эйлера на графы, которые не являются проекциями многогранников и имеют криволинейные ребра.
Но трудность обобщения формулы Эйлера состоит в том, что это проходит не для всех графов. Подсчитать вершины и ребра просто — это те элементы, из которых граф и состоит, но вот граней у графа может и не быть. Даже в том случае, когда граф нарисован на бумаге, ребра необязательно разбивают область на грани. Например, ребро PR в левом графе на рис. 13.1 пересекает ребро QS, поэтому не может быть границей никакой грани. Однако этот граф можно нарисовать по-другому (как в правой части), так что пересечений не будет, и тогда область разбивается на грани. Граф, который можно нарисовать, так что ребра не пересекаются, называется планарным.
В многограннике грань — это область, ограниченная многоугольником. Для графов определение не такое строгое. Грань может быть ограничена одним ребром, как петля из P в P на рис. 13.1. Или двумя ребрами, как в случае пары ребер, соединяющих вершины Q и R. (Два ребра между одной и той же парой вершин называются параллельными.) Возможно даже, что ребро заходит внутрь грани, как ребро между S и T.
Рис. 13.1. Два представления одного и того же графа
Многие специалисты по теории графов считают внешнюю область гранью. Если рассматривать граф как остров, то эта неограниченная грань будет морем, протянувшимся в бесконечность во всех направлениях. И хотя называть эту неограниченную область гранью довольно странно, часто полезнее включать ее в число граней, чем исключать. Один из способов обрести душевный покой в этом вопросе — рассматривать граф как остров не в бескрайнем море, а на глобусе (рис. 13.2). Тогда неограниченная грань оказывается конечной.
Рис. 13.2. Расположение планарного графа на сфере
Итак, мы имеем следующее обобщение формулы Эйлера для планарных графов.
Если не считать неограниченную область гранью, то формула Эйлера принимает вид V — E + F = 1. У графа на рис. 13.1 пять вершин, семь ребер и четыре грани, 5–7 + 4 = 2, как и должно быть.
В качестве элементарного примера рассмотрим дерево. Деревом называется связный граф без циклов (см. рис. 13.3). Поскольку в дереве нет циклов, не ограничена всего одна грань, поэтому формула Эйлера дает V — E + 1 = 2, или V = E + 1. Иными словами, число вершин дерева на единицу больше числа ребер. В дереве на рис. 13.3 имеется 19 вершин и 18 ребер.