Ориентация (теория графов) - Orientation (graph theory)

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

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

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

А турнир ориентация полный график. А многодерево ориентация неориентированного дерево.[2] Гипотеза Самнера заявляет, что каждый турнир с 2п - 2 вершины содержат каждое многодерево с п вершины.[3]

Количество неизоморфный ориентированные графы с п вершины (для п = 1, 2, 3,…) является

1, 2, 7, 42, 582, 21480, 2142288, 575016219, 415939243032,… (последовательность A001174 в OEIS ).

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

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

А сильная ориентация ориентация, которая приводит к сильно связный граф. Тесно связанные полностью циклические ориентации - это ориентации, в которых каждое ребро принадлежит хотя бы одному простому циклу. Ориентация неориентированного графа грамм полностью цикличен тогда и только тогда, когда он является сильной ориентацией каждого связный компонент из грамм. Теорема Роббинса утверждает, что граф имеет сильную ориентацию тогда и только тогда, когда он 2-кромочно-соединенные; несвязные графы могут иметь полностью циклическую ориентацию, но только если они не имеют мосты.[5]

An ациклическая ориентация ориентация, которая приводит к ориентированный ациклический граф. Каждый граф имеет ациклическую ориентацию; все ациклические ориентации можно получить, поместив вершины в последовательность, а затем направив каждое ребро от более ранней из его конечных точек в последовательности к более поздней конечной точке. В Теорема Галлаи – Хассе – Роя – Витавера. утверждает, что граф имеет ациклическую ориентацию, в которой самый длинный путь имеет не более k вершины тогда и только тогда, когда это может быть цветной максимум с k цвета.[6] Ациклические ориентации и полностью циклические ориентации связаны друг с другом соотношением планарная двойственность. Ациклическая ориентация с одним источником и одним стоком называется биполярная ориентация.[7]

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

An Эйлерова ориентация неориентированного графа - это ориентация, в которой каждая вершина имеет одинаковую внутреннюю и исходящую степень. Эйлеровы ориентации сеточные графики возникать в статистическая механика в теории ледовые модели.[10]

А Пфаффовская ориентация обладает тем свойством, что некоторые циклы четной длины в графе имеют нечетное количество ребер, ориентированных в каждом из двух направлений. Они всегда существуют для планарные графы, но не для некоторых других графиков. Они используются в Алгоритм FKT для подсчета идеальных совпадений.[11]

Смотрите также

Рекомендации

  1. ^ Дистель, Рейнхард (2005), «1.10 Другие понятия графов», Теория графов (PDF) (3-е изд.), Springer, ISBN  978-3-540-26182-7.
  2. ^ Ребане, Джордж; Жемчужина, Иудея (1987), «Восстановление причинных поли-деревьев из статистических данных», в Proc. 3-я ежегодная конференция по неопределенности в искусственном интеллекте (UAI 1987), Сиэтл, Вашингтон, США, июль 1987 г. (PDF), стр. 222–228[постоянная мертвая ссылка ].
  3. ^ Гипотеза Самнера об универсальном турнире, Дуглас Б. Вест, получено 2 августа 2012 г.
  4. ^ Харари, Фрэнк; Палмер, Эдгар М. (1973), «Формула 5.4.13», Графическое перечисление, Нью-Йорк: Academic Press, стр. 133, МИСТЕР  0357214.
  5. ^ Роббинс, Х. (1939), «Теорема о графах в приложении к проблеме управления движением», Американский математический ежемесячник, 46 (5): 281–283, Дои:10.2307/2303897, HDL:10338.dmlcz / 101517, JSTOR  2303897.
  6. ^ Нешетржил, Ярослав; Оссона де Мендес, Патрис (2012), «Теорема 3.13», Разреженность: графики, структуры и алгоритмы, Алгоритмы и комбинаторика, 28, Гейдельберг: Springer, стр. 42, Дои:10.1007/978-3-642-27875-4, HDL:10338.dmlcz / 143192, ISBN  978-3-642-27874-7, МИСТЕР  2920058.
  7. ^ де Фрейссе, Юбер; Оссона де Мендес, Патрис; Розенштиль, Пьер (1995), "Биполярные ориентации снова и снова", Дискретная прикладная математика, 56 (2–3): 157–179, Дои:10.1016 / 0166-218X (94) 00085-R, МИСТЕР  1318743.
  8. ^ Гуила-Хури, Ален (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.
  9. ^ McConnell, R.M .; Спинрад, Дж. (1997), "Линейно-временная транзитивная ориентация", 8-й симпозиум ACM-SIAM по дискретным алгоритмам, стр. 19–25.
  10. ^ Михаил, Милена; Винклер, Питер (1992), "О количестве эулярных ориентаций графа", Материалы третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA '92, Филадельфия, Пенсильвания, США: Общество промышленной и прикладной математики, стр. 138–145, ISBN  978-0-89791-466-6.
  11. ^ Томас, Робин (2006), «Обзор пфаффовых ориентаций графов» (PDF), Международный конгресс математиков. Vol. III, Евро. Математика. Soc., Zürich, pp. 963–984, Дои:10.4171/022-3/47, ISBN  978-3-03719-022-7, МИСТЕР  2275714

внешняя ссылка