st -планарный граф
В теории графов st - планарный граф — это биполярная ориентация плоского графа , для которой и источник, и сток ориентации находятся на внешней грани графа. То есть это ориентированный граф, нарисованный без пересечений на плоскости, так, что в графе нет ориентированных циклов, ровно одна вершина графа не имеет входящих ребер, ровно одна вершина графа не имеет выходящих ребер, а эти две Обе специальные вершины лежат на внешней грани графа. [1]
Внутри рисунка каждая грань графа должна иметь одинаковую структуру: есть одна вершина, выполняющая роль источника грани, одна вершина, выполняющая роль стока грани, и все ребра внутри грани направлены по двум путям. от источника к стоку. Если провести дополнительное ребро из стока st -планарного графа обратно к источнику через внешнюю грань, а затем построить двойственный граф (ориентировав каждое двойственное ребро по часовой стрелке относительно его основного ребра), то результатом снова будет st -планарный граф, дополненный таким же образом дополнительным ребром. [1]
Теория порядка
[ редактировать ]Эти графы тесно связаны с частично упорядоченными множествами и решетками . Диаграмма Хассе частично упорядоченного множества представляет собой ориентированный ациклический граф, вершинами которого являются элементы множества, с ребром от x до y для каждой пары x , y элементов, для которых x ≤ y в частичном порядке, но для которых нет существует z с x ≤ y ≤ z .Частично упорядоченный набор образует полную решетку тогда и только тогда, когда каждое подмножество элементов имеет уникальную максимальную нижнюю границу и уникальную наименьшую верхнюю границу, а порядковая размерность частично упорядоченного набора равна наименьшему числу полных порядков в одном и том же наборе. элементы, пересечение которых является заданным частичным порядком.Если вершины st -плоского графа частично упорядочены по достижимости, то это упорядочение всегда образует двумерную полную решетку, диаграмма Хассе которой является транзитивной редукцией данного графа. И наоборот, диаграмма Хассе любой двумерной полной решетки всегда является st -планарным графом. [2]
Рисование графика
[ редактировать ]На основе этого двумерного свойства частичного порядка каждому st -планарному графу можно дать рисунок доминирования , в котором для каждых двух вершин u и v существует путь от u до v тогда и только тогда, когда обе координаты u меньше, чем соответствующие координаты v . [3] Координаты такого рисунка также можно использовать в качестве структуры данных , которую можно использовать для проверки того, может ли одна вершина st -планарного графа достичь другой за постоянное время для каждого запроса. Поворот такого рисунка на 45° дает вверх плоский рисунок графика . Ориентированный ациклический граф G имеет планарный рисунок вверх тогда и только тогда, когда G является подграфом st -планарного графа. [4]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б Ди Баттиста, Джузеппе; Идс, Питер ; Тамассия, Роберто ; Толлис, Иоаннис Г. (1998), «4.2 Свойства плоских ациклических орграфов», Рисование графов: алгоритмы визуализации графов , Прентис Холл , стр. 89–96, ISBN 978-0-13-301615-4 .
- ^ Платт, CR (1976), «Плоские решетки и плоские графы», Журнал комбинаторной теории , сер. Б, 21 (1): 30–39, doi : 10.1016/0095-8956(76)90024-1 .
- ^ Ди Баттиста и др. (1998) , 4.7 Рисунки доминирования, стр. 112–127.
- ^ Ди Баттиста, Джузеппе; Тамассиа, Роберто (1988), «Алгоритмы для плоских представлений ациклических орграфов», Theoretical Computer Science , 61 (2–3): 175–198, doi : 10.1016/0304-3975(88)90123-5 .