Цикл пространство

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

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

Определения [ править ]

Теория графов [ править ]

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

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

Алгебра [ править ]

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

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

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

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

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

Ссылки [ править ]