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

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

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

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

Турнир — это ориентация полного графа. Полидерево — это ориентация неориентированного дерева[3]. Гипотеза Самнера утверждает, что любой турнир с вершинами содержит любое полидерево с n вершинами[4].

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

1; 2; 7; 42; 582; 21,480; 2,142,288; 575,016,219; 415,939,243,032; … (последовательность A001174 в OEIS).

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

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

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

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

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

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

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


Примечания
  1. Diestel, 2005.
  2. Следует обратить внимание, что в переводе книги Дистеля oriented переводится как направленный, а directed — как ориентированный, то есть понятия переставлены местами. Это может приводить к путанице. В этой статье, как и в других статьях Википедии, приняты определения из русского перевода.
  3. Rebane, Pearl, 1987, с. 222–228.
  4. Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2012-08-02.
  5. Harary, Palmer, 1973, с. 133.
  6. Robbins, 1939, с. 281–283.
  7. Nešetřil, Ossona de Mendez, 2012, с. 42.
  8. de Fraysseix, Ossona de Mendez, Rosenstiehl, 1995, с. 157–179.
  9. Ghouila-Houri, 1962, с. 1370–1371.
  10. McConnell, Spinrad, 1997, с. 19–25.
  11. Mihail, Winkler, 1992, с. 138–145.
  12. Thomas, 2006, с. 963–984.

Литература
  • Reinhard Diestel. 1.10 Other notions of graphs // Graph Theory. — 3rd. — Springer, 2005. — ISBN 3-540-26182-6. Перевод:
    • Рейнгард Дистель. 1.10 Другие виды графов // Теория графов. — Новосибирск: Издательство Института математики, 2002. — ISBN 5-86134-101-X УДК 519.17 ББЛ 22.17.
  • George Rebane, Judea Pearl. The recovery of causal poly-trees from statistical data // Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987. — 1987. — С. 222–228. (недоступная ссылка)
  • Frank Harary, Edgar M. Palmer. Formula 5.4.13 // Graphical Enumeration. — New York: Academic Press, 1973. — С. 133. Перевод:
  • Robbins H. E. A theorem on graphs, with an application to a problem of traffic control // The American Mathematical Monthly. — 1939. — Т. 46, вып. 5. — С. 281–283. — doi:10.2307/2303897. — .
  • Jaroslav Nešetřil, Patrice Ossona de Mendez. Theorem 3.13 // Sparsity: Graphs, Structures, and Algorithms. — Heidelberg: Springer, 2012. — Т. 28. — С. 42. — (Algorithms and Combinatorics). — ISBN 978-3-642-27874-7. — doi:10.1007/978-3-642-27875-4.
  • Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre Rosenstiehl. Bipolar orientations revisited // Discrete Applied Mathematics. — 1995. — Т. 56, вып. 2–3. — С. 157–179. — doi:10.1016/0166-218X(94)00085-R.
  • Alain Ghouila-Houri. Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre // Les Comptes rendus de l'Académie des sciences. — 1962. — Т. 254. — С. 1370–1371.
  • McConnell R. M., Spinrad J. Linear-time transitive orientation // 8th ACM-SIAM Symposium on Discrete Algorithms. — 1997. — С. 19–25.
  • Milena Mihail, Peter Winkler. On the Number of Eularian Orientations of a Graph // Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms. — Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 1992. — С. 138–145. — (SODA '92). — ISBN 0-89791-466-X.
  • Robin Thomas (mathematician). A survey of Pfaffian orientations of graphs // International Congress of Mathematicians. Vol. III. — Eur. Math. Soc., Zürich, 2006. — С. 963–984. — doi:10.4171/022-3/47.

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.