WikiSort.ru - Не сортированное

Порождённые циклы

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

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

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

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

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

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

Циклы граней

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

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

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

Целые базисы

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

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

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

Хортон (Horton 1987) предложил первый алгоритм полиномиального времени для поиска базиса с минимальным весом в графах, у которых все веса больше нуля. Его алгоритм использует тот же подход «получить и проверить», но число просматриваемых циклов ограничивается небольшим множеством размера ${\displaystyle O(mn)}$ — эти циклы называются циклами Хортона. Цикл Хортона — это фундаментальный цикл дерева кратчайших путей^[en] заданного графа. Существует n различных деревьев кратчайших путей (по одному для каждой корневой вершины) и каждое дерево имеет не больше чем m фундаментальных циклов, что и даёт общее число циклов Хортона. Как показал Хортон, любой цикл в базисе циклов минимального веса является циклом Хортона^[13].

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

Последующие исследования дали улучшенные алгоритмы для этой задачи^{[14][15][16][17]}, уменьшающие временную сложность худшего случая^[en] для нахождения базиса циклов минимального веса до ${\displaystyle O(m^{2}n/\log n)}$ , где ${\displaystyle m}$  — число рёбер графа, а ${\displaystyle n}$  — число вершин^[18].

NP-трудность

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

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

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