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

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

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

Определения

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

Остовным подграфом заданного графа ${\displaystyle G}$ называется его

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

Алгебра

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

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

). В циклическом пространстве векторами будут эйлеровы подграфы, их сложению соответствует симметрическая разность, умножению на скаляр ${\displaystyle 1}$ — тождественное отображение, а умножение на скаляр ${\displaystyle 0}$ превращает любой подграф в пустой, который соответствует нулевому вектору циклического пространства.

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

.

Топология

Неориентированный граф можно рассматривать как

Группа гомологий

${\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}$ эйлеровых подграфов, таких что любой эйлеров подграф может быть представлен в виде симметрической разности некоторого набора базисных циклов.

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

По

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

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

Чтобы построить базис циклов можно сконструировать

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

Базис называется слабо фундаментальным, если на множестве циклов можно установить

.

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

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

.

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

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

Критерий

.

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

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

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

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

.

Примечания