Ранг цепи

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

r=m-n+c

,

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

Разложение ушей

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

^ Jump up to: ^а ^б Берже, Клод (2001), «Цикломатическое число», Теория графов , Courier Dover Publications, стр. 27–30, ISBN 9780486419756 .
^ Питер Роберт Котюга (2010), Празднование математического наследия Рауля Ботта , Американское математическое общество, стр. 20, ISBN 978-0-8218-8381-5
^ Пер Хаге (1996), Сети островов: структуры коммуникации, родства и классификации в Океании , издательство Кембриджского университета, стр. 48, ISBN 978-0-521-55232-5
^ Берге, Клод (1976), Графики и гиперграфы , Математическая библиотека Северной Голландии, том. 6, Эльзевир, с. 477, ISBN 9780720424539 .
^ Серр, Жан-Пьер (2003), Деревья , Монографии Спрингера по математике, Спрингер, стр. 23, ISBN 9783540442370 .
^ Григорий Берколайко; Питер Кучмент (2013), Введение в квантовые графы , Американское математическое общество, стр. 4, ISBN 978-0-8218-9211-4
^ Буль, Дж.; Готре, Ж.; Соле, Р.В.; Кунц, П.; Вальверде, С.; Денебур, JL; Тераулаз, Г. (2004), «Эффективность и надежность муравьиных сетей галерей», The European Physical Journal B , 42 (1), Springer-Verlag: 123–129, doi : 10.1140/epjb/e2004-00364-9 .
^ Уитни, Х. (1932), «Неразделимые и плоские графы», Transactions of the American Mathematical Society , 34 (2): 339–362, doi : 10.2307/1989545 , JSTOR 1989545 , PMC 1076008 , PMID 16587624 . См., в частности, теоремы 18 (о связи разложения ушей с рангом схемы) и 19 (о существовании разложений ушей).
^ Бруальди, Ричард А. (2006), Комбинаторные матричные классы , Энциклопедия математики и ее приложений, том. 108, Кембридж: Издательство Кембриджского университета , стр. 108. 349 , ISBN 0-521-86565-4 , Збл 1106.05001
^ Копперсмит, Дон ; Вишкин, Узи (1985), «Решение NP-трудных задач в« почти деревьях »: вершинное покрытие», Дискретная прикладная математика , 10 (1): 27–45, doi : 10.1016/0166-218X(85)90057-5 , Збл 0573.68017 .
^ Фиала, Иржи; Клокс, Тон; Краточвил, Ян (2001), «Сложность λ-маркировок с фиксированным параметром», Discrete Applied Mathematics , 113 (1): 59–72, doi : 10.1016/S0166-218X(00)00387-5 , Zbl 0982.05085 .
^ Мэй, Джон В.; Стейнбек, Кристоф (2014), «Эффективное восприятие кольца для набора для разработки химии», Journal of Cheminformatics , 6 (3): 3, doi : 10.1186/1758-2946-6-3 , PMC 3922685 , PMID 24479757
^ Даунс, генеральный менеджер; Жилле, виджей; Холлидей, Джей Ди; Линч, М.Ф. (1989), «Обзор алгоритмов восприятия колец для химических графов », J. Chem. Инф. Вычислить. наук. , 29 (3): 172–187, doi : 10.1021/ci00063a007
^ Фрежак, Марсель (1939), «№ 108-Конденсация органической молекулы», Bull. Бревно. Сказать. о. , 5 : 1008–1011
^ Демейн, Эрик Д .; Эппштейн, Дэвид ; Хестерберг, Адам; Джайн, Кшитидж; Любив, Анна ; Уэхара, Рюхей; Уно, Юши (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

[berge-1] Jump up to: ^а ^б Берже, Клод (2001), «Цикломатическое число», Теория графов , Courier Dover Publications, стр. 27–30, ISBN 9780486419756 .

[Kotiuga2010-2] Питер Роберт Котюга (2010), Празднование математического наследия Рауля Ботта , Американское математическое общество, стр. 20, ISBN 978-0-8218-8381-5

[Hage1996-3] Пер Хаге (1996), Сети островов: структуры коммуникации, родства и классификации в Океании , издательство Кембриджского университета, стр. 48, ISBN 978-0-521-55232-5

[4] Берге, Клод (1976), Графики и гиперграфы , Математическая библиотека Северной Голландии, том. 6, Эльзевир, с. 477, ISBN 9780720424539 .

[5] Серр, Жан-Пьер (2003), Деревья , Монографии Спрингера по математике, Спрингер, стр. 23, ISBN 9783540442370 .

[BerkolaikoKuchment2013-6] Григорий Берколайко; Питер Кучмент (2013), Введение в квантовые графы , Американское математическое общество, стр. 4, ISBN 978-0-8218-9211-4

[7] Буль, Дж.; Готре, Ж.; Соле, Р.В.; Кунц, П.; Вальверде, С.; Денебур, JL; Тераулаз, Г. (2004), «Эффективность и надежность муравьиных сетей галерей», The European Physical Journal B , 42 (1), Springer-Verlag: 123–129, doi : 10.1140/epjb/e2004-00364-9 .

[8] Уитни, Х. (1932), «Неразделимые и плоские графы», Transactions of the American Mathematical Society , 34 (2): 339–362, doi : 10.2307/1989545 , JSTOR 1989545 , PMC 1076008 , PMID 16587624 . См., в частности, теоремы 18 (о связи разложения ушей с рангом схемы) и 19 (о существовании разложений ушей).

[CMC349-9] Бруальди, Ричард А. (2006), Комбинаторные матричные классы , Энциклопедия математики и ее приложений, том. 108, Кембридж: Издательство Кембриджского университета , стр. 108. 349 , ISBN 0-521-86565-4 , Збл 1106.05001

[10] Копперсмит, Дон ; Вишкин, Узи (1985), «Решение NP-трудных задач в« почти деревьях »: вершинное покрытие», Дискретная прикладная математика , 10 (1): 27–45, doi : 10.1016/0166-218X(85)90057-5 , Збл 0573.68017 .

[11] Фиала, Иржи; Клокс, Тон; Краточвил, Ян (2001), «Сложность λ-маркировок с фиксированным параметром», Discrete Applied Mathematics , 113 (1): 59–72, doi : 10.1016/S0166-218X(00)00387-5 , Zbl 0982.05085 .

[12] Мэй, Джон В.; Стейнбек, Кристоф (2014), «Эффективное восприятие кольца для набора для разработки химии», Journal of Cheminformatics , 6 (3): 3, doi : 10.1186/1758-2946-6-3 , PMC 3922685 , PMID 24479757

[13] Даунс, генеральный менеджер; Жилле, виджей; Холлидей, Джей Ди; Линч, М.Ф. (1989), «Обзор алгоритмов восприятия колец для химических графов », J. Chem. Инф. Вычислить. наук. , 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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]