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

Перейти к навигации Перейти к поиску

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

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

[править | править код]

Ориентированный граф называется направленным, если ни одна из его пар вершин не соединена двумя симметричными (разнонаправленными) рёбрами. Среди ориентированных графов эти графы выделяются отсутствием 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 Архивная копия от 27 февраля 2014 на Wayback Machine, 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. — JSTOR 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.