Основа цикла

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

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

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

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

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

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

Каждый граф имеет базис цикла, в котором каждый цикл является индуцированным циклом . В графе с тремя вершинами всегда существует базис, состоящий из периферийных циклов , циклов, удаление которых не разделяет оставшийся граф. ^{[4] [5]} В любом графе, кроме графа, образованного добавлением одного ребра к циклу, периферийный цикл должен быть индуцированным циклом.

Если — остовное дерево или остовный лес данного графа , и — ребро, которое не принадлежит , то фундаментальный цикл, определяемый как — это простой цикл, состоящий из вместе с путем, соединяющим конечные точки . Существует ровно фундаментальных циклов, по одному для каждого ребра, которое не принадлежит . Каждый из них линейно независим от остальных циклов, поскольку он включает ребро , которое не присутствует ни в каком другом фундаментальном цикле. Следовательно, фундаментальные циклы образуют базис для пространства циклов. ^{[1] [2]} Базис циклов, построенный таким образом, называется фундаментальным базисом циклов или строго фундаментальным базисом циклов . ^[3]${\displaystyle Т}$${\displaystyle G}$${\displaystyle е}$${\displaystyle Т}$${\displaystyle C_{e}}$${\displaystyle е}$${\displaystyle е}$${\displaystyle Т}$${\displaystyle е}$${\displaystyle m-n+c}$${\displaystyle Т}$${\displaystyle е}$

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

Базис цикла называется слабо фундаментальным, если его циклы можно поместить в линейный порядок таким образом, что каждый цикл включает по крайней мере одно ребро, которое не включено ни в один более ранний цикл. Базис фундаментального цикла автоматически является слабо фундаментальным (для любого порядка ребер). ^{[3] [7]} Если каждый базис цикла графа является слабо фундаментальным, то же самое верно для каждого минора графа. Основываясь на этом свойстве, класс графов (и мультиграфов ), для которых каждый базис цикла является слабо фундаментальным, можно охарактеризовать пятью запрещенными минорами : граф квадратной пирамиды , мультиграф, образованный удвоением всех ребер цикла с четырьмя вершинами, два мультиграфа, образованные удвоением двух ребер тетраэдра , и мультиграф, образованный утроением ребер треугольника. ^[8]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В хемоинформатике минимальный циклический базис молекулярного графа называется наименьшим набором наименьших колец . ^{[29] [30] [31]}