Введение

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

В теории графов, являющейся частью математики, циклический ранг, цикломатическое число, ранг циклов или нуль-размерность неориентированного графа – это минимальное количество ребер, которые необходимо удалить из графа, чтобы разрушить все его циклы, превратив его в дерево или лес. Он равен числу независимых циклов в графе (размеру базиса циклов). В отличие от соответствующей задачи об обратном множестве дуг для ориентированных графов, циклический ранг r легко вычисляется по формуле , где m – количество ребер в данном графе, n – количество вершин, а c – количество связных компонент. Также возможно эффективно построить минимальное множество ребер, разрушающих все циклы, используя жадный алгоритм или дополняя остовное дерево. Циклический ранг можно объяснить с точки зрения алгебраической теории графов как размерность циклического пространства графа, с точки зрения теории матроидов как коранг графического матроида, и с точки зрения топологии как одно из чисел Бетти топологического пространства, полученного из графа. Он подсчитывает «уши» в ушном разложении графа, является основой параметризованной сложности для почти деревьев и применяется в метриках программного обеспечения как часть определения цикломатической сложности фрагмента кода. Под названием цикломатического числа эта концепция была введена Густавом Кирхгофом.

Матроидный ранг и конструкция минимального набора краев обратной связи

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

Количество независимых циклов

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

Коэффициент сетчатости

Вариант ранга циклов для планарных графов, нормализованный делением на максимально возможный ранг циклов любого планарного графа с тем же набором вершин, называется коэффициентом сетчатости. Для связного планарного графа с m ребрами и n вершинами коэффициент сетчатости может быть вычислен по формуле. Здесь числитель формулы – ранг циклов данного графа, а знаменатель – наибольший возможный ранг циклов планарного графа с n вершинами. Коэффициент сетчатости изменяется от 0 для деревьев до 1 для максимальных планарных графов.

Разложение уха

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

Почти деревья

Граф с цикломатическим числом r также называют r-почти деревом, поскольку для превращения его в дерево или лес необходимо удалить всего r ребер. 1-почти дерево – это почти дерево: связное почти дерево – это псевдодерево, представляющее собой цикл с (возможно, тривиальным) деревом, присоединенным к каждой вершине. Ряд авторов изучали параметризованную сложность графовых алгоритмов на r-почти деревьях, параметризованную r.

Обобщения для направленных графиков

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

Вычислительная химия

В химии и химиоинформатике ранг цикла молекулярного графа (количество колец в минимальном наборе наименьших циклов) иногда называют числом Фрережака.

Параметризированная сложность

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