Jump to content

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

(Перенаправлено из Ориентированного графа )

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

Ориентированные графы [ править ]

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

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

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

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

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

Ограниченные ориентации [ править ]

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

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

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

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

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

См. также [ править ]

Ссылки [ править ]

  1. ^ Дистель, Рейнхард (2005), «1.10 Другие понятия графов», Теория графов (PDF) (3-е изд.), Springer , ISBN  978-3-540-26182-7 .
  2. ^ Ребане, Джордж; Перл, Иудея (1987), «Восстановление причинных полидеревьев по статистическим данным», Proc. 3-я ежегодная конференция по неопределенности в искусственном интеллекте (UAI 1987), Сиэтл, Вашингтон, США, июль 1987 г. , стр. 222–228, arXiv : 1304.2736 .
  3. ^ Гипотеза Самнера о универсальном турнире , Дуглас Б. Уэст, получено 2 августа 2012 г.
  4. ^ Харари, Фрэнк ; Палмер, Эдгар М. (1973), «Формула 5.4.13», Графическое перечисление , Нью-Йорк: Academic Press, стр. 133, МР   0357214 .
  5. ^ Роббинс, HE (1939), «Теорема о графах с применением к проблеме управления дорожным движением», The American Mathematical Monthly , 46 (5): 281–283, doi : 10.2307/2303897 , hdl : 10338.dmlcz/ 101517 , JSTOR   2303897 .
  6. ^ Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), «Теорема 3.13», Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Гейдельберг: Springer, с. 42, номер домена : 10.1007/978-3-642-27875-4 , ISBN  978-3-642-27874-7 , МР   2920058 .
  7. ^ де Фрессе, Юбер; Оссона де Мендес, Патрис ; Розенштиль, Пьер (1995), «Возвращение к биполярным ориентациям», Discrete Applied Mathematics , 56 (2–3): 157–179, doi : 10.1016/0166-218X(94)00085-R , MR   1318743 .
  8. ^ Гуила-Ури, Ален (1962), «Характеризация неориентированных графов, ребра которых могут быть ориентированы так, чтобы получить график отношения порядка», Les Comptes Rends de l'Académie des Sciences , 254 : 1370–1371, MR   0172275 .
  9. ^ МакКоннелл, РМ; Спинрад, Дж. (1997), «Транзивная ориентация в линейном времени», 8-й симпозиум ACM-SIAM по дискретным алгоритмам , стр. 19–25 .
  10. ^ Михаил, М.; Винклер, П. (1996), «О количестве эйлеровых ориентаций графа», Algorithmica , 16 (4–5): 402–414, doi : 10.1007/s004539900057 , MR   1407581 .
  11. ^ Томас, Робин (2006), «Обзор пфаффовой ориентации графов» (PDF) , Международный конгресс математиков. Том. III , Евр. Математика. Soc., Цюрих, стр. 963–984, doi : 10.4171/022-3/47 , ISBN.  978-3-03719-022-7 , МР   2275714

Внешние ссылки [ править ]

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: ea809fa56d2b50edd58bb8eda1355b33__1716052200
URL1:https://arc.ask3.ru/arc/aa/ea/33/ea809fa56d2b50edd58bb8eda1355b33.html
Заголовок, (Title) документа по адресу, URL1:
Orientation (graph theory) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)