Цикломатичне число графа вікі
Цей граф має контурний ранг r = 2. оскільки його можна перетворити в дерево видаленням двох ребер, наприклад, ребер 1-2 і 2-3, але видалення лише одного ребра залишає цикл в графі.
В теорії графів контурний ранг [1] неориентированного графа - це мінімальне число ребер, видалення яких руйнує все цикли графа, перетворюючи його в дерево або ліс. Контурний ранг можна розуміти також як число незалежних циклів в графі. На відміну від відповідного завдання знаходження розрізає цикли набору дуг [en] для орієнтованих графів. контурний ранг r легко обчислюється за формулою
де m - число ребер заданого графа, n - число вершин. а c - число компонент зв'язності [2]. Можна також ефективно побудувати безліч ребер мінімального розміру, розбивають цикли, використовуючи або жадібний алгоритм. або доповнення остовного дерева.
Контурний ранг відомий також як цикломатичне число графа. Його можна пояснити в термінах алгебри теорії графів як розмірність циклічне простір [en] графа, в термінах матроідов з використанням поняття коранга графових матроідов [en] [3] і в термінах топології як одне з чисел Бетті топологічного простору, похідного від графа. Контурний ранг підраховує число вух в вушної декомпозиції графа, що дає базис для поняття параметризрвані складності [en] на майже деревах і застосовується в метриках програмного забезпечення як частину визначення цикломатическая складності фрагмента коду. Під назвою цикломатическая складність поняття було введено Густавом Кірхгофа [4] [5].
Ранг матроід і побудова мінімального розрізає цикли безлічі [| ]
Контурний ранг графа G можна описати за допомогою теорії матроідов як коранг графового матроід [en] для G [6]. Якщо врахувати властивість жадібності матроідов, це означає, що можна знайти мінімальний набір ребер, що руйнує все цикли, використовуючи жадібний алгоритм. вибирає на кожному кроці ребро, що належить щонайменше одному циклу залишився графа.
З іншого боку, мінімальний набір множин, що руйнує все цикли, можна знайти шляхом побудови остовного лісу графа G і вибору доповнює безлічі ребер, які не належать остовному лісі.
Число незалежних циклів [| ]
В алгебраїчній теорії графів. контурний ранг - це розмірність циклічного простору [en] графа G. Інтуїтивно можна пояснити контурний ранг як підраховує число незалежних циклів графа, де набір циклів вважається незалежний, якщо неможливо утворити один цикл як симетричну різницю деякого поднабора інших циклів [2].
Цей підрахунок незалежних циклів може бути пояснений за допомогою теорії гомологий. гілки топології. Будь-граф G можна розглядати як приклад 1-мірного симпліціального комплексу. одного з видів топологічного простору. утвореного поданням кожного ребра графа відрізком і склеюванням цих відрізків на кінцях. Цикломатичне число є рангом першої (цілої) групи гомологий цього комплексу [7],
У зв'язку з такою топологічної зв'язком цикломатичне число графа G називається також першим числом Бетті графа G [8]. У більш загальному випадку перше число Бетті будь-якого топологічного простору підраховує число незалежних циклів в просторі.
Додатки [| ]
Коефіцієнт сітчасті [| ]
Варіант контурного рангу планарного графа. нормалізований шляхом ділення на максимально можливий контурний ранг будь-якого планарного графа з тим же набором вершин, називається коефіцієнтом сітчасті. Для зв'язкових планарних графів з m ребрами і n вершинами коефіцієнт сітчасті можна обчислити за формулою [9]
У цій формулі чисельник m # X2212; n + 1 у формулі є контурним рангом даного графа, а знаменник 2 n # X2212; 5 є найбільшим можливим контурним рангом планарного графа з n вершинами. Коефіцієнт сітчасті лежить між 0 для дерев і 1 для максимальних планарних графів [en].
Вушна декомпозиція [| ]
Контурний ранг відображає число вух в вушної декомпозиції графа, розкладанні ребер графа на шляху і цикли, що часто виявляється корисним в алгоритмах на графах. Зокрема, граф вершинно 2-зв'язний тоді і тільки тоді, коли він має відкриту вушну декомпозицію, послідовність подграфов, в якому перший підграф є простим циклом, а що залишилися підграфи є простими шляхами і кожен шлях починається і закінчується в вершинах, що належать попереднім подграфа, і кожна внутрішня вершина шляху з'являється перший раз в цьому шляху. У будь-якому двусвязного графі з контурним рангом r будь-яка відкрита вушна декомпозиція має в точності r вух [10].
Майже дерева [| ]
Граф з цикломатическая числом r називається також майже r -дерева. оскільки потрібно видалити з графа лише r ребер, щоб перетворити його в дерево або ліс. Майже 1-дерево є майже деревом - чіткий майже дерево є псевдолесом. циклом з (можливо тривіальними) деревами з корінням в кожній вершині [11].
Узагальнення для орієнтованих графів [| ]
Циклічний ранг [en] - це інваріант орієнтованих графів. вимірює рівень вкладеності циклів в графі. Цей інваріант має більш складне визначення, ніж цикломатическая ранг (тісно пов'язаний з визначенням глибини дерева для неорієнтованих графів) і обчислення його істотно складніше. Інше завдання для орієнтованих графів, пов'язана з цикломатическая рангом - визначення мінімального розрізає цикли набору дуг [en]. тобто мінімального набору дуг, видалення яких руйнує все орієнтовані цикли. Обидва завдання, обчислення циклічного рангу і визначення мінімального рарезающіего цикли набору дуг, є NP-важкими.
Також можна обчислити більш простий інваріант орієнтованих графів, якщо ігнорувати напрямки ребер і обчислити циклічний ранг неориентированного графа. Цей принцип утворює базис для визначення цикломатическая складності. міри складності комп'ютерної програми для оцінки складності фрагмента комп'ютерного коду.
Пов'язані поняття [| ]
Інші числа, що визначаються в термінах видалення ребер з неорієнтованого графа, включають реберної зв'язності. мінімальне число ребер, видалення яких призводить до втрати зв'язності, і число запобігання паросочетание [en]. мінімальне число ребер, видалення яких призводить до втрати існування досконалого паросполучення.