Ранг в округе

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

Этот граф имеет ранг цикла r = 2, поскольку его можно превратить в дерево, удалив два ребра, например, ребра 1–2 и 2–3, но удаление любого одного ребра оставляет в графе цикл.

В теории графов , разделе математики , ранг цепи , цикломатическое число , ранг цикла или нуль неориентированного графа — это минимальное количество ребер, которое необходимо удалить из графа, чтобы разорвать все его циклы , превратив его в дерево или лес . Он равен количеству независимых циклов в графе (размеру базиса цикла ). В отличие от соответствующей задачи набора дуг обратной связи для ориентированных графов , ранг цепи r легко вычисляется с помощью формулы

${\displaystyle r=m-n+c}$,

где m — количество ребер в данном графе, n — количество вершин , а c — количество связанных компонентов . ^[1] Также возможно построить набор ребер минимального размера, который эффективно разрывает все циклы, либо используя жадный алгоритм , либо дополняя остовной лес .

Ранг схемы можно объяснить в терминах алгебраической теории графов как размерность пространства циклов графа, в терминах теории матроидов как коранг графического матроида , а в терминах топологии как одно из чисел Бетти топологического пространства, полученного из графа. Он подсчитывает уши в ушной декомпозиции графа, формирует основу параметризованной сложности на почти деревьях и применялся в метриках программного обеспечения как часть определения цикломатической сложности фрагмента кода. Под названием цикломатического числа эта концепция была введена Густавом Кирхгофом . ^{[2] [3]}

Ранг матроида и построение минимального набора ребер обратной связи

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

В качестве альтернативы минимальный набор ребер, который разрывает все циклы, можно найти, построив остовной лес G и выбрав дополнительный набор ребер, которые не принадлежат остовному лесу.

Число независимых циклов

В алгебраической теории графов ранг схемы также является размерностью пространства циклов . Интуитивно это можно объяснить так, что ранг схемы подсчитывает количество независимых циклов в графе, где набор циклов независим, если невозможно сформировать один из циклов как симметричную разность некоторого подмножества других. ^[1] ${\displaystyle G}$

Это количество независимых циклов также можно объяснить с помощью теории гомологии , раздела топологии. Любой граф G можно рассматривать как пример одномерного симплициального комплекса , типа топологического пространства, образованного представлением каждого ребра графа отрезком прямой и склеиванием этих отрезков прямой вместе в их конечных точках. Цикломатическое число — это ранг первой ( целой ) группы гомологий этого комплекса, ^[5]

${\displaystyle r=\operatorname {rank} \left[H_{1}(G,\mathbb {Z} )\right].}$

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

Приложения

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

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

${\displaystyle {\frac {m-n+1}{2n-5}}.}$

Здесь числитель формулы - это ранг цепи данного графа, а знаменатель - это максимально возможный ранг цепи n -вершинного планарного графа. Коэффициент сетчатости варьируется от 0 для деревьев до 1 для максимальных планарных графов . ${\displaystyle m-n+1}$ ${\displaystyle 2n-5}$

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

Ранг схемы контролирует количество ушей в ушной декомпозиции графа, разбиении ребер графа на пути и циклы, которое полезно во многих алгоритмах графов. В частности, граф является 2-вершинно-связным тогда и только тогда, когда он имеет открытую ушную декомпозицию. Это последовательность подграфов, где первый подграф является простым циклом, все остальные подграфы являются простыми путями, каждый путь начинается и заканчивается на вершинах, которые принадлежат предыдущим подграфам, и каждая внутренняя вершина пути появляется впервые в этом пути. В любом двусвязном графе с рангом схемы каждое открытое ушное разложение имеет ровно уши. ^[8] ${\displaystyle r}$ ${\displaystyle r}$

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

Граф с цикломатическим числом также называется r -почти-деревом , потому что для того, чтобы превратить его в дерево или лес, из графа нужно удалить только r ребер. 1-почти-дерево — это почти-дерево : связанное почти-дерево — это псевдодерево , цикл с (возможно, тривиальным) деревом, укорененным в каждой вершине. ^[9] ${\displaystyle r}$

Несколько авторов изучали параметризованную сложность графовых алгоритмов на r -почти-деревьях, параметризованных с помощью . ^{[10] [11]} ${\displaystyle r}$

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

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

Также возможно вычислить более простой инвариант ориентированных графов, игнорируя направления ребер и вычисляя ранг цепи базового неориентированного графа. Этот принцип лежит в основе определения цикломатической сложности , программной метрики для оценки сложности фрагмента компьютерного кода.

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

