Пространство циклов

Пространство циклов неориентированного графа — линейное пространство над полем ${\displaystyle \mathbb {F} _{2}}$, состоящее из его эйлеровых подграфов. Размерность этого пространства называется контурным рангом графа. С точки зрения алгебраической топологии циклическое пространство является первой группой гомологий графа.

Определения

Теория графов

Остовным подграфом заданного графа ${\displaystyle G}$ называется его подграф ${\displaystyle S}$, такой что множество вершин ${\displaystyle S}$ совпадает с множеством вершин ${\displaystyle G}$. Таким образом, любой граф с ${\displaystyle m}$ рёбрами имеет ${\displaystyle 2^{m}}$ остовных подграфов, включая сам ${\displaystyle G}$ и пустой граф на наборе вершин графа ${\displaystyle G}$. Семейство всех остовных подграфов ${\displaystyle G}$ образует рёберное пространство данного графа. Граф называется эйлеровым если каждой его вершине инцидентно чётное число рёбер (другими словами, степень любой вершины графа чётна). Семейство всех эйлеровых остовных подграфов образует циклическое пространство данного графа[1][2].

Алгебра

Симметрическая разность двух эйлеровых подграфов (красный и зелёный) также является эйлеровым подграфом (синий).

Рёберное пространство любого графа замкнуто относительно теоретико-множественных операций, поэтому оно образует булеву алгебру[3]. Циклические пространства также обладают алгебраической структурой: объединение или пересечение эйлеровых подграфов может не быть эйлеровым, но их симметрическая разность будет[1]. Это связано с тем, что симметрическая разность множеств с чётным набором элементов (окрестности вершины в первом и во втором подграфах) также содержит чётное множество элементов.

Семейство множеств, замкнутое относительно симметрической разности может быть алгебраически описано векторным пространством над двухэлементным конечным полем ${\displaystyle \mathbb {F} _{2}}$[4]. Данное поле состоит из двух элементов, ${\displaystyle 0}$ и ${\displaystyle 1}$, а сложение и умножение соответствуют логическим операциям исключающего «или» и конъюнкции (сложение и умножение по модулю 2). В циклическом пространстве векторами будут эйлеровы подграфы, их сложению соответствует симметрическая разность, умножению на скаляр ${\displaystyle 1}$ — тождественное отображение, а умножение на скаляр ${\displaystyle 0}$ превращает любой подграф в пустой, который соответствует нулевому вектору циклического пространства.

Рёберное пространство также является векторным пространством над ${\displaystyle \mathbb {F} _{2}}$ с операцией симметрической разности в качестве сложения. Циклическое пространство и пространство разрезов[5] являются ортогональными дополнениями друг друга внутри рёберного пространства. Это значит, что множество рёбер ${\displaystyle S}$ является разрезом если и только если любой эйлеров подграф содержит чётное число рёбер из ${\displaystyle S}$ и, наоборот, множество ${\displaystyle S}$ является эйлеровым подграфом если и только если любой разрез содержит чётное число рёбер из ${\displaystyle S}$[2]. Хотя эти пространства и являются ортогональными дополнениями друг друга, у них может быть нетривиальное пересечение. В общем случае, у графа ${\displaystyle G}$ есть непустой эйлеров разрез если и только если число его остовных лесов чётно[6].

Топология

Неориентированный граф можно рассматривать как симплициальный комплекс, чьи вершины являются нуль-мерными симплексами, а рёбра — одномерными симплексами[7]. Цепной комплекс такого топологического пространства состоит из его рёберного и вершинного пространств, связанных граничным оператором, который переводит любой остовный подграф (элемент рёберного пространства) в его множество вершин нечётной степени (элемент вершинного пространства). Группа гомологий ${\displaystyle H_{1}(G,\mathbb {F} _{2})}$ состоит из элементов рёберного пространства, которые переводятся граничным оператором в нулевой элемент вершинного пространства, то есть, из эйлеровых подграфов. Соответственно, групповой операцией здесь является симметрическая разность эйлеровых графов.

