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

Эта статья о теореме о графиках многогранников. Чтобы узнать о других значениях, см. теорему Стейница (значения) .

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

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

Теорема появляется в публикации Эрнста Стейница 1922 года . в честь которого он назван. Это можно доказать с помощью математической индукции (как это сделал Стейниц), найдя состояние с минимальной энергией двумерной пружинной системы и перенося результат в три измерения, или используя теорему об упаковке кругов .Известно несколько расширений теоремы, в которых многогранник, реализующий заданный граф, имеет дополнительные ограничения; например, каждый граф многогранника является графиком выпуклого многогранника с целочисленными координатами или графиком выпуклого многогранника, все ребра которого касаются общей средней сферы .

Определения и формулировка теоремы

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

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

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

Доказательства

Иллюстрация доказательства теоремы Балинского , показывающая нулевое множество линейной функции (синий), проходящей через две заданные вершины (желтый), и пути симплексного метода, соединяющие оставшийся граф (зеленый).

Одно направление теоремы Стейница (направление, которое легче доказать) гласит, что график каждого выпуклого многогранника плоский и 3-связный. Как показано на иллюстрации, планарность можно показать с помощью диаграммы Шлегеля : если разместить источник света возле одной грани многогранника, а плоскость - с другой стороны, тени ребер многогранника образуют плоский граф, вложенный таким образом, чтобы края представляли собой отрезки прямых линий. 3-связность многогранного графа является частным случаем теоремы Балинского о том, что график любого $k$-мерный выпуклый многогранник $k$- связан. Связность графа многогранника после удаления всех $k-1$ его вершин, можно доказать, выбрав еще одну вершину $v$, находя линейную функцию , равную нулю на результирующем множестве $k$ вершины и следуя путям, созданным симплекс-методом, чтобы соединить каждую вершину с одной из двух крайних вершин линейной функции с выбранной вершиной $v$ подключен к обоим.

Другое, более сложное направление теоремы Стейница утверждает, что каждый плоский 3-связный граф является графиком выпуклого многогранника. Для этой части есть три стандартных подхода: доказательства по индукции, подъем двумерных вложений Тутте в три измерения с использованием соответствия Максвелла – Кремоны и методы, использующие теорему об упаковке кругов для создания канонического многогранника .

Индукция

ΔY- и YΔ-преобразования многогранника

Хотя первоначальное доказательство Стейница не было выражено в терминах теории графов, оно может быть переписано в этих терминах и включает в себя поиск последовательности ΔY- и YΔ-преобразований , которые сводят любой трехсвязный плоский граф к $K_{4}$, график тетраэдра. YΔ-преобразование удаляет вершину третьей степени из графа, добавляя ребра между всеми ее бывшими соседями, если эти ребра еще не существовали; обратное преобразование, ΔY-преобразование, удаляет ребра треугольника из графа и заменяет их новой вершиной третьей степени, смежной с теми же тремя вершинами. Как только такая последовательность найдена, ее можно перевернуть и преобразовать в геометрические операции, которые шаг за шагом создают желаемый многогранник, начиная с тетраэдра. Каждое YΔ-преобразование в обратной последовательности можно выполнить геометрически, отсекая вершину третьей степени от многогранника. ΔY-преобразование в обратной последовательности может быть выполнено геометрически путем удаления треугольной грани из многогранника и продления соседних граней до точки их пересечения, но только тогда, когда эта тройная точка пересечения трех соседних граней находится на дальней стороне многогранника. удаленную грань многогранника. Когда тройная точка пересечения не находится на дальней стороне этой грани, проективного преобразования многогранника достаточно, чтобы переместить его на правильную сторону. Следовательно, индукцией по количеству ΔY- и YΔ-преобразований, необходимых для приведения данного графа к $K_{4}$, каждый многогранный граф можно реализовать как многогранник.

