Свойства циклов в графах

Граф с окрашенными рёбрами для иллюстрации пути H-A-B, замкнутого пути или обхода с повторением вершин B-D-E-F-D-C-B и цикла без повторения рёбер или вершин H-D-G-H

В теории графов два типа объектов обычно называются циклами.

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

Циклы без хорд

Цикл без хорд в графе, также называемый дырой или порождённым циклом, – это цикл, в котором никакие две вершины цикла не соединены ребром, разве что это ребро само принадлежит циклу. Антидыра – это дополнение дыры. Графы без хорд можно использовать для описания совершенных графов – согласно строгой теореме о совершенных графах граф является совершенным в том и только в том случае, когда он не содержит дыр и антидыр с нечётным числом вершин больше трёх. Хордальный граф – это специальный тип совершенных графов, в котором нет дыр размером больше трёх.

Обхват графа – это длина наименьшего цикла. Этот цикл обязательно не будет иметь хорд. Клетки – это наименьшие регулярные графы с заданной степенью вершин и обхватом.

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

Пространство циклов

Понятие цикл может также относиться к элементам пространства циклов графа. Оно состоит из множеств рёбер, которые имеют чётную степень для каждой вершины. Множества образуют векторное пространство над конечным полем из двух элементов. Используя методы алгебраической топологии его можно обобщить до векторных пространств или модулей над другими кольцами, такими как целые числа, вещественные числа и т. д. По теореме Веблена любой элемент пространства циклов можно получить путём комбинирования простых циклов. База циклов графа – это множество простых циклов, которые образуют базис пространства циклов[2][3].

Поиск цикла

Неориентированный граф имеет цикл в том и только в том случае, когда поиск в глубину (DFS) находит ребро, которое приводит к уже посещённой вершине (обратная дуга)[4]. Таким же образом, все обратные рёбра, которые алгоритм DFS обнаруживает, являются частями циклов[5]. Для неориентированных графов требуется только время O(n) для нахождения цикла в графе с n вершинами, поскольку максимум n − 1 рёбер могут быть рёбрами дерева.

Ориентированный граф имеет цикл в том и только в том случае, когда DFS находит обратную дугу. Дуги вперёд и поперечные дуги не обязательно говорят о цикле. Многие алгоритмы топологических сортировок также обнаруживают циклы, поскольку они мешают существованию топологического порядка. Если ориентированный граф разделён на компоненты сильной связности, циклы существуют только в компонентах, но не между ними, поскольку циклы сильно связаны[5].

Приложения алгоритмов нахождения циклов включают графы ожидания для нахождения взаимных блокировок в системах с параллельными потоками[6].

Покрытие графов циклами

В работе 1736 года о проблеме семи мостов Кёнигсберга, общепринято считающейся днём рождения теории графов, Леонард Эйлер доказал, что для того, чтобы конечный неориентированный граф имел замкнутый обход всех рёбер ровно по одному разу, необходимо и достаточно, чтобы он был связан и имел чётную степень всех вершин. Соответствующее описание существования замкнутого обхода каждого ребра ровно один раз в ориентированном графе состоит в требовании, чтобы граф был сильно связан и каждая вершина имела одинаковое число входящих и исходящих дуг. В обоих случаях полученный путь известен как эйлеров цикл. Если конечный неориентированный граф имеет чётную степень каждой вершины, независимо от того, связан он или нет, можно найти множество простых циклов, которые покрывают каждое ребро ровно раз – это теорема Веблена[7]. Если связный граф не удовлетворяет условиям теоремы Эйлера, замкнутый обход минимальной длины, покрывающий все рёбра по меньшей мере один раз может быть найден, тем не менее, за полиномиальное время путём решения задачи об инспекции дорог (англ.)русск..

Задача поиска простого цикла, проходящего через каждую вершину ровно один раз, в отличие от покрытия рёбер, намного сложнее. Такие циклы известны как гамильтоновы циклы, и задача определения существуют ли такие циклы NP-полна[8]. Опубликовано множество исследований относительно классов графов, заведомо содержащих гамильтоновы циклы. Примером может служить теорема Оре о том, что гамильтонов цикл может быть найден в графе всегда, если при сложении степеней любой пары несмежных вершин получим по меньшей мере общее число вершин графа[9].

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

Классы графов, определяемые циклами

Некоторые важные классы графов можно определить или описать их циклами. Это:

• Двудольный граф – граф без нечётных циклов.
• Кактус – граф, в котором любая нетривиальная двусвязная компонента является циклом.
• Граф-цикл – граф, состоящий из единственного цикла.
• Хордальный граф – граф, в котором нет порождённых циклов длиной больше трёх.
• Ориентированный ациклический граф – ориентированный граф без циклов.
• Совершенный граф – граф без порождённых циклов нечётной длины более трёх, либо их дополнений.
• Псевдолес – граф, в котором каждая связная компонента имеет максимум один цикл.
• Сильно связный граф – ориентированный граф, в котором любая дуга входит в какой-либо цикл.
• Граф без треугольников – граф, в котором нет циклов длины три.

