где m — число рёбер заданного графа, n — число вершин, а c — число компонент связности[2]. Можно также эффективно построить множество рёбер минимального размера, разбивающих циклы, используя либо жадный алгоритм, либо дополнение остовного дерева.
Ранг матроида и построение минимального разрезающего циклы множества
Контурный ранг графа G можно описать с помощью теории матроидов как корангграфового матроида[англ.] для G[6]. Если учесть свойство жадности матроидов, это означает, что можно найти минимальный набор рёбер, разрушающий все циклы, используя жадный алгоритм, выбирающий на каждом шаге ребро, принадлежащее по меньшей мере одному циклу оставшегося графа.
С другой стороны, минимальный набор множеств, разрушающий все циклы, можно найти путём построения остовного леса графа G и выбора дополняющего множества рёбер, не принадлежащих остовному лесу.
Число независимых циклов
В алгебраической теории графов, контурный ранг — это размерность пространства циклов графа . Интуитивно можно объяснить контурный ранг как подсчитывающий число независимых циклов графа, где набор циклов считается независимым, если невозможно образовать один цикл как симметрическую разность некоторого поднабора других циклов[2].
В связи с такой топологической связью цикломатическое число графа G называется также первым числом Бетти графа G[8]. В более общем случае первое число Бетти любого топологического пространства подсчитывает число независимых циклов в пространстве.
Вариант контурного ранга планарного графа, нормализованный путём деления на максимально возможный контурный ранг любого планарного графа с тем же набором вершин, называется коэффициентом сетчатости. Для связных планарных графов с m рёбрами и n вершинами коэффициент сетчатости можно вычислить по формуле[9]
В этой формуле числитель в формуле является контурным рангом данного графа, а знаменатель является наибольшим возможным контурным рангом планарного графа с n вершинами. Коэффициент сетчатости лежит между 0 для деревьев и 1 для максимальных планарных графов[англ.].
Ушная декомпозиция
Контурный ранг отражает число ушей в ушной декомпозиции графа, разложении рёбер графа на пути и циклы, что часто оказывается полезным в алгоритмах на графах. В частности, граф вершинно 2-связен тогда и только тогда, когда он имеет открытую ушную декомпозицию, последовательность подграфов, в котором первый подграф является простым циклом, а оставшиеся подграфы являются простыми путями и каждый путь начинается и кончается в вершинах, принадлежащих предыдущим подграфам, и каждая внутренняя вершина пути появляется первый раз в этом пути. В любом двусвязном графе с контурным рангом любая открытая ушная декомпозиция имеет в точности ушей[10].
Почти деревья
Граф с цикломатическим числом называется также почти r-деревом, поскольку нужно удалить из графа лишь r рёбер, чтобы превратить его в дерево или лес. Почти 1-дерево является почти деревом — связное почти дерево является псевдолесом, циклом с (возможно тривиальными) деревьями с корнями в каждой вершине[11].
Циклический ранг — это инвариант ориентированных графов, измеряющий уровень вложенности циклов в графе. Этот инвариант имеет более сложное определение, чем цикломатический ранг (тесно связанный с определением глубины дерева для неориентированных графов) и вычисление его существенно сложнее. Другая задача для ориентированных графов, связанная с цикломатическим рангом — определение минимального разрезающего циклы набора дуг, то есть минимального набора дуг, удаление которых разрушает все ориентированные циклы. Обе задачи, вычисление циклического ранга и определение минимального разрезающего циклы набора дуг, являются NP-трудными.
Также можно вычислить более простой инвариант ориентированных графов, если игнорировать направления рёбер и вычислить циклический ранг неориентированного графа. Этот принцип образует базис для определения цикломатической сложности, меры сложности компьютерной программы для оценки сложности фрагмента компьютерного кода.
↑В русскоязычной литературе и cycle rank, и circuit rank часто переводятся одинаково — циклический ранг. В англоязычной литературе первый термин относится к ориентированным графам, второй — к неориентированным. В данной статье для ориентированных графов используется термин «циклический ранг», для неориентированных графов — «контурный ранг»
↑В русскоязычной литературе употребляется также термин графический матроид, что является калькой английского graphic matroid и не совсем соответствует сущности понятия.
Claude Berge. The Theory of Graphs. — Courier Dover Publications, 2001. — ISBN 9780486419756.
Claude Berge. Graphs and Hypergraphs. — Elsevier, 1976. — Т. 6. — (North-Holland Mathematical Library). — ISBN 9780720424539.
К. Берж. Теория графов и её применение.
J. Buhl, J. Gautrais, R.V. Sole, P. Kuntz, S. Valverde, J.L. Deneubourg, G. Theraulaz. Efficiency and robustness in ant networks of galleries // The European Physical Journal B-Condensed Matter and Complex Systems. — Springer-Verlag, 2004. — Т. 42, вып. 1. — С. 123–129. — doi:10.1140/epjb/e2004-00364-9.
Richard A. Brualdi. Combinatorial matrix classes. — Cambridge: Cambridge University Press, 2006. — Т. 108. — С. 349. — (Encyclopedia of Mathematics and Its Applications). — ISBN 0-521-86565-4.
Don Coppersmith, Uzi Vishkin. Solving NP-hard problems in 'almost trees': Vertex cover // Discrete Applied Mathematics. — 1985. — Т. 10, вып. 1. — С. 27–45. — doi:10.1016/0166-218X(85)90057-5.
Jiří Fiala, Ton Kloks, Jan Kratochvíl. Fixed-parameter complexity of λ-labelings // Discrete Applied Mathematics. — 2001. — Т. 113, вып. 1. — С. 59–72. — doi:10.1016/S0166-218X(00)00387-5.
Peter Robert Kotiuga. A Celebration of the Mathematical Legacy of Raoul Bott. — American Mathematical Soc., 2010. — С. 20. — ISBN 978-0-8218-8381-5.
Per Hage. Island Networks: Communication, Kinship, and Classification Structures in Oceania. — Cambridge University Press, 1996. — С. 48. — ISBN 978-0-521-55232-5.
Jean-Pierre Serre. Trees. — Springer, 2003. — С. 23. — (Springer Monographs in Mathematics).
Gregory Berkolaiko, Peter Kuchment. Introduction to Quantum Graphs. — American Mathematical Soc., 2013. — С. 4. — ISBN 978-0-8218-9211-4.