Более поздняя работа Епифанова усилила доказательство Стейница о том, что любой многогранный граф можно свести к $K_{4}$ путем ΔY- и YΔ-преобразований. Епифанов доказал, что если в плоском графе указаны две вершины, то граф можно свести к одному ребру между этими терминалами, комбинируя ΔY- и YΔ-преобразования с последовательно-параллельными сокращениями . Доказательство Епифанова было сложным и неконструктивным, но Трумпер упростил его с помощью методов, основанных на минорах графов . Трумпер заметил, что каждый сеточный граф можно сократить с помощью ΔY- и YΔ-преобразований таким образом, что эта сводимость сохраняется минорами графа и что каждый планарный граф является минором сеточного графа. Эту идею можно использовать для замены леммы Стейница о существовании редукционной последовательности. После этой замены остальную часть доказательства можно провести по индукции так же, как исходное доказательство Стейница. Для этих доказательств, проводимых с использованием любого из способов нахождения последовательностей ΔY- и YΔ-преобразований, существуют полиэдральные графы, требующие нелинейного числа шагов. Точнее, каждый планарный граф можно сократить за число шагов, не более чем пропорциональное $n^{3/2}$, а бесконечное число графов требует числа шагов, по крайней мере пропорционального $n^{3/2}$, где $n$ — количество вершин в графе.

Альтернативная форма индукционного доказательства основана на удалении ребер (и сжатии вершин второй степени, которые могут остаться после этого удаления) или сжатии ребер и формировании минора данного плоского графа. Любой многогранный граф можно свести к $K_{4}$ на линейное число этих операций, и снова операции можно обратить, а обратные операции выполнить геометрически, что дает многогранную реализацию графа. Однако, хотя доказать, что последовательность редукции для этого типа аргументов проще, и последовательности редукции короче, геометрические шаги, необходимые для обращения последовательности, более сложны.

Лифтинг

Равновесное напряжение на графике куба

Усеченная пирамида , поднимающая напряженный рисунок (с теми же 2D-позициями) в 3D.

Если граф нарисован на плоскости с прямыми ребрами, то равновесное напряжение определяется как присвоение ребрам ненулевых действительных чисел (весов) со свойством, что каждая вершина находится в положении, заданном средневзвешенным ее значением. соседи. Согласно соответствию Максвелла–Кремоны, равновесное напряжение можно поднять на кусочно-линейную сплошную трехмерную поверхность такую, что края, образующие границы между плоскими частями поверхности, выступают на заданный рисунок. Вес и длина каждого ребра определяют разницу в наклонах поверхности по обе стороны от ребра, и условие, что каждая вершина находится в равновесии со своими соседями, эквивалентно условию, что эти различия в наклоне заставляют поверхность встречаться с поверхностью. себя правильно в окрестности вершины. Положительные веса переводятся в выпуклые двугранные углы между двумя гранями кусочно-линейной поверхности, а отрицательные веса переводятся в вогнутые двугранные углы. И наоборот, каждая непрерывная кусочно-линейная поверхность возникает таким образом из равновесного напряжения. Если нарисован конечный планарный граф и задано равновесное напряжение таким образом, что все внутренние ребра рисунка имеют положительные веса, а все внешние ребра имеют отрицательные веса, то, переведя это напряжение на трехмерную поверхность таким образом, а затем заменив плоскую поверхность, представляющую внешнюю часть графа, его дополнением в той же плоскости, можно получить выпуклый многогранник с дополнительным свойством, заключающимся в том, что его перпендикулярная проекция на плоскость не имеет пересечений.

Соответствие Максвелла-Кремоны использовалось для получения многогранных реализаций многогранных графов путем объединения его с рисования планарных графов методом WT Tutte , вложением Tutte . Метод Тутте начинается с фиксации одной грани многогранного графа в выпуклом положении на плоскости. Эта грань станет внешней грань рисунка графика. Продолжается метод составлением системы линейных уравнений в координатах вершин, согласно которой каждая оставшаяся вершина должна быть помещена в среднее значение ее соседей. Тогда, как показал Татт, эта система уравнений будет иметь единственное решение, в котором каждая грань графа изображается в виде выпуклого многоугольника. Интуитивно это решение описывает структуру, которая будет получена, если заменить внутренние ребра графа идеальными пружинами и позволить им прийти в состояние с минимальной энергией. В результате получается почти равновесное напряжение: если каждому внутреннему ребру присвоить вес, равный единице, то каждая внутренняя вершина рисунка будет находиться в равновесии. Однако не всегда возможно присвоить внешним ребрам отрицательные числа, чтобы они тоже находились в равновесии. Такое присвоение всегда возможно, если внешняя грань представляет собой треугольник, поэтому этот метод можно использовать для реализации любого многогранного графа, имеющего треугольную грань. Если многогранный граф не содержит треугольной грани, его двойственный граф содержит треугольник и также является многогранником, поэтому можно реализовать двойственный граф таким образом, а затем реализовать исходный граф как полярный многогранник двойственной реализации. Альтернативный метод реализации многогранников с использованием поднятий позволяет избежать двойственности, выбирая любую грань, имеющую не более пяти вершин, в качестве внешней грани. У каждого многогранного графа есть такая грань, и, более тщательно выбирая фиксированную форму этой грани, можно устранить вложение Тутте остальной части графа.

