Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2001/05/09.pdf Дата изменения: Fri Dec 23 19:26:32 2005 Дата индексирования: Tue Oct 2 00:09:58 2012 Кодировка: Windows-1251 Поисковые слова: р р р р р р р р р р р р р р р р р р р р р р р р р р р р р р р р р р р р р р

ТРИ

ТЕОРЕМЫ

О

ВЫПУКЛЫХ

МНОГОГРАННИКАХ

9

ных свойств, которым подчинены тела, ограниченные плоскими гранями'. Теорема Эйлера. Пусть В число вершин выпуклого многогранника, Р число его ребер и Г число граней. Тогда верно равенство ВР+Г=2. ( ) Число = В Р + Г называется эйлеровой характеристикой многогранника. Согласно теореме Эйлера, для выпуклого многогранника эта характеристика равна 2. То, что эйлерова характеристика равна 2 для многих знакомых нам многогранников, видно из следующей таблички:
Многогранник тетраэдр ку б октаэдр

В
4 8 6

Р
6 12 12

Г
4 6 8

2 2 2

n-угольная
пирамида n-угольная призма

n + 1 2n n + 1 2
2n 3n n + 2 2


В действительности мы докажем более общую теорему, которая верна не только для выпуклых многогранников, но для произвольных графов на сфере. Поместим внутри выпуклого многогранника M сферу S. Центр O сферы S также лежит внутри многогранника M. Спроектируем многогранник M из центра O на сферу. Так как многогранник выпуклый, то всякий луч с началом в точке O, лежащей внутри многогранника, пересекает многогранник в единственной точке, которая проектируется в некоторую точку на сфере. Так что проектирование является взаимно однозначным соответствием между точками многогранника и точками сферы. При этом вершины много-

гранника проектируются в точки на сфере, а ребра проектируются в дуги больших окружностей. Эти точкивершины и дуги-ребра образуют граф G, расположенный на сфере S. Ребра этого графа разбивают сферу на области, которые являются проекциями граней многогранника. Футбольный мяч, сшитый из пятиугольников и шестиугольников, можно рассматривать как проекцию многогранника на сферу (рис.4). Рассмотрим теперь на сфере совершенно произвольный граф G, состоящий из В вершин и P ребер. Каждое ребро имеет два конца, являющиеся вершинами графа. При этом предполагаем, что любые два ребра либо имеют общую вершину, либо не пересекаются вовсе. Граф G, вообще говоря, может распадаться на некоторое число K связных частей (компонентов). В каждом компоненте, по определению, от любой вершины к любой другой вершине компонента можно перейти по цепочке ребер из графа. И, наоборот, вершины из разных компонентов связать реберным путем невозможно. Граф разбивает сферу на какое-то число Г связных областей. Например, граф G на рисунке 5 имеет 18 вершин, 12 ребер, 3 области ('нос', 'рот' и все остальное). Граф состоит из 8 связных компонентов. Если граф G является проекцией выпуклого многогранника на сферу,

.5

то число В вершин графа это число вершин многогранника, число Р ребер графа это число ребер многогранника, число Г областей на сфере это число граней многогранника, а число K компонентов равно 1. Обобщенная теорема Эйлера. Для графа на сфере верно равенство В Р + Г K = 1. ( ) Доказательство. Заметим, что так как для выпуклого многогранника

K = 1, то из этой теоремы немедленно вытекает 'обычная' теорема Эйлера для выпуклого многогранника. Рассмотрим теперь особый граф, который назовем 'звездное небо'. Этот граф содержит лишь одни вершины и не содержит ни одного ребра. Такой граф действительно напоминает совокупность звезд на небесной сфере. Он состоит из некоторого числа В вершин. Так как в графе нет ребер, то сфера не разбивается на различные области, т.е. Г = 1. По той же причине отсутствия ребер в графе столько же компонентов, сколько вершин: В = K. Поэтому для 'звездного неба' обобщенная формула () верна: В 0 + 1 K = 1. Обобщенная формула Эйлера верна и для графа на рисунке 5, а именно: 18 12 + 3 8 = 1. Пусть G произвольный граф, содержащий ребро. Мы покажем, что из графа G можно выбросить ребро так, что для старого графа G и нового графа G соответствующие суммы равны: B - P + Г - K = B - - P + Г - K . Возможны два случая. 1) Пусть в графе G существует ребро e со свободным концом, т.е. хотя бы один конец у ребра e не принадлежит никакому другому ребру. Например, в графе на рисунке 5 ребро из 'брови' имеет свободный конец. Удалим это ребро. Условимся, что, удаляя ребро e, мы оставляем обе его концевые вершины. Таким образом, для нового графа имеем: B = B , P = P - 1 . Так как у ребра e хотя бы один конец был свободным, то к ребру e с обеих его сторон прилегает одна и та же область. Другими словами, это ребро не разделяет в графе G никаких двух областей. Поэтому удаление ребра e не приводит к уменьшению числа областей в графе G : Г = Г . А вот число компонентов при удалении ребра со свободным концом увеличивается на 1 за счет того, что две концевые вершины ребра e в графе G принадлежат одному компоненту, а после удаления ребра разным. Итак, K = K + 1. Поэтому у графа G сумма B - P + Г - K = = B - P -1 + Г - K +1 =
= B-P+Г -K та же, что и у G. 2) А что делать, если в графе G нет ни одного ребра со свободным кон-

>

C

>

C

.4
3 Квант ? 5