В математике , А уникальная ориентация раковина представляет собой ориентацию ребер многогранника так , что в каждой грани многогранника ( в том числе весь многогранника в качестве одной из граней), имеется ровно одна вершина , для которой все смежные ребра ориентированы внутрь (т.е. в сторону этой вершины). Если многогранник задан вместе с линейной целевой функцией, а ребра ориентированы от вершин с меньшими значениями целевой функции к вершинам с большими целевыми значениями, результатом будет уникальная ориентация стока. Таким образом, уникальные ориентации стоков можно использовать для моделирования линейных программ, а также некоторых нелинейных программ, таких как задача наименьшего круга .
В гиперкубах [ править ]
Задача нахождения мойки в уникальной мойке ориентации гиперкуба была сформулирована как абстракции линейных задач дополнительности по Stickney & Watson (1978) и было названа «уникальная ориентация раковины» в 2001 году ( Сабо & Welzl 2001 ). Это возможно для алгоритма для определения уникальной мойки в г - мерного гиперкуб во время гр д для С <2 , по существу , меньше , чем 2 г время , необходимыми для изучения всех вершин. Когда ориентация имеет дополнительное свойство, что ориентация образует ориентированный ациклический граф, что происходит, когда для моделирования проблем типа LP используются уникальные ориентации стока , можно найти сток с использованием рандомизированного алгоритма с ожидаемым экспоненциальным временем в квадратном корне из d ( Gärtner 2002 ).
В простых многогранниках [ править ]
Простой д - мерный многогранник является многогранник , в котором каждая вершина имеет ровно d падающие края. В ориентации простого многогранника с единственным стоком каждое подмножество из k входящих ребер в вершине v определяет k -мерную грань, для которой v является единственным стоком. Следовательно, количество граней всех измерений многогранника (включая сам многогранник, но не пустое множество) может быть вычислено как сумма количества подмножеств входящих ребер,
где G ( P ) - график многогранника, а d in ( v ) - внутренняя степень (количество входящих ребер) вершины v в данной ориентации ( Kalai 1988 ).
В более общем случае, для любой ориентации простого многогранника одна и та же сумма подсчитывает количество инцидентных пар грани многогранника и стока грани. А в ациклической ориентации каждое лицо должно иметь хотя бы одну раковину. Следовательно, ациклическая ориентация является уникальной ориентацией стока тогда и только тогда, когда нет другой ациклической ориентации с меньшей суммой. Кроме того, k -регулярный подграф данного графа образует грань многогранника тогда и только тогда, когда его вершины образуют нижнее множество по крайней мере для одной ациклической уникальной ориентации стока. Таким образом, решетка граней многогранника однозначно определяется из графа ( Kalai 1988). На основе этой структуры решетки граней простых многогранников могут быть восстановлены по их графам за полиномиальное время с помощью линейного программирования ( Friedman 2009 ).
Ссылки [ править ]
- Фридман, Эрик Дж (2009), " В поисках простого многогранника из его графа в полиномиальное время", Дискретная и Вычислительная геометрия , 41 (2): 249-256, DOI : 10.1007 / s00454-008-9121-7 , МР 2471873.
- Kalai, Gil (1988), "Простой способ отличить простой многогранник от его графа", Журнал комбинаторной теории , серия A, 49 (2): 381–383, doi : 10.1016 / 0097-3165 (88) 90064- 7 , Руководство по ремонту 0964396.
- Matoušek Йиржи (2006), "Число уникальной мойки ориентаций гиперкуба", Combinatorica , 26 (1): 91-99, CiteSeerX 10.1.1.5.491 , DOI : 10.1007 / s00493-006-0007-0 , Руководство по ремонту 2201286 , S2CID 29950186.
- Шурр, Инго; Сабо, Тибор (2004), «Поиск раковины занимает некоторое время: почти квадратичная нижняя оценка для поиска раковины уникальных ориентированных кубов», Дискретная и вычислительная геометрия , 31 (4): 627–642, doi : 10.1007 / s00454 -003-0813-8 , Руководство по ремонту 2053502.
- Стикни, Алан; Уотсон, Лэйн (1978), "Digraph модель алгоритмов Бард-типа для линейной задачи дополнительности", Математика исследования операций , 3 (4): 322-333, DOI : 10.1287 / moor.3.4.322 , MR 0509668.
- Сабо, Тибор; Welzl, Emo (2001), «Уникальные ориентации раковин кубов», 42-й симпозиум IEEE по основам компьютерных наук (Лас-Вегас, штат Невада, 2001) , Лос-Аламитос, Калифорния: Компьютерное общество IEEE, стр. 547–555, CiteSeerX 10.1. 1.25.2115 , DOI : 10,1109 / SFCS.2001.959931 , ISBN 978-0-7695-1116-0, Руководство по ремонту 1948744 , S2CID 6597643.
- Гертнер, Бернд (2002), "Симплексный алгоритм случайных граней на комбинаторных кубах", Случайные структуры и алгоритмы , 20 (3): 353–381, doi : 10.1002 / rsa.10034.