Упаковка круга

Многогранник, полученный из круга, уложенного на синюю среднюю сферу. Каждая вершина многогранника представлена ​​в упаковке кружком горизонта (красным). Каждое лицо представлено кругом, образованным его пересечением со сферой.

Согласно одному варианту теоремы об упаковке кругов , для каждого многогранного графа существует система окружностей на плоскости или на любой сфере, представляющая вершины и грани графа, так что:

• каждые две соседние вершины графа изображаются касательными окружностями ,
• каждые две соседние грани графа представлены касательной окружностью,
• каждая пара вершины и грани, которой она касается, представлена ​​кругами, пересекающимися под прямым углом , и
• все остальные пары кругов отделены друг от друга.

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

Реализации с дополнительными свойствами

Целочисленные координаты

Можно доказать более сильную форму теоремы Стейница, что любой многогранный граф может быть реализован выпуклым многогранником, координаты которого являются целыми числами . Например, таким образом можно усилить оригинальное доказательство Стейница, основанное на индукции. Однако целые числа, полученные в результате конструкции Стейница, являются дважды экспоненциальными по числу вершин данного многогранного графа. Запись чисел такой величины в двоичной записи потребовала бы экспоненциального числа битов. Геометрически это означает, что некоторые элементы многогранника могут иметь размер в два раза экспоненциально больший, чем другие, что делает реализации, полученные с помощью этого метода, проблематичными для приложений при рисовании графов .

Последующие исследователи нашли алгоритмы реализации, основанные на подъеме, которые используют только линейное количество бит на вершину. Также возможно ослабить требование, чтобы координаты были целыми числами, и назначить координаты таким образом, чтобы $x$-координаты вершин — различные целые числа в диапазоне от 0 до $2n-4$ а две другие координаты являются действительными числами в единичном интервале , так что длина каждого ребра не меньше единицы, а весь многогранник имеет линейный объем. Известно, что некоторые многогранные графы реализуются на сетках только полиномиального размера; в частности, это верно для пирамид (реализаций колесных графов ), призм (реализаций призменных графов ) и сложенных многогранников (реализаций аполлоновых сетей ).

Другой способ констатировать существование целочисленных реализаций состоит в том, что каждый трехмерный выпуклый многогранник имеет комбинаторно эквивалентный целочисленный многогранник. Например, правильный додекаэдр сам по себе не является целочисленным многогранником из-за своих правильных пятиугольных граней, но его можно реализовать как эквивалентный целочисленный пиритоэдр . Это не всегда возможно в более высоких измерениях, где существуют многогранники (например, построенные на основе конфигурации Перля ), которые не имеют целочисленного эквивалента.

Равные уклоны

Граф Халина — это частный случай многогранного графа, образованного из планарно-вложенного дерева (без вершин второй степени) путем соединения листьев дерева в цикл . Для графов Халина можно выбрать многогранные реализации особого типа: внешний цикл образует горизонтальную выпуклую базовую грань, а каждая вторая грань лежит непосредственно над базовой гранью (как в многогранниках, реализованных подъемом), причем все эти верхние грани имеющие одинаковый наклон. многоугольника Многогранные поверхности с гранями одинакового наклона над любым базовым многоугольником (не обязательно выпуклым) могут быть построены из прямого скелета , и эквивалентный способ описания этой реализации состоит в том, что двумерная проекция дерева на базовую грань образует его прямую поверхность. скелет. Для доказательства этого результата используется индукция: любое корневое дерево можно свести к меньшему дереву, удалив листья из внутреннего узла, все дочерние элементы которого являются листьями, граф Халина, сформированный из меньшего дерева, реализуется по гипотезе индукции, и это можно изменить эту реализацию, чтобы добавить любое количество дочерних листьев к узлу дерева, дочерние элементы которого были удалены.

Уточняем форму лица

