Рейтинг схемы

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

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

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

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

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

Содержание

• 1 Ранг матроида и построение минимального набора ребер обратной связи
• 2 Количество независимых циклов
• 3 Приложения
  • 3.1 Коэффициент сетчатости
  • 3.2 Разложение уха
  • 3.3 Почти-деревья
  • 3.4 Обобщения на ориентированные графы
  • 3.5 Вычислительная химия
• 4 Понятия, связанные с данным
• 5 Ссылки

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

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

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

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

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

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

$r\; =\; ранг\; \; [H\; 1\; (G,\; Z)].\; \{\backslash \; displaystyle\; r\; =\; \backslash \; operatorname\; \{rank\}\; \backslash \; left\; [H\_\; \{1\}\; (G,\; \backslash \; mathbb\; \{Z\})\; \backslash \; right].\}$

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

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

В областях химии и химинформатики ранг схемы молекулярного графа (число колец в наименьшем наборе наименьших колец ) иногда упоминается как число Фрережака .

Понятия, связанные с данным

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

Ссылки