Вікіпедія

Комбінаторика многогранників

галузь математики, що вивчає грані опуклих політопів

Комбінато́рика многогра́нників — це галузь математики, що належить до комбінаторики і комбінаторної геометрії і вивчає питання підрахунку й опису граней опуклих многогранників.

Дослідження в комбінаториці многогранників розпадаються на дві гілки. Математики, які працюють у цій галузі, вивчають комбінаторику многогранників; наприклад, вони шукають нерівності, які описують відносини між числом вершин, ребер і граней різних розмірностей у довільному многограннику, а також вивчають інші комбінаторні властивості многогранників, такі як зв'язність і діаметр (число кроків, необхідних для досягнення будь-якої вершини з будь-якої іншої вершини). Крім того, багато вчених, що працюють у галузі інформатики, використовують фразу «комбінаторика многогранників» для опису досліджень з точного опису граней певних многогранників (особливо, 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].

Див. також ред.

Примітки ред.

  1. ↑ Ziegler, 1995, с. 51.
  2. ↑ Ziegler, 1995, с. 245–246.
  3. ↑ Ziegler, 1995, с. 272.
  4. ↑ а б Ziegler, 1995, с. 246–253.
  5. ↑ Steinitz, 1906.
  6. ↑ McMullen, 1970.
  7. ↑ Ziegler, 1995, с. 254–258.
  8. ↑ Höppner, Ziegler, 2000.
  9. ↑ Balinski, 1961.
  10. ↑ Ziegler, 1995, с. 95–96.
  11. ↑ Ziegler, 1995, с. 103–126.
  12. ↑ Blind, Mani-Levitska, 1987.
  13. ↑ Kalai, 1988.
  14. ↑ Friedman, 2009.
  15. ↑ Santos, 2012.
  16. ↑ Kalai, Kleitman, 1992.
  17. ↑ Naddef, (1989).
  18. ↑ Haase, Kiefer, 2015, с. Thm. 5.
  19. ↑ Ziegler, 2000.

Література ред.

  • Michel L. Balinski. On the graph structure of convex polyhedra in n-space // Pacific Journal of Mathematics. — 1961. — Т. 11. — С. 431–434. — DOI:10.2140/pjm.1961.11.431..
  • Roswitha Blind, Peter Mani-Levitska. Puzzles and polytope isomorphisms // Aequationes Mathematicae. — 1987. — Т. 34, вип. 2-3. — С. 287–297. — DOI:10.1007/BF01830678..
  • William Cook, Paul D. Seymour. Polyhedral Combinatorics. — American Mathematical Society, 1989. — (DIMACS Series in Discrete Mathematics and Theoretical Computer Science) — ISBN 978-0-8218-6591-0..
  • Eric J. Friedman. Finding a simple polytope from its graph in polynomial time // Discrete and Computational Geometry. — 2009. — Т. 41, вип. 2. — С. 249–256. — DOI:10.1007/s00454-008-9121-7..
  • Christoph Haase, Stefan Kiefer. The Complexity of the Kth Largest Subset Problem and Related Problems. — 2015.
  • A census of flag-vectors of 4-polytopes. — 2000.. В (Kalai, Ziegler, 2000), стр. 105—110.
  • Gil Kalai. A simple way to tell a simple polytope from its graph // Journal of Combinatorial Theory. — 1988. — Т. 49, вип. 2. — С. 381–383. — (Series A). — DOI:10.1016/0097-3165(88)90064-7..
  • Gil Kalai, Daniel Kleitman. A quasi-polynomial bound for the diameter of graphs of polyhedra // Bulletin of the American Mathematical Society. — 1992. — Т. 26, вип. 2. — С. 315–316. — arXiv:math/9204233. — DOI:10.1090/S0273-0979-1992-00285-9..
  • , ISBN 978-3-7643-6351-2 {{citation}}: Пропущений або порожній |title= (довідка).
  • Peter McMullen. The maximum numbers of faces of a convex polytope // Mathematika. — 1970. — Т. 17. — С. 179–184. — DOI:10.1112/S0025579300002850..
  • Denis Naddef. The Hirsch conjecture is true for (0,1)-polytopes // Mathematical Programming. — 1989. — Т. 45, вип. 1. — С. 109–110. — DOI:10.1007/BF01589099..
  • Francisco Santos. A counterexample to the Hirsch conjecture // Annals of Mathematics. — Princeton University and Institute for Advanced Study, 2012. — Т. 176, вип. 1. — С. 383–412. — arXiv:1006.2814. — DOI:10.4007/annals.2012.176.1.7.
  • Alexander Schrijver. Polyhedral Combinatorics. — Centrum voor Wiskunde en Informatica, 1987..
  • Ernst Steinitz. Über die Eulerschen Polyederrelationen. — Archiv für Mathematik und Physik. — 1906. — Т. 11. — С. 86–88..
  • Günter M. Ziegler. Lectures on Polytopes. — Springer-Verlag, 1995. — Т. 152. — (Graduate Texts in Mathematics) — ISBN 0-387-94365-X..
  • Günter M. Ziegler. Lectures on 0-1 polytopes. — 2000.. В (Kalai, Ziegler, 2000).

Посилання ред.

Отримано з https://uk.wikipedia.org/w/index.php?title=Комбінаторика_многогранників&oldid=42233046