В любом многограннике, представляющем данный многогранный граф $G$, лица $G$ это именно циклы в $G$ которые не разделяют $G$ на две составляющие: то есть удаление лицевого цикла из $G$ оставляет остальную часть $G$ как связный подграф. Такие циклы называются периферическими циклами . Таким образом, комбинаторная структура граней (но не их геометрические формы) однозначно определяется из структуры графа. Другое усиление теоремы Стейница, предложенное Барнеттом и Грюнбаумом, гласит, что для любого многогранного графа, любой грани графа и любого выпуклого многоугольника, представляющего эту грань, можно найти многогранную реализацию всего графа, которая имеет заданную форму для обозначенное лицо. Это связано с теоремой Тутте о том, что любой многогранный граф можно нарисовать на плоскости со всеми выпуклыми гранями и любой заданной формой его внешней грани. Однако рисунки плоских графов, полученные методом Тутте, не обязательно переходят в выпуклые многогранники. Вместо этого Барнетт и Грюнбаум доказывают этот результат, используя индуктивный метод. Это также всегда возможно, учитывая многогранный граф $G$ и произвольный цикл $C$ в $G$, найти реализацию, для которой $C$ формирует силуэт реализации при параллельной проекции .

Касательные сферы

Реализация многогранников с использованием теоремы об упаковке кругов обеспечивает еще одно усиление теоремы Стейница: каждый трехсвязный плоский граф может быть представлен как выпуклый многогранник таким образом, что все его ребра касаются одной и той же единичной сферы , средней сферы многогранник. Выполняя тщательно выбранное преобразование Мёбиуса упаковки кругов перед преобразованием ее в многогранник, можно найти многогранную реализацию, которая реализует все симметрии основного графа в том смысле, что каждый автоморфизм графа является симметрией многогранной реализации. . В более общем смысле, если $G$ является многогранным графом и $K$ — любое гладкое трехмерное выпуклое тело , можно найти многогранное представление $G$ у которого все ребра касаются $K$.

Методы упаковки кругов также можно использовать для характеристики графов многогранников, у которых есть описанная сфера, проходящая через все вершины, или сфера, касающаяся всех их граней. (Многогранники с описанной сферой также важны в гиперболической геометрии как идеальные многогранники .) В обоих случаях существование сферы эквивалентно разрешимости системы линейных неравенств о положительных действительных переменных, связанных с каждым ребром графа. В случае сферы сумма этих переменных должна равняться ровно одной в каждом цикле граней графа и более одной в каждом цикле, не являющемся гранью. Двойственно, для описанной сферы переменные должны в сумме давать единицу в каждой вершине и более одной в каждом разрезе с двумя или более вершинами на каждой стороне разреза. Хотя может потребоваться экспоненциально много линейных неравенств, решение (если оно существует) может быть найдено за полиномиальное время, используя метод эллипсоида . Значения переменных из решения определяют углы между парами окружностей в упаковке кругов, соответствующий многогранник которых имеет заданное отношение к своей сфере.

Связанные результаты

Графы трехмерных невыпуклых многогранников могут быть несвязными (слева), и даже для топологически сферических многогранников, грани которых представляют собой простые многоугольники, эти графы могут быть несвязными (справа).

В любой размерности выше трех алгоритмическая задача Стейница состоит в определении того, является ли данная решетка решеткой граней выпуклого многогранника . Маловероятно, что он будет иметь полиномиальную временную сложность, поскольку он NP-труден и более полен для экзистенциальной теории действительных чисел , даже для четырехмерных многогранников, согласно теореме Рихтера-Геберта об универсальности. Здесь экзистенциальная теория действительных чисел представляет собой класс вычислительных задач, которые можно сформулировать в терминах поиска реальных переменных, удовлетворяющих заданной системе полиномиальных уравнений и неравенств. Для алгоритмической задачи Стейница переменными такой задачи могут быть координаты вершин многогранника, а уравнения и неравенства могут использоваться для задания плоскостности каждой грани в заданной решетке граней и выпуклости каждого угла между гранями. Полнота означает, что любая другая проблема в этом классе может быть преобразована в эквивалентный экземпляр алгоритмической задачи Стейница за полиномиальное время. Существование такого преобразования подразумевает, что если алгоритмическая задача Стейница имеет полиномиальное решение по времени, то то же самое имеет и каждая проблема экзистенциальной теории действительных чисел и каждая проблема в NP. Однако, поскольку данный граф может соответствовать более чем одной решетке граней, трудно распространить этот результат о полноте на задачу распознавания графов 4-многогранников. Определение вычислительной сложности этой задачи распознавания графов остается открытым.

