Базис циклов

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

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

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

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

Определения

Остовное дерево заданного графа $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$, не принадлежащее ни одному другому фундаментальному циклу. Таким образом, фундаментальные циклы образуют базис пространства циклов. Базис циклов, построенный таким способом, называется фундаментальным базисом циклов или строго фундаментальным базисом циклов.

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

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

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

Циклы граней

Если связный конечный планарный граф вложен в плоскость, каждая грань вложения окружена циклом рёбер. Одна грань будет неограничена (она содержит точки, произвольно далёкие от вершин графа), остальные грани будут ограничены. Согласно формуле Эйлера, существует ровно $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} )$ являются пометками рёбер графа числами со свойством, что в каждой вершине сумма меток входящих дуг равна сумме меток исходящих дуг. Групповая операция — это сложение векторов меток. Целый базис циклов — это множество простых циклов, которые генерируют эту группу.

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

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

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

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

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

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

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

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

NP-трудность

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

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

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

Приложения

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

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

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

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

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

Литература

• Reinhard Diestel. 1.9 Some linear algebra // Graph Theory. — Springer, 2012. — Т. 173. — С. 23–28. — (Graduate Texts in Mathematics).
• David M. Chickering, Dan Geiger, David Heckerman. On finding a cycle basis with a shortest maximal cycle // Information Processing Letters. — 1995. — Т. 54, вып. 1. — С. 55–58. — doi:10.1016/0020-0190(94)00231-M.
• J. D. Horton. A polynomial-time algorithm to find the shortest cycle basis of a graph // SIAM Journal on Computing. — 1987. — Т. 16, вып. 2. — С. 358–366. — doi:10.1137/0216026.
• S. Mac Lane. A combinatorial condition for planar graphs // Fundamenta Mathematicae. — 1937. — Т. 28. — С. 22–32.
• Oswald Veblen. An application of modular equations in analysis situs // Annals of Mathematics. — 1912. — Т. 14, вып. 1. — С. 86–94. — .
• Franziska Berger, Peter Gritzmann, Sven de Vries. Minimum cycle bases for network graphs // Algorithmica. — 2004. — Т. 40, вып. 1. — С. 51–62. — doi:10.1007/s00453-004-1098-x.
• Kurt Mehlhorn, Dimitrios Michail. Implementing minimum cycle basis algorithms // ACM Journal of Experimental Algorithmics. — 2006. — Т. 11. — doi:10.1145/1187436.1216582.
• Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch. An ${\tilde {O}}(m^{2}n)$ algorithm for minimum cycle basis of graphs // Algorithmica. — 2008. — Т. 52, вып. 3. — С. 333–349. — doi:10.1007/s00453-007-9064-z.
• Telikepalli Kavitha, Christian Liebchen, Kurt Mehlhorn, Dimitrios Michail, Romeo Rizzi, Torsten Ueckerdt, Katharina A. Zweig. Cycle bases in graphs: Characterization, algorithms, complexity, and applications // Computer Science Review. — 2009. — Т. 3, вып. 4. — С. 199–243. — doi:10.1016/j.cosrev.2009.08.001.
• W. T. Tutte. How to draw a graph // Proceedings of the London Mathematical Society. — 1963. — Т. 13. — С. 743–767. — doi:10.1112/plms/s3-13.1.743.
• D. W. Cribb, R. D. Ringeisen, D. R. Shier. Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. I (Baton Rouge, La., 1981). — 1981. — Т. 32. — С. 221–229. — (Congressus Numerantium).
• David Hartvigsen, Eitan Zemel. Is every cycle basis fundamental? // Journal of Graph Theory. — 1989. — Т. 13, вып. 1. — С. 117–137. — doi:10.1002/jgt.3190130115.
• David Hartvigsen, Russell Mardon. The all-pairs min cut problem and the minimum cycle basis problem on planar graphs // SIAM Journal on Discrete Mathematics. — 1994. — Т. 7, вып. 3. — С. 403–418. — doi:10.1137/S0895480190177042.
• Edoardo Amaldi, Claudio Iuliano, Romeo Rizzi. Integer Programming and Combinatorial Optimization: 14th International Conference, IPCO 2010, Lausanne, Switzerland, June 9-11, 2010, Proceedings. — Springer, 2010. — Т. 6080. — С. 397–410. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-13036-6_30.
• Giulia Galbiati, Edoardo Amaldi. Approximation and Online Algorithms: First International Workshop, WAOA 2003, Budapest, Hungary, September 16-18, 2003, Revised Papers. — Berlin: Springer, 2004. — Т. 2909. — С. 151–164. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-24592-6_12.
• Narsingh Deo, G. M. Prabhu, M. S. Krishnamoorthy. Algorithms for generating fundamental cycles in a graph // ACM Transactions on Mathematical Software. — 1982. — Т. 8, вып. 1. — С. 26–42. — doi:10.1145/355984.355988.
• Glencora Borradaile, Piotr Sankowski, Christian Wulff-Nilsen. Proc. 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010). — IEEE Computer Soc., Los Alamitos, CA, 2010. — С. 601–610. — doi:10.1109/FOCS.2010.63.
• Christian Liebchen, Romeo Rizzi. Classes of cycle bases // Discrete Applied Mathematics. — 2007. — Т. 155, вып. 3. — С. 337–355. — doi:10.1016/j.dam.2006.06.007.
• Christian Liebchen. Periodic timetable optimization in public transport // Operations Research Proceedings. — 2007. — Т. 2006. — С. 29–36. — doi:10.1007/978-3-540-69995-8_5.
• A. C. Cassell, J. C. De Henderson, A. Kaveh. Cycle bases for the flexibility analysis of structures // International Journal for Numerical Methods in Engineering. — 1974. — Т. 8, вып. 3. — С. 521–528. — doi:10.1002/nme.1620080308.
• Christian Boulinier, Franck Petit, Vincent Villain. Proceedings of the Twenty-third Annual ACM Symposium on Principles of Distributed Computing (PODC '04). — New York, NY, USA: ACM, 2004. — С. 150–159. — doi:10.1145/1011767.1011790.
• Derek Aguiar, Sorin Istrail. HapCompass: A Fast Cycle Basis Algorithm for Accurate Haplotype Assembly of Sequence Data // Journal of Computational Biology. — 2012. — Т. 19, вып. 6. — С. 577–590. — doi:10.1089/cmb.2012.0084.
• Sébastien Lemieux, François Major. Automated extraction and classification of RNA tertiary structure cyclic motifs // Nucleic Acids Research. — 2006. — Т. 34, вып. 8. — С. 2340–2346. — doi:10.1093/nar/gkl120.
• Sébastien Lemieux, François Major. Automated extraction and classification of RNA tertiary structure cyclic motifs // Nucleic Acids Research. — 2006. — Т. 34, вып. 8. — С. 2340–2346. — doi:10.1093/nar/gkl120.
• Craig Gotsman, Kanela Kaligosi, Kurt Mehlhorn, Dimitrios Michail, Evangelia Pyrga. Cycle bases of graphs and sampled manifolds // Computer Aided Geometric Design. — 2007. — Т. 24, вып. 8—9. — С. 464–480. — doi:10.1016/j.cagd.2006.07.001.
• Jonathan L. Gross, Jay Yellen. 4.6 Graphs and Vector Spaces // Graph Theory and Its Applications. — 2nd. — CRC Press, 2005. — С. 197–207. — ISBN 9781584885054.
• Romeo Rizzi. Minimum weakly fundamental cycle bases are hard to find // Algorithmica. — 2009. — Т. 53, вып. 3. — С. 402–424. — doi:10.1007/s00453-007-9112-8.