Войти
Граф с краями, окрашенными для иллюстрации пути HAB (зеленый), замкнутого пути или обхода с повторяющейся вершиной BDEFDCB (синий) и цикл без повторяющихся ребер или вершин HDGH (красный). В теории графов, цикл в графе является непустым след, в котором единственными повторяющимися вершинами являются первая и последняя вершины. направленный цикл в ориентированном графе - это непустой направленный след, в котором единственными повторяющимися вершинами являются первая и последняя вершины.
Граф без циклов называется ациклическим графом. Ориентированный граф без ориентированных циклов называется ориентированным ациклическим графом. связный граф без циклов называется деревом.
На этом графике зеленый цикл (ABCDEFA) не имеет хорды, а красный цикл (GHIJKLG) - нет. Это потому, что ребро KI является хордой. A бесхордовый цикл в графе, также называемом отверстием или индуцированным циклом, называется такой цикл, в котором никакие две вершины цикла не соединяются ребром, которое не принадлежит циклу. Антидыр - это дополнение дыры графа. Бесхордовые циклы могут использоваться для характеристики совершенных графов : по сильной теореме о совершенных графах граф является совершенным тогда и только тогда, когда ни одна из его дыр или антидырок не имеет нечетного числа вершин, которые больше трех. хордовый граф, особый тип совершенного графа, не имеет отверстий любого размера больше трех.
обхват графа - это длина его кратчайшего цикла; этот цикл обязательно бесхордовый. Клетки определяются как наименьшие регулярные графы с заданными комбинациями степени и обхвата.
A Периферийный цикл - это цикл в графе, обладающий тем свойством, что каждые два ребра, не входящие в цикл, могут быть соединены путем, внутренние вершины которого избегают цикла. В графе, который не образован добавлением одного ребра к циклу, периферийный цикл должен быть индуцированным циклом.
Термин цикл может также относиться к элементу пространства цикла графа. Есть много пространств циклов, по одному для каждого поля или кольца коэффициентов. Наиболее распространенным является пространство двоичных циклов (обычно называемое просто пространством циклов), которое состоит из наборов ребер, имеющих четную степень в каждой вершине; он формирует векторное пространство над двухэлементным полем . По теореме Веблена каждый элемент пространства циклов может быть сформирован как непересекающееся по ребрам объединение простых циклов. базис цикла графа - это набор простых циклов, который формирует базис пространства циклов.
Использование идей из алгебраической топологии, двоичное пространство цикла обобщается на векторные пространства или модули над другими кольцами, такими как целые числа, рациональные или действительные числа и т. д.
Существование цикла в ориентированных и неориентированных графах можно определить по тому, найдет ли поиск в глубину (DFS) ребро, которое указывает на предка текущей вершины (оно содержит назад edge ) Все задние кромки, которые пропускает DFS, являются частью циклов. В неориентированном графе ребро, ведущее к родительскому узлу, не должно считаться задним, но обнаружение любой другой уже посещенной вершины укажет на заднее ребро. В случае неориентированных графов требуется всего O (n) времени, чтобы найти цикл в n-вершинном графе, поскольку не более n - 1 ребер могут быть ребрами дерева.
Многие алгоритмы топологической сортировки также обнаруживают циклы, поскольку они являются препятствием для существования топологического порядка. Кроме того, если ориентированный граф был разделен на компоненты с сильной связью, циклы существуют только внутри компонентов, а не между ними, так как циклы сильно связаны.
Для ориентированных графов, основанных на распределенных сообщениях алгоритмы могут быть использованы. Эти алгоритмы основаны на идее, что сообщение, отправленное вершиной в цикле, вернется к самому себе. Алгоритмы обнаружения распределенного цикла полезны для обработки крупномасштабных графов с использованием системы обработки распределенных графов на компьютерном кластере (или суперкомпьютере).
Приложения обнаружения циклов включают использование графиков ожидания для обнаружения взаимоблокировок в параллельных системах.
В своей статье 1736 года о Семи мостах Кенигсберга, которая широко считается рождением теории графов, Леонард Эйлер доказал, что для конечного неориентированного графа должен быть замкнутый обхода, который посещает каждое ребро ровно один раз, необходимо и достаточно, чтобы оно было связным, за исключением изолированных вершин (то есть все ребра содержатся в одной компоненте) и имело четную степень в каждой вершине. Соответствующая характеристика существования замкнутого обхода, посещающего каждое ребро ровно один раз в ориентированном графе, состоит в том, что граф сильно связан и имеет равное количество входящих и исходящих ребер в каждой вершине. В любом случае результирующий обход известен как цикл Эйлера или тур Эйлера. Если конечный неориентированный граф имеет четную степень в каждой вершине, независимо от того, связан ли он, то можно найти набор простых циклов, которые вместе покрывают каждое ребро ровно один раз: это теорема Веблена. Когда связный граф не удовлетворяет условиям теоремы Эйлера, замкнутый обход минимальной длины, покрывающий каждое ребро хотя бы один раз, может быть найден за полиномиальное время путем решения задачи проверки маршрута.
Проблема поиска единственного простого цикла, который покрывает каждую вершину ровно один раз, а не покрывает ребра, намного сложнее. Такой цикл известен как гамильтонов цикл, и определение того, существует ли он, является NP-полным. Было опубликовано много исследований, касающихся классов графов, которые могут гарантированно содержать гамильтоновы циклы; одним из примеров является теорема Оре о том, что гамильтонов цикл всегда можно найти в графе, для которого каждая несмежная пара вершин имеет степени, суммирующие по крайней мере общее количество вершин в графе.
Гипотеза о двойном покрытии цикла утверждает, что для каждого графа без мостов существует мультимножество простых циклов, которое покрывает каждое ребро графа ровно дважды. Доказательство того, что это верно (или поиск контрпримера), остается открытой проблемой.
Некоторые важные классы графов могут быть определены или охарактеризованы своими циклами. К ним относятся:
