Теорема Штайница

Теорема Штайница — это комбинаторное описание неориентированных графов, образованных рёбрами и вершинами трёхмерного выпуклого многогранника — они в точности являются (простыми) вершинно 3-связными планарными графами (по меньшей мере с четырьмя вершинами). То есть любой выпуклый многогранник образует 3-связный планарный граф, и любой 3-связный планарный граф может быть представлен как выпуклый многогранник. По этой причине 3-связные планарные графы называют также полиэдральными.

Теорема Штайница названа именем Эрнста Штайница, который опубликовал первое доказательство этого результата в 1916 году. Бранко Грюнбаум назвал эту теорему «наиболее важным и глубочайшим результатом о 3-мерных многогранниках».

Название «Теорема Штайница» также применимо к другим результатам Штайница:

• лемма Штайница о замещении — о том, что любой базис векторного пространства имеет одно и то же число векторов;
• теорема, что если выпуклая оболочка множества точек содержит единичную сферу, то существует конечное подмножество точек, выпуклая оболочка которого содержит концентрическую сферу меньшего размера;
• векторное обобщение Штайница теоремы Римана о перегруппировке условно сходящихся рядов.

Утверждение теоремы

Освещение скелета выпуклого многогранника из точечного источника света, близкого к одной из его граней, даёт тень в виде плоской диаграммы Шлегеля.

Неориентированный граф — это система вершин и рёбер, каждое ребро соединяет две вершины. Из любого многогранника можно образовать граф, если вершинами графа принять вершины многогранника и соединять ребром две вершины графа, если соответствующие вершины многогранника являются конечными точками его рёбер. Этот граф известен как одномерный остов многогранника.

Граф является планарным, если его вершины можно расположить на плоскости и нарисовать на этой плоскости рёбра графа как кривые, соединяющие эти точки, таким образом, что никакие два ребра не пересекаются, а вершины лежат на таких кривых, если только вершина является конечной точкой соответствующего ребра. По теореме Фари можно считать, что кривые, на самом деле, являются отрезками. Граф вершинно 3-связен, если после удаления любых двух его вершин любую пару из оставшихся вершин можно соединить путём.

Утверждение теоремы Штайница в одном направлении (более простом для доказательства) гласит, что граф любого выпуклого многогранника является планарным и 3-связным. Как показано на рисунке, планарность можно показать с помощью диаграммы Шлегеля — если разместить точечный источник света вблизи одной из граней многогранника, а с другой стороны разместить плоскость, тени рёбер многогранника образуют планарный граф, вложенный в плоскость таким образом, что рёбра графа представлены в виде отрезков. 3-связность графа многогранника является частным случаем теоремы Балинского, что граф любого k-мерного выпуклого многогранника является k-связным.

Утверждение в другую, более сложную, сторону гласит, что любой планарный 3-связный граф является графом выпуклого многогранника.

Усиления и связанные результаты

Можно доказать более строгое утверждение теоремы Штайница, что любой полиэдральный граф можно реализовать как выпуклый многогранник с вершинами, имеющими целые координаты. Целые числа, получающиеся в оригинальном доказательстве Штайница, являются дважды экспоненциальной функцией от числа вершин заданного многогранника. Таким образом, запись этих чисел требует экспоненциального числа бит. Однако в последующих исследованиях найден алгоритм визуализации графов, который требует лишь O(n) бит для каждой вершины. Можно ослабить требование, чтобы все координаты были целыми и назначить координаты таким образом, что x-координаты вершин будут различными целыми числами в интервале [0,2n − 4], а другие две координаты будут вещественными числами из интервала [0,1], так что каждое ребро имеет длину не меньшую единицы, в то время как объём многогранника будет ограничен O(n).

В любом многограннике, который представляет заданный полиэдральный граф G, грани G являются в точности циклами в G, которые не делят G на две компоненты. То есть, удаление цикла, соответствующего грани, из G даёт связный подграф G. Можно заранее указать форму любой одной грани многогранника — если выбрать цикл C, не разделяющий граф на части, и его вершины расположить в виде двумерного выпуклого многоугольника P, то существует полиэдральное представление G, в котором грань, соответствующая C, конгруэнтна P. Также всегда есть возможность для заданного полиэдрального графа G и произвольного цикла C найти реализацию, при которой C образует силуэт реализации при параллельной проекции.

Теорему об упаковке кругов Кёбе — Андреева — Тёрстона можно рассматривать как другое усиление теоремы Штайница, что любой 3-связный планарный граф может быть представлен в виде выпуклого многогранника таким образом, что все его рёбра касаются одной и той же единичной сферы. Более обще, если G — полиэдральный граф и K — гладкое трёхмерное выпуклое тело, можно найти полиэдральное представление G, в котором все рёбра касаются K.

См. также

• Вложение Татта, метод получения диаграммы Шлегеля полиэдрального представления графа с помощью решения системы линейных уравнений.