Цикл (теория графов)


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

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

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

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

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