Ориентация (теория графов)
Ориентация неориентированного графа — это назначение направлений каждому ребру, что превращает исходный граф в ориентированный граф.
Ориентированные графы
Ориентированный граф называется направленным, если ни одна из его пар вершин не соединена двумя симметричными (разнонаправленными) рёбрами. Среди ориентированных графов эти графы выделяются отсутствием 2-циклов (то есть только одна из дуг Шаблон:Nobreak и Шаблон:Nobreak может присутствовать в графе)Шаблон:Sfn[1].
Турнир — это ориентация полного графа. Шаблон:Не переведено 5 — это ориентация неориентированного дереваШаблон:Sfn. Гипотеза Самнера утверждает, что любой турнир с вершинами содержит любое полидерево с n вершинамиШаблон:R.
Число неизоморфных направленных графов с n вершинами (для n=1, 2, 3, …) равно
- 1; 2; 7; 42; 582; 21,480; 2,142,288; 575,016,219; 415,939,243,032; … (Шаблон:OEIS).
Направленные графы находятся в один-к-одному соответствии с полным ориентированным графами (графами, в которых есть ориентированная дуга между любой парой различных вершин). Полный ориентированный граф может быть преобразован в направленный граф путём удаления всех 2-циклов, и наоборот, направленный граф может быть преобразован в полный ориентированный граф путём добавления 2-цикла между каждой парой вершин, не являющихся концами какой-либо дуги. Эти соответствия биективно. Поэтому та же последовательность чисел решает задачу перечисления графов для полных орграфов. Существует явная, но сложная формула для чисел этой последовательностиШаблон:Sfn.
Ограниченные ориентации
Сильная ориентация — это ориентация, в результате которой получаем сильно связанный орграф. Тесно связанные вполне циклические ориентации — это ориентации, в которых каждая дуга принадлежит по меньшей мере одному простому циклу. Ориентация неориентированного графа G вполне циклическая тогда и только тогда, когда она является сильной ориентацией любой компоненты связности графа G. Теорема Роббинса гласит, что граф имеет сильную ориентацию тогда и только тогда, когда он рёберно 2-связен. Несвязные графы могут иметь вполне циклические ориентации, но только в случае, когда в них нет мостовШаблон:Sfn.
Ациклическая ориентация — это ориентация, которая приводит к ориентированному ациклическому графу. Любой граф имеет ациклическую ориентацию. Все ациклические ориентации можно получить, расположив вершены в ряд, а затем направляя дугу из более ранней вершины в более позднюю в этом ряду. Теорема Галлаи — Хассе — Роя — Витавера утверждает, что граф имеет ациклическую ориентацию, в которой самый длинный путь имеет максимум k вершин, тогда и только тогда, когда его можно раскрасить раскрасить максимум в k цветовШаблон:Sfn. Ациклические ориентации и вполне циклические ориентации связаны друг с другом планарной двойственностью. Ациклическая ориентация с единственным источником и единственным стоком называется биполярной ориентациейШаблон:Sfn.
Транзитивная ориентация — это ориентация, при которой получаемый ориентированный граф является своим транзитивным замыканием. Графы с транзитивными ориентациями называются графами сравнимости. Они могут быть определены из частично упорядоченного множества, если сделать два элемента смежными во всех случаях, когда они сравнимы в частичном порядкеШаблон:Sfn. Транзитивная ориентация, если существует, может быть найдена за линейное времяШаблон:Sfn. Однако проверка, будет ли полученная ориентация (или любая заданная ориентация) действительно транзитивной, требует больше времени, поскольку она по сложности эквивалентна умножению матриц.
Эйлерова ориентация неориентированного графа — это ориентация, в которой каждая вершина имеет одинаковую полустепень захода и полустепень исхода. Эйлерова ориентация решёток появляется в статистической механике в теории Шаблон:Не переведено 5Шаблон:Sfn.
Пфаффова ориентация имеет свойство, что определённые циклы чётной длины в графе имеют нечётное число дуг в двух различных направлениях. Такие ориентации всегда существуют для планарных графов, но не всегда для других типов графов. Эта ориентация используется в алгоритме FKT подсчёта совершенных паросочетанийШаблон:Sfn.
Примечания
Литература
- Шаблон:Книга Перевод:
- Шаблон:КнигаШаблон:Недоступная ссылка
- Шаблон:Книга Перевод:
Ссылки
- ↑ Следует обратить внимание, что в переводе книги Дистеля oriented переводится как направленный, а directed — как ориентированный, то есть понятия переставлены местами. Это может приводить к путанице. В этой статье, как и в других статьях Википедии, приняты определения из русского перевода.