Ориентация (теория графов) - Orientation (graph theory)
В теории графов , ориентации из неориентированного графа является присвоение направлению к каждому краю, превращая первоначальный график в ориентированный граф .
Ориентированные графы
Ориентированный граф называется ориентированным, если ни одна из пар его вершин не соединена двумя симметричными ребрами. Среди ориентированных графов ориентированные графы - это те, которые не имеют 2-циклов (то есть не более одного из ( x , y ) и ( y , x ) могут быть стрелками графа).
Турнир является ориентацией полного графа . Polytree является ориентация неориентированного дерева . Гипотеза Самнера утверждает, что каждый турнир с 2 n - 2 вершинами содержит каждое многодерево с n вершинами.
Количество неизоморфных ориентированных графов с n вершинами (для n = 1, 2, 3,…) равно
Турниры находятся во взаимно однозначном соответствии с полными ориентированными графами (графами, в которых есть направленное ребро в одном или обоих направлениях между каждой парой различных вершин). Полный ориентированный граф можно преобразовать в ориентированный граф, удалив все 2-цикла, и, наоборот, ориентированный граф может быть преобразован в полный ориентированный граф, добавив 2-цикл между каждой парой вершин, не являющихся конечными точками ребра; эти соответствия взаимно однозначны . Следовательно, та же последовательность чисел также решает проблему перечисления графов для полных орграфов. Для чисел в этой последовательности есть явная, но сложная формула.
Ограниченные ориентации
Сильная ориентация является ориентацией , что приводит к сильно связному графу . Тесно связанные полностью циклические ориентации - это ориентации, в которых каждое ребро принадлежит хотя бы одному простому циклу. Ориентации неориентированного графа G является полностью циклической , если и только если она является сильной ориентацией каждого подключенного компонента из G . Теорема Роббинса утверждает, что граф имеет сильную ориентацию тогда и только тогда, когда он имеет 2-реберную связность ; несвязные графы могут иметь полностью циклическую ориентацию, но только если в них нет мостов .
Ациклическая ориентация является ориентацией , что дает в результате ориентированной ациклический граф . Каждый граф имеет ациклическую ориентацию; все ациклические ориентации можно получить, поместив вершины в последовательность, а затем направив каждое ребро от более ранней из его конечных точек в последовательности к более поздней конечной точке. Теорема Галлаи – Хассе – Роя – Витавера утверждает, что граф имеет ациклическую ориентацию, в которой самый длинный путь имеет не более k вершин тогда и только тогда, когда он может быть раскрашен не более чем в k цветов. Ациклические ориентации и полностью циклические ориентации связаны друг с другом планарной двойственностью . Ациклическая ориентация с одним источником и одним стоком называется биполярной ориентацией .
Транзитивен ориентации является ориентация , так что полученный ориентированный граф является его собственным транзитивное замыкание . Графы с транзитивной ориентацией называются графами сопоставимости ; они могут быть определены из частично упорядоченного набора , сделав два элемента смежными, если они сопоставимы в частичном порядке. Транзитивная ориентация, если таковая существует, может быть обнаружена за линейное время. Однако проверка того, является ли полученная ориентация (или любая заданная ориентация) действительно транзитивной, требует больше времени, поскольку по сложности она эквивалентна умножению матриц .
Эйлерова ориентацией неориентированного графа является ориентацией , в которой каждая вершина имеет равную по-степень и вне степени. Эйлеровы ориентации сеточных графов возникают в статистической механике в теории моделей ледяного типа .
Пфаффова ориентации обладает свойством , что определенные циклы даже длины в графе имеют нечетное число ребер , ориентированных в каждом из двух направлений по всему циклу. Они всегда существуют для плоских графов , но не для некоторых других графов. Они используются в алгоритме FKT для подсчета идеальных совпадений.