Ориентация (теория графов)
В теории графов ориентация неориентированного графа — это задание направления каждому ребру, превращающее исходный граф в ориентированный .
Ориентированные графы [ править ]
Ориентированный граф называется ориентированным , если ни одна из его пар вершин не соединена двумя симметричными ребрами. Среди ориентированных графов ориентированными являются графы, не имеющие 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]
См. также [ править ]
Ссылки [ править ]
- ^ Дистель, Рейнхард (2005), «1.10 Другие понятия графов», Теория графов (PDF) (3-е изд.), Springer , ISBN 978-3-540-26182-7 .
- ^ Ребане, Джордж; Перл, Иудея (1987), «Восстановление причинных полидеревьев по статистическим данным», Proc. 3-я ежегодная конференция по неопределенности в искусственном интеллекте (UAI 1987), Сиэтл, Вашингтон, США, июль 1987 г. , стр. 222–228, arXiv : 1304.2736 .
- ^ Гипотеза Самнера о универсальном турнире , Дуглас Б. Уэст, получено 2 августа 2012 г.
- ^ Харари, Фрэнк ; Палмер, Эдгар М. (1973), «Формула 5.4.13», Графическое перечисление , Нью-Йорк: Academic Press, стр. 133, МР 0357214 .
- ^ Роббинс, HE (1939), «Теорема о графах с применением к проблеме управления дорожным движением», The American Mathematical Monthly , 46 (5): 281–283, doi : 10.2307/2303897 , hdl : 10338.dmlcz/ 101517 , JSTOR 2303897 .
- ^ Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «Теорема 3.13», Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Гейдельберг: Springer, с. 42, номер домена : 10.1007/978-3-642-27875-4 , ISBN 978-3-642-27874-7 , МР 2920058 .
- ^ де Фрессе, Юбер; Оссона де Мендес, Патрис ; Розенштиль, Пьер (1995), «Возвращение к биполярным ориентациям», Discrete Applied Mathematics , 56 (2–3): 157–179, doi : 10.1016/0166-218X(94)00085-R , MR 1318743 .
- ^ Гуила-Ури, Ален (1962), «Характеризация неориентированных графов, ребра которых могут быть ориентированы так, чтобы получить график отношения порядка», Les Comptes Rends de l'Académie des Sciences , 254 : 1370–1371, MR 0172275 .
- ^ МакКоннелл, РМ; Спинрад, Дж. (1997), «Транзивная ориентация в линейном времени», 8-й симпозиум ACM-SIAM по дискретным алгоритмам , стр. 19–25 .
- ^ Михаил, М.; Винклер, П. (1996), «О количестве эйлеровых ориентаций графа», Algorithmica , 16 (4–5): 402–414, doi : 10.1007/s004539900057 , MR 1407581 .
- ^ Томас, Робин (2006), «Обзор пфаффовой ориентации графов» (PDF) , Международный конгресс математиков. Том. III , Евр. Математика. Soc., Цюрих, стр. 963–984, doi : 10.4171/022-3/47 , ISBN. 978-3-03719-022-7 , МР 2275714