St-планарный граф - St-planar graph

В теория графов, ул-планарный граф это биполярная ориентация из плоский график для которого и источник, и сток ориентации находятся на внешней стороне графа. То есть это ориентированный граф, нарисованный без пересечений на плоскости таким образом, что в графе нет направленных циклов, ровно одна вершина графа не имеет входящих ребер, ровно одна вершина графа не имеет исходящих ребер, и эти две обе специальные вершины лежат на внешней грани графа.^[1]

На чертеже каждая грань графа должна иметь одинаковую структуру: есть одна вершина, которая действует как источник грани, одна вершина, которая действует как сток грани, и все ребра внутри грани направлены по двум путям. от истока до раковины. Если вытянуть дополнительный край из раковины ул-планарный граф возвращается к источнику через внешнюю грань, а затем строит двойственный граф (ориентируя каждое двойное ребро по часовой стрелке относительно его прямого ребра), то результат снова будет ул-планарный граф, дополненный таким же ребром.^[1]

Теория порядка

Эти графики тесно связаны с частично упорядоченные наборы и решетки. В Диаграмма Хассе частично упорядоченного множества - это ориентированный ациклический граф, вершинами которого являются элементы множества, с ребром из Икс к у для каждой пары Икс, у элементов, для которых Икс ≤ у в частичном порядке, но для которого не существует z с Икс ≤ у ≤ zЧастично упорядоченный набор образует полную решетку тогда и только тогда, когда каждое подмножество элементов имеет единственную точную нижнюю границу и уникальную наименьшую верхнюю границу, а размер заказа частично упорядоченного набора - наименьшее количество общее количество заказов на одном и том же множестве элементов, пересечение которых является данным частичным порядком. Если вершины ул-плоские графы частично упорядочены по достижимости, тогда этот порядок всегда образует двумерную полную решетку, диаграмма Хассе которой является переходная редукция данного графа. И наоборот, диаграмма Хассе каждой двумерной полной решетки всегда ул-планарный граф.^[2]

Рисование графика

Основываясь на этом свойстве двумерного частичного порядка, каждое ул-планарному графу можно дать рисунок доминирования, в котором для каждых двух вершин ты и v существует путь от ты к v тогда и только тогда, когда обе координаты ты меньше соответствующих координатv.^[3] Координаты такого чертежа также могут использоваться как структура данных который можно использовать, чтобы проверить, есть ли одна вершина ул-планарный граф может достичь другого за постоянное время на запрос. Поворот такого чертежа на 45 ° дает направленный вверх плоский рисунок графа. Направленный ациклический граф грамм имеет направленный вверх плоский рисунок если и только если грамм является подграфом ул-планарный граф.^[4]

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