В теории графов , ориентации из неориентированного графа является присвоение направлению к каждому краю, превращая первоначальный график в ориентированный граф .
Ориентированные графы
Ориентированный граф называется ориентированным, если ни одна из пар его вершин не соединена двумя симметричными ребрами. Среди ориентированных графов ориентированные графы - это те, которые не имеют 2-циклов (то есть не более одного из ( x , y ) и ( y , x ) могут быть стрелками графа). [1]
Турнир является ориентацией полного графа . Polytree является ориентация неориентированного дерева . [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», Graphical Enumeration , Нью-Йорк: 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 , Heidelberg: Springer, p. 42, DOI : 10.1007 / 978-3-642-27875-4 , ЛВП : 10338.dmlcz / 143192 , ISBN 978-3-642-27874-7, MR 2920058.
- ^ де Фрейссе, Юбер; Оссона де Мендес, Патрис ; Rosenstiehl, Пьер (1995), "Bipolar ориентация вновь", Дискретная прикладная математика , 56 (2-3): 157-179, DOI : 10.1016 / 0166-218X (94) 00085-Р , МР 1318743.
- ^ Гуила-Ури, Ален (1962), "Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une Relations d'ordre", Les Comptes rendus de l'Académie des Sciences , 254 : 1370– 1371, Руководство по ремонту 0172275.
- ^ МакКоннелл, РМ; Спинрад, Дж. (1997), "Линейно-временная транзитивная ориентация", 8-й симпозиум ACM-SIAM по дискретным алгоритмам , стр. 19–25..
- ^ Михаил, М .; Винклер П. (1996), "О числе эйлеровых ориентаций графа", Algorithmica , 16 (4-5): 402-414, DOI : 10.1007 / s004539900057 , МР 1407581.
- ^ Томас, Робин (2006), «Обзор пфаффовой ориентации графов» (PDF) , Международный конгресс математиков. Vol. III , Eur. Математика. Soc, Цюрих, стр 963-984,.. DOI : 10,4171 / 022-3 / 47 , ISBN 978-3-03719-022-7, Руководство по ремонту 2275714
Внешние ссылки
- Вайсштейн, Эрик В. , «Ориентация графа» , MathWorld
- Вайсштейн, Эрик В. , «Ориентированный граф» , MathWorld