Примечания

1. ↑ V. K. Balakrishnan. Schaum’s outline of theory and problems of graph theory. – McGraw-Hill, 2005. – ISBN 978-0070054899.
2. ↑ Jonathan L. Gross, Jay Yellen. 4.6 Graphs and Vector Spaces // Graph Theory and Its Applications. – 2nd. – CRC Press, 2005. – С. 197-207. – ISBN 9781584885054.
3. ↑ Reinhard Diestel. 1.9 Some linear algebra // Graph Theory. – Springer, 2012. – Т. 173. – С. 23-28. – (Graduate Texts in Mathematics).. Перевод: Рейнгард Дистель. 1.9 Немного линейной алгебры // Теория графов. – Новосибирск: Издательство Института математики, 2002. – С. 35-40. – ISBN 5-86134-101-X..
4. ↑ Alan Tucker. Chapter 2: Covering Circuits and Graph Colorings // Applied Combinatorics. – 5th. – Hoboken: John Wiley & sons, 2006. – С. 49. – ISBN 978-0-471-73507-6.
5. ↑ 1 2 Robert Sedgewick. Graph algorithms. – Addison-Wesley, 1983. – ISBN 0-201-06672-6.
6. ↑ Abraham Silberschatz, Peter Galvin, Greg Gagne. Operating System Concepts. – John Wiley & Sons, INC., 2003. – С. 260. – ISBN 0-471-25060-0.
7. ↑ Oswald Veblen. An Application of Modular Equations in Analysis Situs // Annals of Mathematics. – 1912. – Т. 14, вып. 1. – С. 86-94.
8. ↑ Richard M. Karp. Complexity of Computer Computations / R. E. Miller and J. W. Thatcher. – New York: Plenum, 1972. – С. 85-103.
9. ↑ Ø. Ore. Note on Hamilton circuits // American Mathematical Monthly. – 1960. – Т. 67, вып. 1. – С. 55.
10. ↑ F. Jaeger. Annals of Discrete Mathematics 27 – Cycles in Graphs. – 1985. – Т. 27. – С. 1-12. – (North-Holland Mathematics Studies). – doi:10.1016/S0304-0208(08)72993-1.

Эта страница в последний раз была отредактирована 25 апреля 2021 в 12:17.

Как только страница обновилась в Википедии она обновляется в Вики 2.

Обычно почти сразу, изредка в течении часа.

Источник

Граф с краями, окрашенными для иллюстрации пути HAB (зеленый), замкнутого пути или обхода с повторяющейся вершиной BDEFDCB (синий ) и цикл без повторяющихся ребер или вершин HDGH (красный).

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

Граф без циклов называется ациклическим графом. Ориентированный граф без ориентированных циклов называется ориентированным ациклическим графом . связный граф без циклов называется деревом .

Определения

Схема, цикл

• A схема – это непустой след , в котором первая вершина равна последней вершине (замкнутый след).

Пусть G = (V, E, ϕ) график. Схема – это непустой след (e 1 , e 2 ,…, e n ) с последовательностью вершин (v 1 , v 2 ,…, v n , v 1).

• A cycle или простая схема – это схема, в которой единственной повторяющейся вершиной является первая / последняя вершина.
• Длина схемы или цикла – это количество задействованных ребер.

Направленная схема, цикл

• A направленная схема не- пустой направленный след , в котором первая вершина равна последней вершине.

Пусть G = (V, E, ϕ) – ориентированный граф. Направленный контур – это непустой направленный след ( e 1 , e 2 ,…, e n ) с последовательностью вершин (v 1 , v 2 ,…, V n , v 1).

• A направленный цикл или простой направленный контур – это направленный контур, в котором единственная повторяющаяся вершина является первой / последней вершиной.

Бесхордовые циклы

На этом графике зеленый цикл (ABCDEFA) не имеет хорды, а красный цикл (GHIJKLG) – нет. Это потому, что ребро KI является хордой.

A бесхордовый цикл в графе, также называемом отверстием или индуцированным циклом, называется такой цикл, в котором никакие две вершины цикла не соединяются ребром, которое не принадлежит циклу. Антидыр – это дополнение дыры графа. Бесхордовые циклы могут использоваться для характеристики совершенных графов : по сильной теореме о совершенных графах граф является совершенным тогда и только тогда, когда ни одна из его дыр или антидырок не имеет нечетного числа вершин, которые больше трех. хордовый граф , особый тип совершенного графа, не имеет отверстий любого размера больше трех.

обхват графа – это длина его кратчайшего цикла; этот цикл обязательно бесхордовый. Клетки определяются как наименьшие регулярные графы с заданными комбинациями степени и обхвата.

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

Пространство цикла