В области химии и хемоинформатики ранг цепи молекулярного графа (число колец в наименьшем наборе наименьших колец ) иногда называют числом Фрережака . ^{[12] [13] [14]}

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

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

Связанные концепции

Другие числа, определяемые с точки зрения удаления элементов из графиков:

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

Ссылки

1. Берже, Клод (2001), «Цикломатическое число», Теория графов, Courier Dover Publications, стр. 27–30, ISBN 9780486419756.
2. Питер Роберт Котиуга (2010), Чествование математического наследия Рауля Ботта, Американское математическое общество, стр. 20, ISBN 978-0-8218-8381-5
3. Пер Хаге (1996), Островные сети: коммуникация, родство и структуры классификации в Океании, Cambridge University Press, стр. 48, ISBN 978-0-521-55232-5
4. Берж, Клод (1976), Графы и гиперграфы, Математическая библиотека Северной Голландии, т. 6, Elsevier, стр. 477, ISBN 9780720424539.
5. Серр, Жан-Пьер (2003), Деревья, Springer Monographs in Mathematics, Springer, стр. 23, ISBN 9783540442370.
6. Грегори Берколайко; Питер Кучмент (2013), Введение в квантовые графы, Американское математическое общество, стр. 4, ISBN 978-0-8218-9211-4
7. Буль, Дж.; Готре, Дж.; Соле, Р. В.; Кунц, П.; Вальверде, С.; Денебург, Дж. Л.; Тераулаз, Г. (2004), «Эффективность и надежность в муравьиных сетях галерей», The European Physical Journal B , 42 (1), Springer-Verlag: 123–129, doi :10.1140/epjb/e2004-00364-9.
8. Уитни, Х. (1932), «Неразделимые и планарные графы», Труды Американского математического общества , 34 (2): 339–362, doi : 10.2307/1989545 , JSTOR  1989545, PMC 1076008 , PMID  16587624 . См., в частности, теоремы 18 (связывающую разложение ушей с рангом цепи) и 19 (о существовании разложений ушей).
9. Бруальди, Ричард А. (2006), Комбинаторные матричные классы, Энциклопедия математики и ее приложений, т. 108, Кембридж: Cambridge University Press , стр. 349, ISBN 0-521-86565-4, ЗБЛ  1106.05001
10. Копперсмит, Дон ; Вишкин, Узи (1985), «Решение NP-трудных задач в «почти деревьях»: покрытие вершин», Дискретная прикладная математика , 10 (1): 27–45, doi : 10.1016/0166-218X(85)90057-5 , Zbl  0573.68017.
11. Фиала, Иржи; Клокс, Тон; Краточвил, Ян (2001), «Сложность λ-разметок с фиксированным параметром», Discrete Applied Mathematics , 113 (1): 59–72, doi : 10.1016/S0166-218X(00)00387-5 , Zbl  0982.05085.
12. Мэй, Джон В.; Стейнбек, Кристоф (2014), «Эффективное восприятие колец для набора для разработки химии», Журнал химинформатики , 6 (3): 3, doi : 10.1186/1758-2946-6-3 , PMC 3922685 , PMID  24479757 
13. Даунс, GM; Джиллет, VJ; Холлидей, JD; Линч, MF (1989), "Обзор алгоритмов восприятия колец для химических графов ", J. Chem. Inf. Comput. Sci. , 29 (3): 172–187, doi :10.1021/ci00063a007
14. Фрежак, Марсель (1939), «№ 108-Конденсация органической молекулы» [Конденсация органической молекулы], Bull. Соц. Хим. о. , 5 : 1008–1011
15. Демейн, Эрик Д .; Эппштейн, Дэвид ; Хестерберг, Адам; Джейн, Кшитидж; Любив, Анна ; Уэхара, Рюхей; Уно, Юши (2019), «Реконфигурация ненаправленных путей», в Фриггстад, Захари; Сак, Йорг-Рюдигер ; Салаватипур, Мохаммад Р. (ред.), Алгоритмы и структуры данных – 16-й международный симпозиум, WADS 2019, Эдмонтон, AB, Канада, 5-7 августа 2019 г., Труды , заметки лекций по информатике, т. 11646, Springer, стр. 353–365, arXiv : 1905.00518 , doi :10.1007/978-3-030-24766-9_26, ISBN 978-3-030-24765-2