Определение циклического пространства может быть расширено заменой ${\displaystyle \mathbb {F} _{2}}$ на произвольное кольцо, результирующая группа гомологий будет модулем над данным кольцом[8]. В частности, целочисленным циклическим пространством называют группу гомологий ${\displaystyle H_{1}(G,\mathbb {Z} )}$. В теоретико-графовых терминах такое пространство может быть определено заданием ориентации на графе и определением целочисленного цикла как набора целых чисел, присвоенных рёбрам графа таким образом, что в любой вершине сумма чисел, присвоенных рёбрам, входящим в неё, равна сумме чисел, присвоенных рёбрам, исходящим из неё. Соответственно, целочисленное циклическое пространство состоит из всех целочисленных циклов, а сложению векторов в данном пространстве будет соответствовать сложение чисел, присвоенных каждому ребру в отдельности[9].

Элементы ${\displaystyle H_{1}(G,\mathbb {Z} )}$ или ${\displaystyle H_{1}(G,\mathbb {Z} _{k})}$ (циклического пространства по модулю ${\displaystyle k}$) с дополнительным условием, что все присвоенные числа являются ненулевыми называются нигде не нулевыми потоками[10].

Циклический ранг

Основная статья: Контурный ранг

Размерность пространства циклов графа с ${\displaystyle n}$ вершинами, ${\displaystyle m}$ рёбрами и ${\displaystyle c}$ компонентами связности равна ${\displaystyle m-n+c}$[1][2][11]. Это число можно топологически интерпретировать как первое число Бетти графа[7]. В теории графов оно также известно как циклический ранг и цикломатическое число. Из того, что пространство циклов является векторным пространством над двухэлементным полем следует, что общее число элементов пространства циклов равно ${\displaystyle 2^{m-n+c}}$.

Базис циклов

Основная статья: Базис циклов

Базис пространства циклов представляет собой семейство из ${\displaystyle m-n+c}$ эйлеровых подграфов, таких что любой эйлеров подграф может быть представлен в виде симметрической разности некоторого набора базисных циклов.

Существование

По теореме Веблена[12] любой эйлеров подграф может быть разложен в сумму простых циклов — подграфов, все рёбра которой образуют одну компоненту связности, все вершины которой имеют степень ${\displaystyle 2}$. Таким образом, всегда существует базис, все элементы которого являются простыми циклами. Такой базис называется базисом циклов данного графа. Более того, всегда возможно построить такой базис, что все его элементы будут порождёнными циклами (то есть, циклами без хорд в исходном графе)[13].

Фундаментальные и слабо фундаментальные базисы

Чтобы построить базис циклов можно сконструировать остовный лес графа, а затем для каждого ребра ${\displaystyle e}$, не принадлежащего лесу сформировать цикл ${\displaystyle C_{e}}$, состоящий из ${\displaystyle e}$ вместе с путём в остовном лесу, соединяющем концы ребра. Множество сформированных таким образом циклов является линейно независимым (так как каждый цикл содержит ребро ${\displaystyle e}$, не принадлежащее другим циклам) и состоит из ${\displaystyle m-n+c}$ циклов, поэтому гарантированно является базисом. Построенный таким образом базис называют фундаментальным базисом циклов[1].

Базис называется слабо фундаментальным, если на множестве циклов можно установить линейный порядок, такой что каждый цикл содержит хотя бы одно ребро, которое не содержится ни в одном из предыдущих циклов. Любой фундаментальный базис циклов является слабо фундаментальным (для любых порядков), обратное не верно. Существуют графы, некоторые из базисов циклов которых не являются слабо фундаментальными[14].

Базис наименьшего веса

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

Планарные графы

Критерий планарности Маклейна

Основная статья: Критерий планарности Маклейна

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

Двойственность

Пространство циклов планарного графа является пространством разрезов двойственного к нему графа, и наоборот. Базис наименьшего веса в планарном графе не обязательно совпадает с базисом из границ его граней, описанным выше. Однако, у планарного графа всегда есть базис наименьшего веса, в котором никакие два базисных цикла не пересекаются. Из двойственности пространств циклов и разрезов следует, что такой базис циклов планарного графа соответствует дереву Гомори — Ху двойственного ему графа, которое задаёт базис наименьшего веса в его пространстве разрезов[17].

