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

Теорема Штайніца — це комбінаторний опис неорієнтованих графів, утворених ребрами й вершинами тривимірного опуклого многогранника — вони точно є (простими) вершинно 3-зв'язними планарними графами (щонайменше з чотирма вершинами). Тобто будь-який опуклий многогранник утворює 3-зв'язний планарний граф, і будь-який 3-зв'язний планарний граф можна подати як опуклий многогранник. З цієї причини 3-зв'язні планарні графи називають також поліедральними.

Теорему названо ім'ям Ернста Штайніца, який опублікував перше доведення цього результату 1916 року. Бранко Ґрюнбаум назвав цю теорему «найважливішим і найглибшим результатом про тривимірні політопи».

Назву «теорема Штайніца» також застосовують до інших результатів Штайніца:

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

Твердження теореми

Висвітлення скелета опуклого багатогранника точковим джерелом світла, близьким до однієї з його граней, дає тінь у вигляді плоскої діаграми Шлегеля.

Неорієнтований граф — це система вершин і ребер, кожне ребро поєднує дві вершини. З будь-якого многогранника можна утворити граф, якщо за вершини графа прийняти вершини многогранника і з'єднати ребром дві вершини графа, якщо відповідні вершини многогранника є кінцевими точками його ребер. Цей граф відомий як одновимірний кістяк многогранника.

Граф є планарним, якщо його вершини можна позначити точками на площині і намалювати на цій площині ребра графа як криві, що з'єднують ці точки, так, щоб жодні два ребра не перетиналися, а точка лежала на кривій, тільки якщо вершина є кінцевою точкою відповідного ребра. За теоремою Фарі можна вважати, що криві, насправді, є відрізками. Граф вершинно 3-зв'язний, якщо після видалення будь-яких двох його вершин будь-яку пару з решти вершин можна з'єднати шляхом.

Теорема Штайніца в одному напрямку (простішому для доведення) стверджує, що граф будь-якого опуклого многогранника є планарним і 3-зв'язним. Як показано на малюнку, планарність можна показати за допомогою діаграми Шлегеля — якщо розмістити точкове джерело світла поблизу однієї з граней багатогранника, а з іншого боку розмістити площину, тіні ребер многогранника утворюють планарний граф, укладений у площину таким чином, що ребра графа представлені відрізками. 3-зв'язність графа многогранника є окремим випадком теореми Балінського, що граф будь-якого k-вимірного опуклого многогранника є k-зв'язним.

Твердження в інший, складніший, бік: будь-який планарний 3-зв'язний граф є графом опуклого многогранника.

Посилення та пов'язані результати

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

У будь-якому многограннику, який відповідає даному поліедральному графу $G$, грані є точно циклами в $G$, які не ділять $G$ на дві компоненти. Тобто, видалення з $G$ циклу, відповідного грані, дає зв'язний підграф $G$ (такі цикли називають периферійними). Можна заздалегідь вказати форму будь-якої однієї грані багатогранника — якщо вибрати цикл $C$, який не розділяє графа на частини, і його вершини розташувати у вигляді двовимірного опуклого многокутника $P$, існує поліедральне подання $G$, в якому грань, відповідна $C$, конгруентна $P$. Також завжди є можливість для заданого поліедрального графа $G$ і довільного циклу $C$ знайти реалізацію, за якої $C$ утворює силует реалізації при паралельній проєкції.

Теорему про пакування кіл Кебе — Андрєєва — Терстона можна розглядати як інше посилення теореми Штайніца, що будь-який 3-зв'язний планарний граф можна подати у вигляді опуклого многогранника так, що всі його ребра дотикатимуться до однієї й тієї самої одиничної сфери. Загальніше, якщо $G$ — поліедральний граф і $K$ — гладке тривимірне опукле тіло, можна знайти поліедральне подання $G$, в якому всі ребра дотикаються до $K$.

Див. також

• Вкладення Татта — метод отримання діаграми Шлегеля поліедрального подання графа за допомогою розв'язання системи лінійних рівнянь.