Введение

Все подграфы графа с четной степенью. Понятие в теории графов.

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

Определения

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

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

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

Граф G или один из его подграфов называется эйлеровым, если каждая его вершина имеет четное число инцидентных ребер (это число называется степенью вершины). Это свойство названо в честь Леонарда Эйлера, который доказал в 1736 году в своей работе «Семь мостов Кёнигсберга», что связный граф имеет тур, проходящий по каждому ребру ровно один раз, тогда и только тогда, когда он является эйлеровым. Однако, для целей определения циклических пространств, эйлеров подграф не обязательно должен быть связным; например, пустой граф, в котором все вершины изолированы друг от друга, является эйлеровым в этом смысле. Циклическое пространство графа – это совокупность его расширяющих эйлеровых подграфов. Циклическое пространство также обладает алгебраической структурой, но более ограничительной. Объединение или пересечение двух эйлеровых подграфов может не быть эйлеровым. Однако симметричная разность двух эйлеровых подграфов (граф, состоящий из ребер, принадлежащих ровно одному из двух заданных графов) снова является эйлеровым. Это поле имеет два элемента, 0 и 1, и его операции сложения и умножения могут быть описаны как привычное сложение и умножение целых чисел по модулю 2. Векторное пространство состоит из множества элементов вместе с операциями сложения и скалярного умножения, удовлетворяющими определенным свойствам, обобщающим свойства знакомых вещественных векторных пространств. Для циклического пространства элементами векторного пространства являются эйлеровы подграфы, операцией сложения – симметричная разность, умножение на скаляр 1 – это тождественная операция, а умножение на скаляр 0 переводит каждый элемент в пустой граф, который является аддитивным элементом нейтрали для циклического пространства. Пространство ребер также является векторным пространством над полем из двух элементов, где сложением является симметричная разность. Как векторные пространства, циклическое пространство и пространство разрезов графа (семейство множеств ребер, которые охватывают разрезы графа) являются ортогональными дополнениями друг друга в пространстве ребер. Это означает, что множество ребер в графе образует разрез, тогда и только тогда, когда каждый эйлеров подграф имеет четное число ребер, общих с этим множеством, а множество образует эйлеров подграф, тогда и только тогда, когда каждый разрез имеет четное число ребер, общих с ним.

Рейтинг цепи

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

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

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

Минимальные весовые основания

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

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

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

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

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

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

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