Нигде не нулевые потоки

В планарных графах раскраски с ${\displaystyle k}$ различными цветами двойственны нигде не нулевым потокам над полем ${\displaystyle \mathbb {Z} _{k}}$ остатков по модулю ${\displaystyle k}$. Разность между номерами цветов соседних граней в данной двойственности представляется значением потока, текущего по ребру, которое разделяет эти грани. В частности, существование нигде не нулевого 4-потока в любом планарном графе эквивалентно теореме о четырёх красках. Теорема о снарках обобщает данный результат на непланарные графы[18].

Примечания

1. Gross, Jonathan L.; Yellen, Jay (2005), "4.6 Graphs and Vector Spaces", Graph Theory and Its Applications (2nd ed.), CRC Press, pp. 197—207, ISBN 9781584885054, Архивировано из оригинала 2 мая 2019, Дата обращения: 10 февраля 2020.
2. Diestel, Reinhard (2012), "1.9 Some linear algebra", Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer, pp. 23—28, Архивировано из оригинала 2 мая 2019, Дата обращения: 10 февраля 2020.
3. Joshi, K. D. (1997), Applied Discrete Structures, New Age International, p. 172, ISBN 9788122408263.
4. Wallis, W. D. (2010), A Beginner's Guide to Graph Theory, Springer, p. 66, ISBN 9780817645809.
5. Здесь под разрезом графа ${\displaystyle G=(V,E)}$ имеется в виду множество рёбер ${\displaystyle S}$, такое что множество вершин ${\displaystyle V}$ может быть разбито на два непересекающихся подмножества ${\displaystyle A}$ и ${\displaystyle B}$, таких что ${\displaystyle S=E\cap (A\times B)}$.
6. Eppstein, David (1996), On the Parity of Graph Spanning Tree Numbers (PDF), Technical Report 96-14, Department of Information and Computer Science, University of California, Irvine, Архивировано из оригинала (PDF) 5 октября 2020, Дата обращения: 10 февраля 2020
7. Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, p. 23, ISBN 9783540442370
8. Biggs, Norman (1993), Algebraic Graph Theory, Cambridge Mathematical Library, Cambridge University Press, p. 154, ISBN 9780521458979
9. Berger, Franziska; Gritzmann, Peter; de Vries, Sven (2009), "Minimum cycle bases and their applications", Algorithmics of Large and Complex Networks, Lecture Notes in Computer Science, vol. 5515, pp. 34—49, doi:10.1007/978-3-642-02094-0_2, ISBN 978-3-642-02093-3
10. Seymour, P. D. (1995), "Nowhere-zero flows", Handbook of combinatorics, Vol. 1, 2, Amsterdam: Elsevier, pp. 289—299, MR 1373660
11. Berge, Claude (2001), "Cyclomatic number", The Theory of Graphs, Courier Dover Publications, pp. 27—30, ISBN 9780486419756
12. Veblen, Oswald (1912), "An application of modular equations in analysis situs", Annals of Mathematics, Second Series, 14 (1): 86—94, doi:10.2307/1967604, JSTOR 1967604
13. Diestel (2012), pp. 32, 65.
14. Rizzi, Romeo (2009), "Minimum weakly fundamental cycle bases are hard to find", Algorithmica, 53 (3): 402—424, doi:10.1007/s00453-007-9112-8, MR 2482112
15. Diestel (2012), pp. 105—106.
16. Mac Lane, S. (1937), "A combinatorial condition for planar graphs" (PDF), Fundamenta Mathematicae, 28: 22—32, Архивировано из оригинала (PDF) 20 января 2022, Дата обращения: 10 февраля 2020
17. Hartvigsen, David; Mardon, Russell (1994), "The all-pairs min cut problem and the minimum cycle basis problem on planar graphs", SIAM Journal on Discrete Mathematics, 7 (3): 403—418, doi:10.1137/S0895480190177042, MR 1285579
18. Thomas, Robin (1999), "Recent Excluded Minor Theorems for Graphs", Surveys in Combinatorics, 1999 (PDF), Cambridge University Press, pp. 201—222, Архивировано из оригинала (PDF) 3 августа 2016, Дата обращения: 10 февраля 2020