Велосипедное пространство

Эта статья о концепции теории графов . Информацию о месте, отведенном для велосипедов, см. в разделе «Велоинфраструктура» .

В теории графов , разделе математики, (двоичное) пространство циклов неориентированного графа представляет собой набор его подграфов четной степени .

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

Определения

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

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

данного Охватывающий подграф графа G может быть определен из любого подмножества S ребер G . Подграф имеет тот же набор вершин , что и сам G (в этом смысл слова «охват»), но элементы S являются его ребрами. Таким образом, граф G с m ребрами имеет 2 ^м охватывающий подграфы, включая сам G , а также пустой граф на том же наборе вершин, что и G . подграфов графа G образует реберное пространство G Совокупность всех охватывающих .

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

Алгебра

Если применить любую операцию над множеством, такую ​​как объединение или пересечение множеств, к двум охватывающим подграфам данного графа, результатом снова будет подграф. Таким образом, реберное пространство произвольного графа можно интерпретировать как булевую алгебру .

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

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

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

Краевое пространство также является векторным пространством над $\mathbb {Z} _{2}$ с симметричной разностью как сложением. Как векторные пространства, пространство циклов и пространство разрезов графа (семейство множеств ребер, охватывающих разрезы графа) являются ортогональными дополнениями друг друга в пространстве ребер. Это означает, что набор $S$ ребер в графе образует разрез тогда и только тогда, когда каждый эйлеров подграф имеет четное число общих ребер с $S$, и $S$ образует эйлеров подграф тогда и только тогда, когда каждый разрез имеет четное число общих ребер с $S$. Хотя эти два пространства являются ортогональными дополнениями, в некоторых графах есть непустые подграфы, принадлежащие им обоим. Такой подграф (эйлеров разрез) существует как часть графа $G$ тогда и только тогда, когда $G$ имеет четное количество охватывающих лесов .

Топология

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

$H_{1}(G,\mathbb {Z} _{2})$

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

Замена $\mathbb {Z} _{2}$ в этой конструкции произвольным кольцом позволяет расширить определение пространств циклов до пространств циклов с коэффициентами из данного кольца, которые образуют модули над кольцом. В частности, целочисленным пространством циклов является пространство

$H_{1}(G,\mathbb {Z} ).$

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

Член $H_{1}(G,\mathbb {Z} )$ или из $H_{1}(G,\mathbb {Z} _{k})$ (пространство цикла по модулю $k$) с дополнительным свойством, заключающимся в том, что все числа, присвоенные ребрам, ненулевые, называется потоком с нигде ненулевым потоком или потоком с нигде ненулевым значением. $k$-поток.

Ранг цепи

Основная статья: Цепной ранг

В качестве векторного пространства размерность пространства циклов графа с $n$ вершины, $m$ края, и $c$ компоненты связанные $m-n+c$. Это число можно топологически интерпретировать как первое число Бетти графа. В теории графов это известно как ранг схемы , цикломатическое число или нуль графа.

Сочетание этой формулы для ранга с тем фактом, что пространство циклов является векторным пространством над двухэлементным полем, показывает, что общее количество элементов в пространстве циклов точно равно $2^{m-n+c}$.

Базы цикла

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

Базис . векторного пространства — это минимальное подмножество элементов, обладающее тем свойством, что все остальные элементы могут быть записаны как линейная комбинация базисных элементов Каждый базис конечномерного пространства имеет одинаковое количество элементов, равное размерности пространства. В случае пространства циклов базисом является семейство ровно $m-n+c$ Эйлеровы подграфы, обладающие тем свойством, что каждый эйлеров подграф можно записать как симметричную разность семейства базисных элементов.

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

По Веблена теореме Каждый эйлеров подграф данного графа может быть разложен на простые циклы , подграфы, в которых все вершины имеют нулевую или вторую степень и в которых вершины второй степени образуют связное множество. Следовательно, всегда можно найти базис, в котором все элементы базиса сами являются простыми циклами. Такой базис называется цикловым базисом данного графа. Более строго, всегда можно найти базис, в котором базисными элементами являются индуцированные циклы или даже (в 3-вершинно-связном графе ) неразделяющие индуцированные циклы.

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

Один из способов построения базиса цикла — сформировать максимальный лес графа, а затем для каждого ребра $e$ что не принадлежит лесу, образуют цикл $C_{e}$ состоящий из $e$ вместе с тропинкой в ​​лесу, соединяющей конечные точки $e$. Циклы $C_{e}$ сформированные таким образом линейно независимы (каждая из них содержит ребро $e$ который не принадлежит ни одному из других циклов) и имеет правильный размер $m-n+c$ быть основой, поэтому оно обязательно является основой. Сформированный таким образом базис называется базисом фундаментального цикла (по отношению к выбранному лесу).

Если существует линейное упорядочение циклов в базисе цикла такое, что каждый цикл включает хотя бы одно ребро, не входящее в состав какого-либо предыдущего цикла, то базис цикла называется слабо фундаментальным . Каждый фундаментальный базис цикла является слабо фундаментальным (для всех линейных порядков), но не обязательно наоборот. Существуют графы и базисы циклов для этих графов, которые не являются слабо фундаментальными.

Базовый минимальный вес

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

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

Гомология

Если планарный граф вложен в плоскость, его цепной комплекс ребер и вершин может быть встроен в цепной комплекс более высокой размерности, который также включает в себя наборы граней графа. Граничное отображение этого цепного комплекса переводит любую 2-цепь (набор граней) в множество ребер, принадлежащих нечетному числу граней в 2-цепи.Граница 2-цепи обязательно является эйлеровым подграфом, и каждый эйлеров подграф может быть порожден таким образом ровно из двух разных 2-цепей (каждая из которых является дополнением другой). Из этого следует, что набор ограниченных граней вложения образует базис цикла для плоского графа: удаление неограниченной грани из этого набора циклов уменьшает количество способов генерации каждого эйлерова подграфа с двух до ровно одного.

Лейна

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

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

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

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

Потоки в никуда-ноль

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