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

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

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

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

Определения

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

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

Охватывающий подграф данного графа 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. Гросс, Джонатан Л.; Йеллен, Джей (2005), «4.6 Графы и векторные пространства», Теория графов и ее приложения (2-е изд.), CRC Press, стр. 197–207, ISBN 9781584885054.
2. Diestel, Reinhard (2012), "1.9 Некоторые элементы линейной алгебры", Теория графов, Graduate Texts in Mathematics, т. 173, Springer, стр. 23–28.
3. Джоши, КД (1997), Прикладные дискретные структуры, New Age International, стр. 172, ISBN 9788122408263.
4. Уоллис, У. Д. (2010), Руководство для начинающих по теории графов, Springer, стр. 66, ISBN 9780817645809.
5. Эппштейн, Дэвид (1996), О четности чисел остовного дерева графа (PDF) , Технический отчет 96-14, Департамент информации и компьютерных наук, Калифорнийский университет, Ирвайн.
6. Serre, Jean-Pierre (2003), Деревья, Springer Monographs in Mathematics, Springer, стр. 23, ISBN 9783540442370.
7. Биггс, Норман (1993), Алгебраическая теория графов, Кембриджская математическая библиотека, Cambridge University Press, стр. 154, ISBN 9780521458979.
8. Бергер, Франциска; Грицманн, Питер; де Врис, Свен (2009), «Базы минимального цикла и их приложения», Алгоритмика больших и сложных сетей , Конспект лекций по информатике, т. 5515, стр. 34–49, doi :10.1007/978-3-642-02094-0_2, ISBN 978-3-642-02093-3.
9. Сеймур, ПД (1995), «Нигде-нулевые потоки», Справочник по комбинаторике, т. 1, 2 , Амстердам: Elsevier, стр. 289–299, MR  1373660.
10. Берж, Клод (2001), «Цикломатическое число», Теория графов, Courier Dover Publications, стр. 27–30, ISBN 9780486419756.
11. Веблен, Освальд (1912), «Применение модульных уравнений в анализе на месте», Annals of Mathematics , Вторая серия, 14 (1): 86–94, doi :10.2307/1967604, JSTOR  1967604.
12. Дистель (2012), стр. 32, 65.
13. Rizzi, Romeo (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