Исследователи также нашли теоретико-графовые характеристики графиков некоторых специальных классов трехмерных невыпуклых многогранников. и четырехмерные выпуклые многогранники. Однако в обоих случаях общая проблема остается нерешенной. Действительно, даже проблема определения того, какие полные графы являются графами невыпуклых многогранников (кроме $K_{4}$ для тетраэдра и $K_{7}$ для многогранника Часара ) остается нерешенной.

Теорема Эберхарда частично характеризует мультимножества многоугольников , которые можно объединить в грани выпуклого многогранника. Это можно доказать, сформировав 3-связный плоский граф с заданным набором граней многоугольника, а затем применив теорему Стейница, чтобы найти многогранную реализацию этого графа.

Ласло Ловас показал соответствие между многогранными представлениями графов и матрицами, реализующими графовые инварианты Колена де Вердьера тех же графов. Инвариант Колена де Вердьера — это максимальный коранг взвешенной матрицы смежности графа при некоторых дополнительных условиях, которые не имеют значения для многогранных графов. Это квадратные симметричные матрицы, индексированные по вершинам, с весом вершины $i$ в диагональном коэффициенте $M_{i,i}$ и с весом края $i,j$ в недиагональных коэффициентах $M_{i,j}$ и $M_{j,i}$. Когда вершины $i$ и $j$ не являются соседними, коэффициент $M_{i,j}$ требуется, чтобы оно было равно нулю. Этот инвариант не превосходит трех тогда и только тогда, когда граф является плоским . Как показывает Ловас, когда граф является многогранником, его представление в виде многогранника можно получить, найдя взвешенную матрицу смежности коранга три, найдя три вектора, образующие основу его нулевого пространства , используя коэффициенты этих векторов в качестве координат для вершины многогранника и соответствующее масштабирование этих вершин.

История

История теоремы Стейница описана Грюнбаумом (2007) : который отмечает его первое появление в загадочной форме в публикации Эрнста Стейница , первоначально написанной в 1916 году. Более подробную информацию Стейниц представил в более поздних конспектах лекций, опубликованных после его смерти в 1928 году. Хотя современные трактовки теоремы Стейница утверждают, что она представляет собой теоретико-графовую характеристику многогранников, Стейниц не использовал язык графов. Теоретико-графовая формулировка теоремы была введена в начале 1960-х годов Бранко Грюнбаумом и Теодором Моцкиным , а ее доказательство также было преобразовано в теорию графов в тексте Грюнбаума 1967 года «Выпуклые многогранники» . Работа Епифанова по ΔY- и YΔ-преобразованиям , усиливающим доказательство Стейница, была мотивирована иными проблемами, чем характеризация многогранников. Трумпер (1989) благодарит Грюнбаума за то, что он заметил актуальность этой работы для теоремы Стейница.

Соответствие Максвелла-Кремоны между диаграммами напряжений и многогранными подъемами было развито в серии статей Джеймса Клерка Максвелла с 1864 по 1870 год на основе более ранних работ Пьера Вариньона , Уильяма Рэнкина и других и было популяризировано в конце 19 века Луиджи Кремона . Наблюдение о том, что это соответствие можно использовать с вложением Тутте для доказательства теоремы Стейница, было сделано Идесом и Гарваном (1995) ; см. также Рихтер-Геберт (1996) .

Теорема об упаковке кругов была доказана Полом Кебе в 1936 году. и (самостоятельно) Е. М. Андреева в 1970 г.; он был популяризирован в середине 1980-х годов Уильямом Терстоном , которого (несмотря на цитирование Кебе и Андреева) часто называют одним из его первооткрывателей. Версия теоремы Андреева уже была сформулирована как характеризация типа Стейница для некоторых многогранников в гиперболическом пространстве : а использование упаковки кругов для создания многогранников со средними сферами взято из работы Терстона. Проблема характеристики многогранников с вписанными или описанными сферами, в конечном итоге решенная с использованием метода, основанного на реализации упаковки кругов, восходит к неопубликованной работе Рене Декарта около 1630 года. и Якобу Штайнеру в 1832 году; первые примеры многогранников, не имеющих реализации с описанной или внутренней сферой, были приведены Стейницем в 1928 году.