Цикл (теория графов)
В теории графов цикл — это в графе непустой след только первая и последняя вершины , в котором равны . Ориентированный цикл в ориентированном графе — это непустой ориентированный путь , в котором равны только первая и последняя вершины.
Граф без циклов называется ациклическим графом . Ориентированный граф без ориентированных циклов называется ориентированным ациклическим графом . без Связный граф циклов называется деревом .
Определения [ править ]
Схема и цикл [ править ]
- Пусть G = ( V , E , Φ ) — граф. Схема — это непустой след ( e 1 , e 2 , ..., ) en с последовательностью вершин ( v 1 , v 2 , ..., v n , v 1 ) .
- Цикл — это схема , или простая схема в которой равны только первая и последняя вершины. [1]
- n называется длиной цепи соотв. длина цикла .
Направленная цепь и направленный цикл [ править ]
- Ориентированная цепь — это непустая направленная трасса, в которой первая и последняя вершины равны ( замкнутая направленная трасса ). [1]
- Пусть G = ( V , E , Φ ) — ориентированный граф. Ориентированная цепь — это непустая направленная трасса e 1 , e 2 , ..., en ( ) с последовательностью вершин ( v 1 , v 2 , ..., v n , v 1 ) .
- или Ориентированный цикл простой ориентированный контур — это ориентированный контур, в котором равны только первая и последняя вершины. [1]
- n называется длиной направленной цепи соотв. длина направленного цикла .
Безаккордовый цикл [ править ]
в Безхордовый цикл графе, также называемый дыркой или индуцированным циклом, — это цикл, в котором никакие две вершины цикла не соединены ребром, которое само не принадлежит циклу. Антидыра — это дополнение к дырке в графе. Бесхордовые циклы могут использоваться для характеристики совершенных графов : согласно сильной теореме о совершенном графе , граф совершенен тогда и только тогда, когда ни одна из его дырок или антидыр не имеет нечетного числа вершин, большего трех. , Хордальный граф особый тип совершенного графа, не имеет дыр размером больше трех.
Обхват графа — это длина его кратчайшего цикла; этот цикл обязательно безаккордовый. Клетки определяются как наименьшие правильные графы с заданными комбинациями степени и обхвата.
Периферийный цикл — это цикл в графе, обладающий тем свойством, что каждые два ребра, не входящие в цикл, могут быть соединены путем, внутренние вершины которого выходят за пределы цикла. В графе, который не образован добавлением одного ребра к циклу, периферийный цикл должен быть индуцированным циклом.
Циклическое пространство [ править ]
Термин цикл может также относиться к элементу пространства циклов графа. Существует множество циклических пространств, по одному на каждое поле коэффициентов или кольцо. Наиболее распространенным является пространство двоичных циклов (обычно называемое просто пространством циклов ), которое состоит из наборов ребер, имеющих четную степень в каждой вершине; оно образует векторное пространство над двухэлементным полем . По теореме Веблена каждый элемент пространства циклов может быть образован как непересекающееся по ребрам объединение простых циклов. Базис циклов графа — это набор простых циклов, образующий базис пространства циклов. [2]
Используя идеи алгебраической топологии , пространство двоичных циклов обобщается на векторные пространства или модули над другими кольцами, такими как целые, рациональные или действительные числа и т. д. [3]
Обнаружение цикла [ править ]
Существование цикла в ориентированных и неориентированных графах можно определить по тому, находит ли поиск в глубину (DFS) ребро, которое указывает на предка текущей вершины (т. е. оно содержит заднее ребро ). [4] Все задние ребра, которые пропускает DFS, являются частью циклов. [5] В неориентированном графе ребро родительского узла не должно считаться задним ребром, но обнаружение любой другой уже посещенной вершины будет указывать на заднее ребро. В случае неориентированных графов всего O ( n -вершинном графе требуется для нахождения цикла в n ) времени , поскольку не более n − 1 ребер могут быть ребрами дерева.
Многие алгоритмы топологической сортировки также обнаруживают циклы, поскольку они являются препятствиями для существования топологического порядка. Кроме того, если ориентированный граф разделен на сильно связные компоненты , циклы существуют только внутри компонентов, а не между ними, поскольку циклы сильно связны. [5]
Для ориентированных графов можно использовать распределенные алгоритмы на основе сообщений. Эти алгоритмы основаны на идее, что сообщение, отправленное вершиной в цикле, вернется к самому себе. Алгоритмы обнаружения распределенных циклов полезны для обработки крупномасштабных графов с использованием системы распределенной обработки графов в компьютерном кластере (или суперкомпьютере).
Приложения обнаружения циклов включают использование графиков ожидания для обнаружения взаимоблокировок в параллельных системах. [6]
Алгоритм [ править ]
Вышеупомянутое использование поиска в глубину для поиска цикла можно описать следующим образом:
For every vertex v: visited(v) = finished(v) = false For every vertex v: DFS(v)
где
DFS(v) =
if finished(v): return
if visited(v):
"Cycle found"
return
visited(v) = true
for every neighbour w: DFS(w)
finished(v) = true
Для неориентированных графов «сосед» означает все вершины, связанные с v , за исключением той, которая рекурсивно вызывается DFS(v) . Это упущение не позволяет алгоритму найти тривиальный цикл вида v → w → v ; они существуют в каждом неориентированном графе хотя бы с одним ребром.
Вариант, использующий вместо этого поиск в ширину, найдет цикл наименьшей возможной длины.
Покрытие графиков циклом [ править ]
В своей статье 1736 года о семи мостах Кенигсберга , которую многие считают рождением теории графов, Леонард Эйлер доказал, что для конечного неориентированного графа существует замкнутый обход, который посещает каждое ребро ровно один раз (что делает его замкнутым маршрутом), необходимо и достаточно, чтобы оно было связным, за исключением изолированных вершин (т. е. все ребра содержались в одной компоненте) и имело четную степень в каждой вершине. Соответствующая характеристика существования замкнутого маршрута, посещающего каждое ребро ровно один раз в ориентированном графе, состоит в том, что граф сильно связен и имеет одинаковое количество входящих и исходящих ребер в каждой вершине. В любом случае результирующий замкнутый след известен как Эйлеров след . Если конечный неориентированный граф имеет четную степень в каждой своей вершине, независимо от того, связен ли он, то можно найти набор простых циклов, которые вместе покрывают каждое ребро ровно один раз: это теорема Веблена . [7] Когда связный граф не удовлетворяет условиям теоремы Эйлера, замкнутый обход минимальной длины, охватывающий каждое ребро хотя бы один раз, тем не менее может быть найден за полиномиальное время путем решения задачи проверки маршрута .
Гораздо сложнее найти один простой цикл, который покрывает каждую вершину ровно один раз, а не ребра. Такой цикл известен как гамильтонов цикл , и определение его существования является NP-полным . [8] Было опубликовано много исследований, касающихся классов графов, которые могут гарантированно содержать гамильтоновы циклы; Одним из примеров является теорема Ора о том, что гамильтонов цикл всегда можно найти в графе, для которого каждая несмежная пара вершин имеет степени, сумма которых равна как минимум общему числу вершин в графе. [9]
утверждает Гипотеза о двойном покрытии цикла , что для каждого графа без мостов существует мультимножество простых циклов, которое покрывает каждое ребро графа ровно дважды. Доказать, что это правда (или найти контрпример) остается открытой проблемой. [10]
Классы графов, определенные циклом [ править ]
Несколько важных классов графов могут быть определены или охарактеризованы с помощью их циклов. К ним относятся:
- Двудольный граф , граф без нечетных циклов (циклов с нечетным числом вершин)
- Граф кактуса — граф, в котором каждый нетривиальный двусвязный компонент является циклом.
- Циклический график — график, состоящий из одного цикла.
- Хордальный граф — граф, в котором каждый индуцированный цикл представляет собой треугольник.
- Ориентированный ациклический граф — ориентированный граф без ориентированных циклов.
- Линейный совершенный граф — граф, в котором каждый нечетный цикл представляет собой треугольник.
- Совершенный граф , граф без индуцированных циклов или их дополнений нечетной длины, большей трех.
- Псевдолес — граф, в котором каждый связный компонент имеет не более одного цикла.
- Удушенный граф — граф, в котором каждый периферийный цикл представляет собой треугольник.
- Сильно связный граф — ориентированный граф, в котором каждое ребро является частью цикла.
- Граф без треугольников — граф без трехвершинных циклов.
- Граф без четных циклов — граф без четных циклов.
- Граф без четных дырок — граф без четных циклов длиной больше или равной 6.
См. также [ править ]
- Велосипедное пространство
- Основа цикла
- Обнаружение цикла в последовательности повторяющихся значений функции
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б с д Бендер и Уильямсон 2010 , с. 164.
- ^ Гросс, Джонатан Л.; Йеллен, Джей (2005), «4.6 Графы и векторные пространства» , Теория графов и ее приложения (2-е изд.), CRC Press, стр. 197–207, ISBN 9781584885054 , заархивировано из оригинала 4 февраля 2023 г. , получено 27 сентября 2016 г.
- ^ Дистель, Рейнхард (2012), «1.9 Некоторые линейные алгебры» , Теория графов , Тексты для выпускников по математике, том. 173, Springer, стр. 23–28, заархивировано из оригинала 4 февраля 2023 г. , получено 27 сентября 2016 г.
- ^ Такер, Алан (2006). «Глава 2: Покрытие схем и раскраски графов». Прикладная комбинаторика (5-е изд.). Хобокен: Джон Уайли и сыновья. п. 49. ИСБН 978-0-471-73507-6 .
- ^ Jump up to: Перейти обратно: а б Седжвик, Роберт (1983), «Графовые алгоритмы», Алгоритмы , Аддисон-Уэсли, ISBN 0-201-06672-6
- ^ Зильбершац, Авраам; Питер Гэлвин; Грег Ганье (2003). Концепции операционной системы . John Wiley & Sons, INC., стр. 260 . ISBN 0-471-25060-0 .
- ^ Веблен, Освальд (1912), «Применение модульных уравнений в анализе ситуации», Annals of Mathematics , Second Series, 14 (1): 86–94, doi : 10.2307/1967604 , JSTOR 1967604 .
- ^ Ричард М. Карп (1972), «Сводимость среди комбинаторных задач» (PDF) , в Р.Э. Миллере и Дж. Тэтчере (ред.), Сложность компьютерных вычислений , Нью-Йорк: Пленум, стр. 85–103, заархивировано (PDF) с сайта оригинал 10 февраля 2021 г. , получен 12 марта 2014 г.
- ^ Оре, Ø. (1960), «Заметки о схемах Гамильтона», American Mathematical Monthly , 67 (1): 55, doi : 10.2307/2308928 , JSTOR 2308928 .
- ^ Джагер, Ф. (1985), «Обзор гипотезы о двойном покрытии цикла», Annals of Discrete Mathematics 27 – Cycles in Graphs , North-Holland Mathematics Studies, vol. 27, стр. 1–12, номер документа : 10.1016/S0304-0208(08)72993-1 .
- Балакришнан, В.К. (2005). Очерк теории и проблем теории графов Шаума (изд. [Nachdr.]). МакГроу-Хилл. ISBN 978-0070054899 .
- Бендер, Эдвард А.; Уильямсон, С. Гилл (2010). Списки, решения и графики. С введением в вероятность .