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

построение в теории графов

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

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

• 1 Определения
  • 1.1 Теория графов
  • 1.2 Алгебра
  • 1.3 Топология
• 2 Схема ранг
• 3 Базы цикла
  • 3.1 Существование
  • 3.2 Фундаментальные и слабо фундаментальные базисы
  • 3.3 Базы минимального веса
• 4 Планарные графы
  • 4.1 Гомология
  • 4.2 Критерий планарности Мак-Лейна
  • 4.3 Двойственность
  • 4.4 Нигде нулевые потоки
• 5 Ссылки

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

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

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

Алгебра

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

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

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

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

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

Топология

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

$H\; 1\; (G,\; Z\; 2)\; \{\backslash \; displaystyle\; H\_\; \{1\}\; (G,\; \backslash \; mathbb\; \{Z\}\; \_\; \{2\})\}$

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

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

$H\; 1\; (G,\; Z).\; \{\backslash \; displaystyle\; H\_\; \{1\}\; (G,\; \backslash \; mathbb\; \{Z\}).\}$

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

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

Как векторное пространство, размерность цикла пространство графа с $n\; \{\backslash \; displaystyle\; n\}$вершинами, $m\; \{\backslash \; displaystyle\; m\}$ребрами и $c\; \{\backslash \; displaystyle\; c\}$соединенные компоненты - это $m\; -\; n\; +\; c\; \{\backslash \; displaystyle\; m-n\; +\; c\}$. Это число можно интерпретировать топологически как первое число Бетти на графике. В теории графов это известно как ранг схемы, цикломатическое число или нулевое значение графа.

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

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

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

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

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

Один из способов построения базиса цикла состоит в том, чтобы сформировать покрывающий лес графа, а затем для каждого ребра $e\; \{\backslash \; displaystyle\; e\}$, не принадлежащий лесу, образуют цикл $C\; e\; \{\backslash \; displaystyle\; C\_\; \{e\}\}$, состоящий из $e\; \{\backslash \; displaystyle\; e\}$вместе с путем в лесу, соединяющим конечные точки $e\; \{\backslash \; displaystyle\; e\}$. Набор циклов $C\; e\; \{\backslash \; displaystyle\; C\_\; \{e\}\}$, сформированный таким образом, линейно независим (каждый из них содержит ребро $e\; \{\backslash \; displaystyle\; e\}$, который не принадлежит ни к одному из других циклов) и имеет правильный размер $m\; -\; n\; +\; c\; \{\backslash \; displaystyle\; m-n\; +\; c\}$, чтобы быть основой, поэтому он обязательно является основание. Основание, сформированное таким образом, называется базисом основного цикла .

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

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

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

Гомология

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

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

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

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

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

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

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