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

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

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

Источник: Википедия

а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я