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

Все подграфы четной степени графа

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

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

Определения

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

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

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

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

Алгебра

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

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

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

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

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

Топология

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

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

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

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

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

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

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

Ранг цепи

В качестве векторного пространства размерность пространства циклов графа с вершинами, ребрами и связными компонентами равна . ^{[1] [2] [10]} Топологически это число можно интерпретировать как первое число Бетти графа. ^[6] В теории графов это известно как ранг цепи , цикломатическое число или нуль графа. ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle c}$ ${\displaystyle m-n+c}$

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

Базы цикла

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

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

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

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

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

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

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

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

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

Гомология

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

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

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

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

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

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

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

Рекомендации

1. Gross, Джонатан Л.; Йеллен, Джей (2005), «4.6 Графы и векторные пространства», Теория графов и ее приложения (2-е изд.), CRC Press, стр. 197–207, ISBN 9781584885054.
2. Дистель, Рейнхард (2012), «1.9 Некоторые линейные алгебры», Теория графов, Тексты для выпускников по математике, том. 173, Спрингер, стр. 23–28..
3. Джоши, К.Д. (1997), Прикладные дискретные структуры, New Age International, стр. 172, ИСБН 9788122408263.
4. Уоллис, WD (2010), Руководство для начинающих по теории графов, Springer, стр. 66, ISBN 9780817645809.
5. Эппштейн, Дэвид (1996), О четности чисел связующего дерева графа (PDF) , Технический отчет 96-14, Департамент информации и компьютерных наук, Калифорнийский университет, Ирвин.
6. Серр, Жан-Пьер (2003), Деревья, Монографии Springer по математике, Springer, стр. 23, ISBN 9783540442370.
7. Биггс, Норман (1993), Алгебраическая теория графов, Кембриджская математическая библиотека, издательство Кембриджского университета, стр. 154, ISBN 9780521458979.
8. Бергер, Франциска; Грицманн, Питер; де Врис, Свен (2009), «Базисы минимального цикла и их приложения», Алгоритма больших и сложных сетей , Конспекты лекций по информатике, том. 5515, стр. 34–49, номер домена : 10.1007/978-3-642-02094-0_2, ISBN. 978-3-642-02093-3.
9. Сеймур, П.Д. (1995), «Потоки в никуда-ноль», Справочник по комбинаторике, Vol. 1, 2 , Амстердам: Elsevier, стр. 289–299, MR  1373660..
10. Берже, Клод (2001), «Цикломатическое число», Теория графов, Courier Dover Publications, стр. 27–30, ISBN 9780486419756.
11. Веблен, Освальд (1912), «Применение модульных уравнений в анализе ситуации», Annals of Mathematics , Second Series, 14 (1): 86–94, doi : 10.2307/1967604, JSTOR  1967604.
12. Дистель (2012), стр. 32, 65.
13. Рицци, Ромео (2009), «Трудно найти минимальные слабо фундаментальные основания цикла», Algorithmica , 53 (3): 402–424, doi : 10.1007/s00453-007-9112-8, MR  2482112.
14. Дистель (2012), стр. 105–106.
15. Мак Лейн, С. (1937), «Комбинаторное условие для плоских графов» (PDF) , Fundamenta Mathematicae , 28 : 22–32.
16. Хартвигсен, Дэвид; Мардон, Рассел (1994), «Проблема минимального разреза для всех пар и задача базиса минимального цикла на плоских графах», SIAM Journal on Discrete Mathematics , 7 (3): 403–418, doi : 10.1137/S0895480190177042, MR  1285579.
17. Томас, Робин (1999), «Недавние исключенные второстепенные теоремы для графов», Обзоры по комбинаторике, 1999 (PDF) , Cambridge University Press, стр. 201–222