В теории графов ориентация неориентированного графа — это присвоение направления каждому ребру, превращающее исходный граф в ориентированный граф .
Направленный граф называется ориентированным графом, если ни одна из его пар вершин не связана двумя взаимно симметричными ребрами. Среди направленных графов ориентированными являются те, которые не имеют 2-циклов (то есть не более одной из ( x , y ) и ( y , x ) могут быть стрелками графа). [1]
Турнир — это ориентация полного графа . Полидерево — это ориентация неориентированного дерева . [2] Гипотеза Самнера утверждает, что каждый турнир с 2 n – 2 вершинами содержит каждое полидерево с n вершинами. [3]
Число неизоморфных ориентированных графов с n вершинами (для n = 1, 2, 3, … ) равно
Турниры находятся во взаимно-однозначном соответствии с полными ориентированными графами (графами, в которых есть направленное ребро в одном или обоих направлениях между каждой парой различных вершин). Полный ориентированный граф может быть преобразован в ориентированный граф путем удаления каждого 2-цикла, и наоборот, ориентированный граф может быть преобразован в полный ориентированный граф путем добавления 2-цикла между каждой парой вершин, которые не являются конечными точками ребра; эти соответствия являются биективными . Следовательно, та же последовательность чисел также решает задачу перечисления графов для полных орграфов. Существует явная, но сложная формула для чисел в этой последовательности. [4]
Сильная ориентация — это ориентация, которая приводит к сильно связанному графу . Тесно связанные полностью циклические ориентации — это ориентации, в которых каждое ребро принадлежит по крайней мере одному простому циклу. Ориентация неориентированного графа G является полностью циклической тогда и только тогда, когда она является сильной ориентацией каждого связного компонента G. Теорема Роббинса утверждает , что граф имеет сильную ориентацию тогда и только тогда, когда он 2-ребро связан ; несвязные графы могут иметь полностью циклические ориентации, но только если у них нет мостов . [5]
Ациклическая ориентация — это ориентация, которая приводит к направленному ациклическому графу . Каждый граф имеет ациклическую ориентацию; все ациклические ориентации могут быть получены путем размещения вершин в последовательности, а затем направления каждого ребра от более ранней из его конечных точек в последовательности к более поздней конечной точке. Теорема Галлаи–Хассе–Роя–Витавера утверждает, что граф имеет ациклическую ориентацию, в которой самый длинный путь имеет не более k вершин, тогда и только тогда, когда он может быть раскрашен не более чем в k цветов. [6] Ациклические ориентации и полностью циклические ориентации связаны друг с другом планарной двойственностью . Ациклическая ориентация с одним источником и одним стоком называется биполярной ориентацией . [7]
Транзитивная ориентация — это ориентация, при которой полученный ориентированный граф является своим собственным транзитивным замыканием . Графы с транзитивными ориентациями называются графами сравнимости ; они могут быть определены из частично упорядоченного множества путем создания двух элементов смежными, если они сравнимы в частичном порядке. [8] Транзитивная ориентация, если она существует, может быть найдена за линейное время. [9] Однако проверка того, является ли полученная ориентация (или любая заданная ориентация) на самом деле транзитивной, требует больше времени, поскольку по сложности она эквивалентна умножению матриц .
Эйлерова ориентация неориентированного графа — это ориентация, в которой каждая вершина имеет равную степень входа и выхода. Эйлеровы ориентации графов-решеток возникают в статистической механике в теории моделей типа льда . [10]
Ориентация Пфаффа имеет свойство, что определенные циклы четной длины в графе имеют нечетное число ребер, ориентированных в каждом из двух направлений вокруг цикла. Они всегда существуют для планарных графов , но не для некоторых других графов. Они используются в алгоритме FKT для подсчета совершенных паросочетаний. [11]