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

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

В гиперкубах

Задача нахождения стока в уникальной ориентации стока гиперкуба была сформулирована как абстракция задачи линейной дополнительности к Стикни и Ватсон (1978) и в 2001 году это было названо "уникальной ориентацией раковины" (Сабо и Вельцль 2001). Возможно алгоритм для определения уникальной раковины d-мерный гиперкуб во времени c^d за c < 2, существенно меньше, чем 2^d время, необходимое для изучения всех вершин. Когда ориентация имеет дополнительное свойство, ориентация образует ориентированный ациклический граф, что происходит, когда для моделирования используются уникальные ориентации стоков. Проблемы типа LP, можно найти сток, используя рандомизированный алгоритм в ожидаемом экспоненте времени в квадратном корне из d (Гертнер 2002).

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

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

${displaystyle sum _ {vin G (P)} 2 ^ {d_ {имя оператора {in}} (v)}}$

куда грамм(п) - график многогранника, а d_в(v) это в степени (количество входящих ребер) вершины v в данной ориентации (Калаи 1988).

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

Рекомендации

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