Меню

Главная
Случайная статья
Настройки
Ориентация (теория графов)
Материал из https://ru.wikipedia.org

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

Содержание

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

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


Литература
  • 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. — .
  • 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. Caractrisation des graphes non orients dont on peut orienter les arrtes de manire obtenir le graphe d'une relation d'ordre // Les Comptes rendus de l'Acadmie des sciences. — 1962. — Т. 254. — С. 1370–1371.


Ссылки
Downgrade Counter