Термин цикл может также относиться к элементу пространства цикла графа. Есть много пространств циклов, по одному для каждого поля или кольца коэффициентов. Наиболее распространенным является пространство двоичных циклов (обычно называемое просто пространством циклов), которое состоит из наборов ребер, имеющих четную степень в каждой вершине; он формирует векторное пространство над двухэлементным полем . По теореме Веблена каждый элемент пространства циклов может быть сформирован как непересекающееся по ребрам объединение простых циклов. базис цикла графа – это набор простых циклов, который формирует базис пространства циклов.

Использование идей из алгебраической топологии , двоичное пространство цикла обобщается на векторные пространства или модули над другими кольцами , такими как целые числа, рациональные или действительные числа и т. д.

Обнаружение цикла

Существование цикла в ориентированных и неориентированных графах можно определить по тому, найдет ли поиск в глубину (DFS) ребро, которое указывает на предка текущей вершины (оно содержит назад edge ) Все задние кромки, которые пропускает DFS, являются частью циклов. В неориентированном графе ребро, ведущее к родительскому узлу, не должно считаться задним, но обнаружение любой другой уже посещенной вершины укажет на заднее ребро. В случае неориентированных графов требуется всего O (n) времени, чтобы найти цикл в n-вершинном графе, поскольку не более n – 1 ребер могут быть ребрами дерева.

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

Для ориентированных графов, основанных на распределенных сообщениях алгоритмы могут быть использованы. Эти алгоритмы основаны на идее, что сообщение, отправленное вершиной в цикле, вернется к самому себе. Алгоритмы обнаружения распределенного цикла полезны для обработки крупномасштабных графов с использованием системы обработки распределенных графов на компьютерном кластере (или суперкомпьютере).

Приложения обнаружения циклов включают использование графиков ожидания для обнаружения взаимоблокировок в параллельных системах.

Покрытие графиков циклами

В своей статье 1736 года о Семи мостах Кенигсберга , которая широко считается рождением теории графов, Леонард Эйлер доказал, что для конечного неориентированного графа должен быть замкнутый обхода, который посещает каждое ребро ровно один раз, необходимо и достаточно, чтобы оно было связным, за исключением изолированных вершин (то есть все ребра содержатся в одной компоненте) и имело четную степень в каждой вершине. Соответствующая характеристика существования замкнутого обхода, посещающего каждое ребро ровно один раз в ориентированном графе, состоит в том, что граф сильно связан и имеет равное количество входящих и исходящих ребер в каждой вершине. В любом случае результирующий обход известен как цикл Эйлера или тур Эйлера. Если конечный неориентированный граф имеет четную степень в каждой вершине, независимо от того, связан ли он, то можно найти набор простых циклов, которые вместе покрывают каждое ребро ровно один раз: это теорема Веблена . Когда связный граф не удовлетворяет условиям теоремы Эйлера, замкнутый обход минимальной длины, покрывающий каждое ребро хотя бы один раз, может быть найден за полиномиальное время путем решения задачи проверки маршрута .

Проблема поиска единственного простого цикла, который покрывает каждую вершину ровно один раз, а не покрывает ребра, намного сложнее. Такой цикл известен как гамильтонов цикл , и определение того, существует ли он, является NP-полным . Было опубликовано много исследований, касающихся классов графов, которые могут гарантированно содержать гамильтоновы циклы; одним из примеров является теорема Оре о том, что гамильтонов цикл всегда можно найти в графе, для которого каждая несмежная пара вершин имеет степени, суммирующие по крайней мере общее количество вершин в графе.

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

Классы графов, определяемые циклами

Некоторые важные классы графов могут быть определены или охарактеризованы своими циклами. К ним относятся:

• Двудольный граф , граф без нечетных циклов (циклы с нечетным числом вершин).
• Граф кактусов , граф, в котором каждая нетривиальная двусвязная компонента является циклом
• Граф циклов , граф, состоящий из одного цикла.
• Хордовый граф , граф, в котором каждый индуцированный цикл представляет собой треугольник
• Направленный ациклический граф , ориентированный граф без циклов
• Линейный идеальный граф , граф, в котором каждый нечетный цикл представляет собой треугольник
• Идеальный граф , граф без индуцированных циклов или их дополнений нечетной длины, превышающей три
• Псевдолес , граф, в котором каждая связная компонента имеет не более одного цикла
• Странгулированный граф , граф, в котором каждый периферийный цикл представляет собой треугольник
• Сильно связанный граф , ориентированный граф, в котором каждое ребро является частью цикла
• Граф без треугольников , граф без трех вершинных циклов

См. также

• Пространство циклов
• Базис цикла
• Обнаружение цикла в последовательности повторенный f значения функции

Литература

• Балакришнан В.К. (2005). Очерк теории и проблем теории графов Шаума ([Nachdr.] Ed.). Макгроу – Хилл. ISBN978-0070054899 .
• Bender, Edward A .; Уильямсон, С. Гилл (2010). Списки, решения и графики. Знакомство с вероятностью .

Источник