Уникальная ориентация раковины

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

В гиперкубах

Проблема нахождения стока в уникальной ориентации стока гиперкуба была сформулирована как абстракция задач линейной дополнительности Стикни и Уотсоном (1978) , а в 2001 году она была названа «уникальной ориентацией стока» ( Szabó & Welzl 2001 ). может Алгоритм определить уникальный сток $d$ -мерного гиперкуба за время $c д$ для $c < 2$ существенно меньше, чем $2 д$ время, необходимое для проверки всех вершин. Когда ориентация имеет дополнительное свойство, состоящее в том, что ориентация образует ориентированный ациклический граф , что происходит, когда уникальные ориентации стока используются для моделирования задач типа LP , можно найти сток, используя рандомизированный алгоритм в экспоненте ожидаемого времени в квадратном корне. d ( ) Gärtner 2002 .

В простых многогранниках

Простой d d -мерный многогранник — это многогранник, в каждой вершине которого имеется ровно инцидентных ребер. В ориентации простого многогранника с единственным стоком каждое подмножество из k входящих ребер в вершину v определяет k -мерную грань, для которой v является единственным стоком. Следовательно, количество граней всех измерений многогранника (включая сам многогранник, но не пустое множество) можно вычислить как сумму количества подмножеств входящих ребер:

\sum _{v\in G(P)}2^{d_{\operatorname {in} }(v)}

где G ( P ) — график многогранника, а d _in ( v ) — входная степень (количество входящих ребер) вершины v в заданной ориентации ( Kalai 1988 ).

В более общем смысле, для любой ориентации простого многогранника одна и та же сумма подсчитывает количество инцидентных пар грани многогранника и стока грани. А в ациклической ориентации каждая грань должна иметь хотя бы один сток. Следовательно, ациклическая ориентация является уникальной стоковой ориентацией тогда и только тогда, когда не существует другой ациклической ориентации с меньшей суммой. Кроме того, k -регулярный подграф данного графа образует грань многогранника тогда и только тогда, когда его вершины образуют нижнее множество хотя бы для одной ациклической уникальной ориентации стока. Таким образом, решетка граней многогранника однозначно определяется из графа ( Kalai 1988 ). На основе этой структуры решетки граней простых многогранников можно восстановить по их графам за полиномиальное время с помощью линейного программирования ( Фридман, 2009 ).

Ссылки

Фридман, Эрик Дж. (2009), «Нахождение простого многогранника по его графику за полиномиальное время», Discrete & Computational Geometry , 41 (2): 249–256, doi : 10.1007/s00454-008-9121-7 , MR 2471873 .
Калаи, Гил (1988), «Простой способ отличить простой многогранник по его графику», Журнал комбинаторной теории , серия A, 49 (2): 381–383, doi : 10.1016/0097-3165(88)90064- 7 , МР 0964396 .
Матушек, Иржи (2006), «Количество ориентаций уникального стока гиперкуба», Combinatorica , 26 (1): 91–99, CiteSeerX 10.1.1.5.491 , doi : 10.1007/s00493-006-0007-0 , МР 2201286 , S2CID 29950186 .
Шурр, Инго; Сабо, Тибор (2004), «Нахождение стока занимает некоторое время: почти квадратичная нижняя граница для поиска стока уникальных кубов, ориентированных на сток», Discrete & Computational Geometry , 31 (4): 627–642, doi : 10.1007/s00454 -003-0813-8 , hdl : 20.500.11850/50744 , MR 2053502 .
Стикни, Алан; Уотсон, Лэйн (1978), «Орграфовые модели алгоритмов типа Барда для задачи линейной дополнительности», Mathematics of Operations Research , 3 (4): 322–333, doi : 10.1287/moor.3.4.322 , MR 0509668 .
Сабо, Тибор; Велцл, Эмо (2001), «Уникальные стоковые ориентации кубов», 42-й симпозиум IEEE по основам информатики (Лас-Вегас, Невада, 2001) , Лос-Аламитос, Калифорния: Компьютерное общество IEEE, стр. 547–555, CiteSeerX 10.1. 25.01.2115 , номер doi : 10.1109/SFCS.2001.959931 , ISBN 978-0-7695-1116-0 , MR 1948744 , S2CID 6597643 .
Гертнер, Бернд (2002), «Симплекс-алгоритм случайных граней на комбинаторных кубах», Random Structures & Algorithms , 20 (3): 353–381, doi : 10.1002/rsa.10034 .