Комбінато́рика многогра́нників — це галузь математики, що належить до комбінаторики і комбінаторної геометрії і вивчає питання підрахунку й опису граней опуклих многогранників.
Дослідження в комбінаториці многогранників розпадаються на дві гілки. Математики, які працюють у цій галузі, вивчають комбінаторику многогранників; наприклад, вони шукають нерівності, які описують відносини між числом вершин, ребер і граней різних розмірностей у довільному многограннику, а також вивчають інші комбінаторні властивості многогранників, такі як зв'язність і діаметр (число кроків, необхідних для досягнення будь-якої вершини з будь-якої іншої вершини). Крім того, багато вчених, що працюють у галузі інформатики, використовують фразу «комбінаторика многогранників» для опису досліджень з точного опису граней певних многогранників (особливо, 0-1 многогранників, вершини яких є підмножинами гіперкуба), що виникають із задач цілочисельного програмування.
Грані і вектори підрахунку граней
Грань опуклого многогранника P можна визначити як перетин P і замкнутого півпростору H, такого, що межа H не містить внутрішніх точок P. Розмірність грані дорівнює розмірності цього перетину. 0-вимірні грані — це самі вершини, а 1-вимірні грані (їх називають ребрами) є відрізками, що з'єднують пари вершин. Зауважимо, що це визначення включає як грані порожні множини і весь многогранник P. Якщо P має розмірність d, грані P з розмірністю d − 1 називають фасетами многогранника P, а межі розмірності d − 2 називають гребенями[1]. Межі P можуть бути частково впорядкованими за включенням, утворюючи ґратку граней, що має на вершині сам многогранник P і порожню множину внизу.
Ключовим методом комбінаторики многогранників є розгляд ƒ-вектора многогранника[2] — вектора (f0, f1, …, fd − 1), де fi є числом i-вимірних граней многогранника. Наприклад, куб має вісім вершин, дванадцять ребер і шість граней (фасок), тому його ƒ-вектор дорівнює (8,12,6). Двоїстий многогранник має ƒ-вектор з тими ж числами у зворотному порядку. Так, наприклад, правильний октаедр, двоїстий кубу, має ƒ-вектор (6,12,8). Розширений ƒ-вектор утворюється додаванням одиниць по обох кінцях ƒ-вектора, що відповідає пелічуванню об'єктів усіх рівнів ґратки граней: f−1 = 1 позначає порожню множину як грань, тоді як fd = 1 позначає сам P.
Для куба розширений ƒ-вектор — це (1,8,12,6,1), а для октаедра — (1,6,12,8,1). Хоча вектори цих прикладів унімодальні (зліва направо спочатку зростають, а потім зменшуються), існують многогранники більш високих розмірностей, для яких це не так[3].
Для симпліційних політопів (політопів, кожна грань яких є симплексом) часто перетворюють цей вектор, утворюючи h-вектор. Якщо розглянути елементи ƒ-вектора (без кінцевої 1) як коефіцієнти многочлена f(x) = Σfixd − i − 1 (наприклад, для октаедра це дає многочлен f(x) = x3 + 6x2 + 12x + 8), тоді h-вектор містить коефіцієнти многочлена h(x) = ƒ(x − 1) (знову, для октаедра, h(x) = x3 + 3x2 + 3x + 1)[4]. Як пише Ціґлер, «для різних задач про симпліційні політопи h-вектори значно зручніші для встановлення інформації про кількість граней, ніж f-вектори».
Рівності і нерівності
Найважливіше співвідношення коефіцієнтів ƒ-вектора многогранника — це формула Ейлера Σ(-1)ifi = 0, де підсумовування ведеться за елементами розширеного ƒ-вектора. У тривимірному просторі перенесення двох одиниць з лівого і правого боку розширеного ƒ-вектора (1, v, e, f, 1) в праву частину рівності перетворює рівність до більш звичного вигляду v - e + f = 2. З того факту, що будь-яка грань тривимірного многогранника має щонайменше три ребра, слідує, що 2e ≥ 3f. Використовуючи цей вираз для виключення e і f із формули Ейлера, отримаємо e ≤ 3 v — 6 і f ≤ 2 v — 4. З огляду на двоїстість e ≤ 3 f — 6 і v ≤ 2 f — 4. З теореми Штайніца слідує, що будь-який 3-вимірний цілочисельний вектор, що задовольняє цим рівностям і нерівностям, є ƒ-вектором опуклого многогранника[5].
У більш високих розмірностях стають важливими й інші відношення між числом граней многогранника, зокрема рівняння Дена — Сомервіля, яке, виражене в термінах h-векторів симпліційного політопа, набуває простої форми hk = hd-k для будь-якого k. Варіант цих рівнянь з k = 0 еквівалентний формулі Ейлера, але для d > 3 ці рівняння лінійно незалежні одне від одного і накладають додаткові обмеження на h-вектори (а тому й на ƒ-вектори) [4] .
Ще одна важлива нерівність для числа граней многогранника виходить з теореми про верхню оцінку[en], вперше доведеної МакМалленом[6], яка стверджує, що d-вимірний многогранник з n вершинами може мати не більше граней будь-якої розмірності, ніж суміжнісний многогранник з таким самим числом вершин:
де зірочка означає, що останній член суми повинен бути зменшений удвічі, якщо d парне[7]. В асимптоті з цього випливає, що не може бути більше ніж граней усіх розмірностей.
Навіть для розмірності чотири множина всіх можливих ƒ-векторів опуклих многогранників не утворює опуклої підмножини чотиривимірної цілочисельної ґратки та багато залишається неясним про можливі значеннях цих векторів[8].
Властивості з теорії графів
Поряд з числом граней многогранників дослідники вивчають й інші їхні комбінаторні властивості, такі як властивості графів, одержуваних з вершин і ребер многогранників (їх 1-кістяка).
Теорема Балінського[ru] стверджує, що граф, отриманий таким шляхом з будь-якого d-вимірного опуклого многогранника, є вершинно d-зв'язним[9][10]. У разі тривимірних многогранників цю властивість і планарність можна використати для точного опису графів многогранників — теорема Штайніца стверджує, що G є кістяком тривимірного многогранника тоді і тільки тоді, коли G є вершинно 3-зв'язним планарним графом[11].
Теорема Блайнда і Мані-Левицької[12] (сформульована як гіпотеза Міхою Перле[en]) стверджує, що можна відновити структуру граней простого многогранника за його графом. Тобто, якщо даний неорієнтований граф є кістяком простого многогранника, є тільки один многогранник (з точністю до комбінаторної еквівалентності), для якого граф є кістяком. Ця властивість різко контрастує з властивостями суміжнісних (не простих) многогранників, графи яких є повними — може існувати багато різних суміжнісних многогранників з одним і тим самим графом. Інше доведення цієї теореми дав Калаї[13], а Фрідман[14] показав, як використовувати цю теорему для створення алгоритму з поліноміальних часом для побудови простих многогранників за їхніми графам.
В контексті симплекс-методу лінійного програмування важливо враховувати діаметр многогранника, мінімальне число вершин, які необхідно пройти, щоб досягти будь-якої вершини з будь-якої іншої вершини. Система лінійних нерівностей задачі лінійного програмування визначає межі многогранника допустимих розв'язків задачі і симплекс-метод знаходить оптимальний розв'язок, проходячи шлях по ребрах цього многогранника. Таким чином, діаметр оцінює нижню межу числа кроків цього методу. Спростована гіпотеза Гірша давала сильну верхню оцінку на діаметр[15]. Відома слабша (квазіполіноміальна) верхня оцінка діаметра[16], а гіпотезу Гірша доведено для окремих класів многогранників[17].
Обчислювальні властивості
Визначення того, чи обмежене число вершин заданого многогранника деяким натуральним числом k, є складною задачею і належить класу складності PP[18].
Грані многогранників 0-1
Важливо в контексті методів відсікань[en] цілочисельного програмування мати можливість описати точно фасети (грані) многогранника, на яких лежать вершини, відповідні розв'язкам комбінаторних оптимізаційних задач. Часто такі завдання мають розв'язки, які можна задати бітовими векторами, а відповідні многогранники мають вершини, координатами яких є числа 0 і 1.
Як приклад візьмемо многогранник Біркгофа, множину n × n матриць, які можна утворити опуклими комбінаціями матриць перестановок. Також, вершини цього многогранника можна розуміти як опис усіх виконаних парувань повного двочасткового графа, а задачу лінійної оптимізації на цьому многограннику можна розглядати як задачу пошуку зваженого мінімального виконаного парування. Теорема Біркгофа стверджує, що такий многогранник можна описати за допомогою двох типів лінійних нерівностей. По-перше, кожен елемент матриці невід'ємний, по-друге, для кожного стовпця і для кожного рядка сума елементів матриці дорівнює одиниці. Обмеження на суму по рядках і стовпцях визначають лінійний підпростір розмірності n2 − 2n + 1, в якому лежить многогранник Біркгофа, а обмеження на невід'ємність елементів матриці задають грані многогранника в цьому підпросторі.
Многогранник Біркгофа незвичайний тим, що відомий повний опис його граней. Для багатьох інших 0-1 многогранників існує експоненційно (або суперекспоненційно) багато граней і доступний тільки частковий їх опис[19].
Див. також
- Абстрактний многогранник
- Абстрактна комутативна алгебра[en]
- Симпліційна сфера
Примітки
Література
Посилання
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
