Жемчужина Эйлера - Дэвид С. Ричесон
Доказательство Эйлера стало предтечей современных комбинаторных доказательств. Он воспользовался методом рассечения, чтобы, взяв сложный многогранник, быть может, с большим числом вершин, свести его к более простому путем применения систематической процедуры. Эйлер предлагает удалять вершины многогранника по одной, пока не останется всего четыре, образующие треугольную пирамиду. Следя за числом вершин, ребер и граней на каждом этапе и используя известные свойства треугольной пирамиды, он смог прийти к выводу, что V — E + F = 2 для исходного многогранника.
Прежде чем переходить непосредственно к доказательству Эйлера, рассмотрим пример. Взгляните на декомпозицию куба на рис. 7.3. На каждом этапе мы удаляем одну вершину куба, отрезая от него треугольные пирамиды, и продолжаем это делать, пока не останется одна треугольная пирамида. Поскольку куб — сравнительно простой многогранник, для удаления вершины достаточно отрезать одну пирамиду. Но в общем случае для этого, возможно, придется отрезать несколько пирамид. В табл. 7.1 показано количество вершин, ребер и граней на каждом этапе декомпозиции.
Рис. 7.3. Удаление вершин куба с целью получения тетраэдра
Таблица 7.1. Преобразование куба в тетраэдр путем удаления вершин по одной
Можно было бы рассчитывать, что при уменьшении числа вершин число граней и ребер уменьшается, следуя какой-то предсказуемой закономерности. Но, как показывает таблица, в этой последовательности нет очевидного порядка. В нашем примере число граней сначала увеличивается и только потом начинает уменьшаться — в исходном многограннике было шесть граней, а после отрезания вершин их становится семь, затем снова семь, потом шесть и, наконец, четыре. Этот путь ведет в тупик. Ключом к доказательству Эйлера является проницательное наблюдение, что разность между числом ребер и числом граней уменьшается на единицу после удаления каждой вершины (это видно из последнего столбца таблицы). Как мы увидим, в этом вся соль доказательства Эйлера.
Вначале мы имеем многогранник с V вершинами, E ребрами и F гранями. Наша первая задача — удалить вершину многогранника, чтобы в новом многограннике вершин было меньше, чем в исходном. После этого мы должны посчитать число граней и ребер в получившемся многограннике. Пусть O — вершина, подлежащая удалению, и предположим, что в ней сходится n граней (и, следовательно, n ребер). Эйлер увидел, что O можно удалить, отрезав n — 2 треугольных пирамид с вершиной O. Например, вершина в многограннике на рис. 7.4 образована схождением 5 граней, и для ее удаления нужно отрезать 3 пирамиды.
Рис. 7.4. Удаление вершины O путем отрезания пирамид
Мы хотели знать, сколько граней и ребер в уменьшенном многограннике. На примере куба мы видели, что простого ответа на этот вопрос нет. Необходимо рассмотреть три случая. Сначала рассмотрим самый простой: предположим, что все грани, сходящиеся в O, треугольные. Отрезав O, мы удалим эти n граней, но под n — 2 отрезанными пирамидами обнаружим n — 2 новых треугольных граней. В предположении, что все новые треугольные грани лежат в разных плоскостях, число граней нового многогранника будет равно
F — n + (n — 2) = F — 2,
где F — исходное число граней.
По ходу дела мы удаляем также n ребер, сходящихся в вершине O, но добавляем n — 3 ребра, разделяющих n — 2 новые треугольные грани. Таким образом, число ребер в новом многограннике равно
E — n + (n — 3) = E — 3,
где E — исходное число ребер.
Снова взглянем на рис. 7.4. Мы начали с многогранника, имеющего 11 граней и 20 ребер. После отрезания трех пирамид получился многогранник с 11 — 2 = 9 гранями и 20 — 3 = 17 ребрами.
В приведенном рассуждении мы сделали два предположения о декомпозиции многогранника. Первое — что все грани, сходящиеся в вершине O, треугольные, второе — что новые треугольные грани многогранника не компланарны. Теперь следует рассмотреть, что будет, если одно или оба предположения не выполняются.
Предположим, что одна из граней, сходящихся в O, не треугольная (например, закрашенная грань на рис. 7.5). Тогда при отрезании пирамиды, одна из граней которой лежит в плоскости этой грани, эта грань не убирается из многогранника полностью. Кроме того, добавляется новое ребро там, где эта грань разрезана на две части. Таким образом, число граней и ребер в новом многограннике на единицу больше, чем предполагалось ранее. В этом примере мы начали с многогранника, имеющего 12 граней и 23 ребра. После отрезания пирамид получается многогранник с 12 — 2 + 1 = 11 гранями и 23 — 3 + 1 = 21 ребром. В общем случае, если исходный многогранник имеет s нетреугольных граней, сходящихся в O, то количество граней и ребер будет на s больше, чем ожидалось. Поэтому число граней равно F — 2 + s, а число ребер равно E — 3 + s.
С другой стороны, предположим, что две из новых треугольных граней расположены рядом и лежат в одной плоскости (например, закрашенные грани на рис. 7.6). Тогда они привнесут в результирующий многогранник не две разные грани, а одну четырехугольную грань. Таким образом, получится на одну грань меньше, чем предполагалось. Поскольку между этими гранями нет ребра, ребер тоже будет на одно меньше. В примере на рис. 7.6 мы начали с многогранника, имеющего 11 граней и 20 ребер. После отрезания пирамид стало 11 — 2–1 = 8 граней и 20 — 3–1 = 16 ребер. если такое происходит t раз, то граней и ребер будет на t меньше, чем ожидалось. Поэтому в результирующем многограннике число граней будет равно F — 2 + s — t, а число ребер — E — 3 + s — t.
Рис. 7.5. Нетреугольная грань привносит одну новую грань и одно новое ребро в новый многогранник
