Изменения

Перейти к: навигация, поиск

Выпуклая оболочка в n-мерном пространстве

444 байта добавлено, 23:27, 22 января 2014
Нет описания правки
|proof=
[[Файл:3dconvexhullprojection.png|300px|thumb|right|Верхняя грань куба спроецировалась на внешнюю грань графа]]
«Спроецируем» многогранник на плоскость, как на картинке(будем считать общеизвестным фактом, что выпуклый многогранник планарен). Получили планарный граф, по формуле Эйлера имеем <tex>n - n_e + n_f = 2</tex>, где <tex>n_e</tex> — число рёбер, <tex>n_f</tex> — число граней. Каждая грань нашего графа имеет по меньшей мере 3 ребра, каждое ребро инцидентно двум граням, поэтому имеем <tex>2 n_e \geqslant 3 n_f</tex>(если не удаётся это понять, можно представить двудольный граф, где слева грани, а справа рёбра. Из каждого ребра исходит ровно 2 вершины, а в каждую грань входит хотя бы 3). Тогда получаем <tex>n_f \leqslant 2n - 4</tex>, и, подставив это в формулу Эйлера, <tex>n_e \leqslant 3n - 6</tex>.
}}
170
правок

Навигация