Основа цикла

Симметричная разность двух циклов представляет собой эйлеров подграф.

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

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

В плоских графах множество ограниченных циклов вложения графа образует базис цикла. Базис минимального весового цикла планарного графа соответствует дереву Гомори – Ху двойственного графа .

Определения

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

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

Специальные велобазы

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

Индуцированные циклы

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

Фундаментальные циклы

Если $T$ является остовным деревом или остовным лесом данного графа $G$, и $e$ представляет собой ребро, не принадлежащее $T$, то фундаментальный цикл $C_{e}$ определяется $e$ – простой цикл, состоящий из $e$ вместе с дорогой в $T$ соединяя конечные точки $e$. Есть точно $m-n+c$ фундаментальные циклы, по одному на каждое ребро, не принадлежащее $T$. Каждый из них линейно независим от остальных циклов, поскольку включает в себя ребро $e$ этого нет ни в одном другом фундаментальном цикле. Таким образом, фундаментальные циклы составляют основу пространства циклов. Построенный таким образом базис цикла называется фундаментальным базисом цикла или сильно фундаментальным базисом цикла .

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

Слабо фундаментальные циклы

Базис цикла называется слабофундаментальным , если его циклы можно расположить в линейном порядке так, что каждый цикл включает хотя бы одно ребро, не входящее ни в один более ранний цикл. Фундаментальный базис цикла автоматически является слабо фундаментальным (при любом порядке ребер). Если каждый цикловый базис графа является слабо фундаментальным, то же самое верно для каждого минора графа. На основании этого свойства класс графов (и мультиграфов ), для которых каждый базис цикла является слабо фундаментальным, можно охарактеризовать пятью запрещенными минорами : графом квадратной пирамиды , мультиграфом, образованным удвоением всех ребер четырехвершинного цикла, два мультиграфа, образованные удвоением двух ребер тетраэдра , и мультиграф, образованный удвоением ребер треугольника.

Лицевые циклы

Если связный конечный планарный граф вложен в плоскость, каждая грань вложения ограничена циклом ребер. Одна грань обязательно неограничена (в нее входят точки, сколь угодно удаленные от вершин графа), а остальные грани ограничены. По формуле Эйлера для плоских графов существует ровно $m-n+1$ ограниченные лица.Симметричная разность любого набора гранных циклов является границей соответствующего набора граней, а разные наборы ограниченных граней имеют разные границы, поэтому невозможно представить один и тот же набор как симметричную разность гранных циклов более чем в одном способ; это означает, что множество гранных циклов линейно независимо. Как линейно независимый набор достаточного количества циклов, он обязательно образует базис цикла. Это всегда слабо фундаментальный базис цикла, и он фундаментален тогда и только тогда, когда вложение графа является внешнепланарным .

Для графов, правильно вложенных в другие поверхности, так что все грани вложения являются топологическими дисками, в общем случае неверно, что существует базис циклов, использующий только циклы граней. Циклы граней этих вложений порождают собственное подмножество всех эйлеровых подграфов. Группа гомологии $H_{2}(S,\mathbb {Z} _{2})$ заданной поверхности $S$ характеризует эйлеровы подграфы, которые нельзя представить как границу множества граней. Критерий планарности Мак Лейна использует эту идею для характеристики плоских графов с точки зрения базисов циклов: конечный неориентированный граф является планарным тогда и только тогда, когда он имеет разреженный цикловый базис или 2-базис . базис, в котором каждое ребро графа участвует не более чем в двух базисных циклах. В плоском графе базис циклов, образованный набором ограниченных граней, обязательно разрежен, и наоборот, разреженный базис циклов любого графа обязательно образует набор ограниченных граней плоского вложения его графа.

Интегральные основы

Пространство циклов графа можно интерпретировать с помощью теории гомологии как группу гомологии. $H_{1}(G,\mathbb {Z} _{2})$ симплициального комплекса с точкой для каждой вершины графа и отрезком для каждого ребра графа. Эту конструкцию можно обобщить на группу гомологий $H_{1}(G,R)$ над произвольным кольцом $R$. Важным частным случаем является кольцо целых чисел , для которого группа гомологий $H_{1}(G,\mathbb {Z} )$ — свободная абелева группа , подгруппа свободной абелевой группы, порожденная ребрами графа. Менее абстрактно, эту группу можно построить, присвоив произвольную ориентацию ребрам данного графа; тогда элементы $H_{1}(G,\mathbb {Z} )$ представляют собой маркировку ребер графа целыми числами со свойством, что в каждой вершине сумма меток входящих ребер равна сумме меток исходящих ребер. Групповая операция – это сложение этих векторов меток. Целочисленный базис цикла — это набор простых циклов, порождающий эту группу.

Минимальный вес

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

По стандартным свойствам базисов в векторных пространствах и матроидах базис цикла минимального веса не только минимизирует сумму весов своих циклов, но и любую другую монотонную комбинацию весов циклов. Например, именно базис цикла минимизирует вес самого длинного цикла.

Алгоритмы с полиномиальным временем

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

Хортон (1987) предложил первый алгоритм с полиномиальным временем для поиска базиса минимального веса в графах, для которых вес каждого ребра положителен. Его алгоритм использует подход «генерация и тестирование», но ограничивает генерируемые циклы небольшим набором циклов. $O(mn)$ циклы, называемые циклами Хортона . Цикл Хортона — это фундаментальный цикл дерева кратчайших путей данного графа. Существует не более n различных деревьев кратчайших путей (по одному на каждую начальную вершину), и каждое из них имеет менее m фундаментальных циклов, что дает ограничение на общее количество циклов Хортона. Как показал Хортон, каждый цикл в базисе цикла минимального веса является циклом Хортона. Использование алгоритма Дейкстры для поиска каждого дерева кратчайших путей, а затем использование метода исключения Гаусса для выполнения этапов тестирования жадного базисного алгоритма приводит к алгоритму полиномиального времени для базиса цикла минимального веса.Последующие исследователи разработали улучшенные алгоритмы решения этой проблемы. уменьшение временной сложности в наихудшем случае для нахождения базиса минимального весового цикла в графе с $m$ края и $n$ вершины в $O(m^{2}n/\log n)$.

NP-твердость

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

В планарных графах

Базис цикла минимального веса для плоского графа не обязательно совпадает с базисом, образованным его ограниченными гранями: он может включать циклы, которые не являются гранями, а некоторые грани могут не включаться как циклы в базис цикла минимального веса. Однако существует базис цикла с минимальным весом, в котором никакие два цикла не пересекаются: для каждых двух циклов в базисе либо циклы заключают в себе непересекающиеся подмножества ограниченных граней, либо один из двух циклов заключает в себе другой. Этот набор циклов соответствует в двойственном графе данного планарного графа набору разрезов , которые образуют дерево Гомори – Ху двойственного графа, базис минимального веса его пространства разрезов . На основе этой двойственности можно построить неявное представление базиса цикла с минимальным весом в плоском графе во времени. $O(n\log ^{3}n)$.

Приложения

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

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

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

В биоинформатике основания циклов использовались для определения информации о гаплотипах на основе данных последовательности генома. использовались для анализа третичной структуры РНК Основания цикла также .

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

В хемоинформатике базис минимального цикла молекулярного графа называется наименьшим набором наименьших колец .