Ранг цепи - Circuit rank - Wikipedia

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

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

,

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

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

Связанные понятия

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

Рекомендации

  1. ^ а б Берже, Клод (2001), «Цикломатическое число», Теория графов, Courier Dover Publications, стр. 27–30, ISBN  9780486419756.
  2. ^ Питер Роберт Котюга (2010). Праздник математического наследия Рауля Ботта. American Mathematical Soc. п. 20. ISBN  978-0-8218-8381-5.
  3. ^ Пер Хаге (1996). Островные сети: коммуникационные, родственные и классификационные структуры в Океании. Издательство Кембриджского университета. п. 48. ISBN  978-0-521-55232-5.
  4. ^ Берже, Клод (1976), Графы и гиперграфы, Математическая библиотека Северной Голландии, 6, Elsevier, стр. 477, г. ISBN  9780720424539.
  5. ^ Серр, Жан-Пьер (2003), Деревья, Монографии Спрингера по математике, Springer, p. 23.
  6. ^ Григорий Берколайко; Питер Кучмент (2013). Введение в квантовые графы. American Mathematical Soc. п. 4. ISBN  978-0-8218-9211-4.
  7. ^ Buhl, J .; Gautrais, J .; Sole, R.V .; Kuntz, P .; Valverde, S .; Deneubourg, J.L .; Тераулаз, Г. (2004), "Эффективность и надежность в муравьиных сетях галерей", Европейский физический журнал B, Springer-Verlag, 42 (1): 123–129, Дои:10.1140 / epjb / e2004-00364-9.
  8. ^ Уитни, Х. (1932), «Неразделимые и плоские графы», Труды Американского математического общества, 34: 339–362, Дои:10.2307/1989545. См., В частности, теоремы 18 (связывающие разложение уха с рангом схемы) и 19 (о существовании разложения уха).
  9. ^ Бруальди, Ричард А. (2006), Комбинаторные матричные классы, Энциклопедия математики и ее приложений, 108, Кембридж: Издательство Кембриджского университета, п.349, ISBN  0-521-86565-4, Zbl  1106.05001
  10. ^ Медник, Дон; Вишкин, Узи (1985), "Решение NP-трудных задач в" почти деревьях ": вершинное покрытие", Дискретная прикладная математика, 10 (1): 27–45, Дои:10.1016 / 0166-218X (85) 90057-5, Zbl  0573.68017.
  11. ^ Фиала, Иржи; Клокс, Тон; Кратохвил, Ян (2001), "Сложность λ-разметки с фиксированными параметрами", Дискретная прикладная математика, 113 (1): 59–72, Дои:10.1016 / S0166-218X (00) 00387-5, Zbl  0982.05085.
  12. ^ Мэй, Джон В .; Стейнбек, Кристоф (2014). «Эффективное восприятие кольца для набора для разработки химии». Журнал химинформатики. 6 (3). Дои:10.1186/1758-2946-6-3. ЧВК  3922685. PMID  24479757.
  13. ^ Даунс, G.M .; Gillet, V.J .; Холлидей, J.D .; Линч, М.Ф. (1989). "Обзор Алгоритмы восприятия кольца для химических графов". J. Chem. Инф. Comput. Sci. 29 (3): 172–187. Дои:10.1021 / ci00063a007.
  14. ^ Фрережак, Марсель (1939). "№ 108-Конденсация органической молекулы" [Конденсация органической молекулы]. Бык. Soc. Чим. Пт. 5: 1008–1011.