Ориентация (теория графов)

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

Ориентированные графы

Ориентированный граф называется направленным, если ни одна из его пар вершин не соединена двумя симметричными (разнонаправленными) рёбрами. Среди ориентированных графов эти графы выделяются отсутствием 2-циклов (то есть только одна из дуг (x, y) и (y, x) может присутствовать в графе).

Турнир — это ориентация полного графа. Полидерево — это ориентация неориентированного дерева. Гипотеза Самнера утверждает, что любой турнир с 2 n − 2 {displaystyle 2n-2} вершинами содержит любое полидерево с n вершинами.

Число неизоморфных направленных графов с n вершинами (для n=1, 2, 3, …) равно

Направленные графы находятся в один-к-одному соответствии с полным ориентированным графами (графами, в которых есть ориентированная дуга между любой парой различных вершин). Полный ориентированный граф может быть преобразован в направленный граф путём удаления всех 2-циклов, и наоборот, направленный граф может быть преобразован в полный ориентированный граф путём добавления 2-цикла между каждой парой вершин, не являющихся концами какой-либо дуги. Эти соответствия биективно. Поэтому та же последовательность чисел решает задачу перечисления графов для полных орграфов. Существует явная, но сложная формула для чисел этой последовательности.

Ограниченные ориентации

Сильная ориентация — это ориентация, в результате которой получаем сильно связанный орграф. Тесно связанные вполне циклические ориентации — это ориентации, в которых каждая дуга принадлежит по меньшей мере одному простому циклу. Ориентация неориентированного графа G вполне циклическая тогда и только тогда, когда она является сильной ориентацией любой компоненты связности графа G. Теорема Роббинса гласит, что граф имеет сильную ориентацию тогда и только тогда, когда он рёберно 2-связен. Несвязные графы могут иметь вполне циклические ориентации, но только в случае, когда в них нет мостов.

Ациклическая ориентация — это ориентация, которая приводит к ориентированному ациклическому графу. Любой граф имеет ациклическую ориентацию. Все ациклические ориентации можно получить, расположив вершены в ряд, а затем направляя дугу из более ранней вершины в более позднюю в этом ряду. Теорема Галлаи — Хассе — Роя — Витавера утверждает, что граф имеет ациклическую ориентацию, в которой самый длинный путь имеет максимум k вершин, тогда и только тогда, когда его можно раскрасить раскрасить максимум в k цветов. Ациклические ориентации и вполне циклические ориентации связаны друг с другом планарной двойственностью. Ациклическая ориентация с единственным источником и единственным стоком называется биполярной ориентацией.

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

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

Пфаффова ориентация имеет свойство, что определённые циклы чётной длины в графе имеют нечётное число дуг в двух различных направлениях. Такие ориентации всегда существуют для планарных графов, но не всегда для других типов графов. Эта ориентация используется в алгоритме FKT подсчёта совершенных паросочетаний.