Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Для связанного понятия, называемого рангом цикла в ориентированных графах, см. Ранг цикла .
Этот граф имеет ранг схемы r = 2, потому что его можно превратить в дерево, удалив два ребра, например ребра 1–2 и 2–3, но удаление любого одного ребра оставляет цикл в графе.

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

,

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

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

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

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

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

Количество независимых циклов [ править ]

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

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

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

Приложения [ править ]

Коэффициент сетчатости [ править ]

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

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

Разложение уха [ править ]

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

Почти деревья [ править ]

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

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

Обобщения на ориентированные графы [ править ]

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

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

Вычислительная химия [ править ]

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

Понятия, связанные с данным [ править ]

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

Ссылки [ править ]

  1. ^ a b Берже, Клод (2001), «Цикломатическое число», Теория графов , Courier Dover Publications, стр. 27–30, ISBN 9780486419756.
  2. ^ Питер Роберт Котюга (2010). Празднование математического наследия Рауля Ботта . American Mathematical Soc. п. 20. ISBN 978-0-8218-8381-5.
  3. ^ Per Hage (1996). Островные сети: коммуникации, родство и классификационные структуры в Океании . Издательство Кембриджского университета. п. 48. ISBN 978-0-521-55232-5.
  4. Перейти ↑ Berge, Claude (1976), Graphs and Hypergraphs , North-Holland Mathematical Library, 6 , Elsevier, p. 477, ISBN 9780720424539.
  5. ^ Серр, Жан-Пьер (2003), Деревья , Монографии Спрингера по математике, Спрингер, стр. 23.
  6. ^ Григорий Берколайко; Питер Кучмент (2013). Введение в квантовые графы . American Mathematical Soc. п. 4. ISBN 978-0-8218-9211-4.
  7. ^ Buhl, J .; Gautrais, J .; Подошва, RV; Kuntz, P .; Valverde, S .; Deneubourg, JL; Тераулаз, Г. (2004), «Эффективность и надежность в муравьиных сетях галерей», The European Physical Journal B , Springer-Verlag, 42 (1): 123–129, doi : 10.1140 / epjb / e2004-00364-9.
  8. ^ Уитни, H. (1932), "Несепарабельные и плоские графы", Труды Американского математического общества , 34 : 339-362, DOI : 10,2307 / 1989545. См., В частности, теоремы 18 (связывающие разложение уха с рангом схемы) и 19 (о существовании разложения уха).
  9. ^ Brualdi, Ричард А. (2006), Комбинаторные матричные классы , Энциклопедия математики и ее приложений, 108 , Кембридж: Cambridge University Press , стр. 349 , ISBN 0-521-86565-4, Zbl  1106,05001
  10. ^ Медник, Дон ; Вишкин, Узи (1985), «Решение NP-сложных задач в« почти деревьях »: вершинное покрытие», Дискретная прикладная математика , 10 (1): 27–45, DOI : 10.1016 / 0166-218X (85) 90057-5 , Zbl 0573.68017 .
  11. ^ Фиала, Иржи; Клокс, Тон; Кратохвил, Ян (2001), "Сложность λ-разметки с фиксированными параметрами", Дискретная прикладная математика , 113 (1): 59–72, DOI : 10.1016 / S0166-218X (00) 00387-5 , Zbl 0982.05085 .
  12. ^ Мэй, Джон У .; Стейнбек, Кристоф (2014). «Эффективное восприятие кольца для набора для разработки химии» . Журнал химинформатики . 6 (3). DOI : 10.1186 / 1758-2946-6-3 . PMC 3922685 . PMID 24479757 .  
  13. ^ Даунс, GM; Gillet, VJ; Холлидей, JD; Линч, MF (1989). «Обзор алгоритмов восприятия кольца для химических графов ». J. Chem. Инф. Comput. Sci. 29 (3): 172–187. DOI : 10.1021 / ci00063a007 .
  14. ^ Frèrejacque, Марсель (1939). "№ 108-Конденсация органической молекулы" [Конденсация органической молекулы]. Бык. Soc. Чим. Пт. 5 : 1008–1011.