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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

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