Гомологии графов

В алгебраической топологии и теории графов гомологии графов описывают группы гомологии графа , где граф рассматривается как топологическое пространство . Он формализует представление о количестве «дырок» в графе. Это частный случай симплициальной гомологии , поскольку граф является частным случаем симплициального комплекса. Поскольку конечный граф является 1-комплексом (т. е. его «гранями» являются вершины, которые являются 0-мерными, и ребра, которые являются 1-мерными), единственными нетривиальными группами гомологии являются 0-я группа. и 1-я группа.

1-я группа гомологии

Общая формула для 1-й группы гомологии топологического пространства X :

$$H_{1}(X):=\ker \partial _{1}{\big /}\operatorname {im} \partial _{2}$$

В приведенном ниже примере эти символы и понятия подробно объясняются на графике.

Пример

Пусть X — ориентированный граф с 3 вершинами {x,y,z} и 4 ребрами {a: x→y, b: y→z, c: z→x, d: z→x}. Он имеет несколько циклов :

• Один цикл представлен циклом a+b+c. Здесь знак плюс означает, что все ребра движутся в одном направлении. Поскольку операция сложения коммутативна, знак + обозначает тот факт, что циклы a+b+c, b+c+a и c+a+b представляют один и тот же цикл.
• Второй цикл представлен циклом a+b+d.
• Третий цикл представлен циклом c-d. Здесь знак минус обозначает тот факт, что ребро d движется назад.

Если разрезать плоскость по петле a+b+d, а затем разрезать по петле c и «склеить» по d, то получим разрез по петле a+b+c. Это можно представить следующим соотношением: (a+b+d) + (cd) = (a+b+c). Чтобы формально определить это отношение, определим следующие коммутативные группы:

• C ₀ — свободная абелева группа, порожденная множеством вершин {x,y,z}. элемент C0 _. называется 0-мерной цепью Каждый
• C ₁ — свободная абелева группа, порожденная множеством направленных ребер {a,b,c,d}. Каждый элемент C ₁ называется 1-мерной цепью . Три упомянутых выше цикла представляют собой одномерные цепи, и действительно, в группе C ₁ выполняется соотношение (a+b+d) + (cd) = (a+b+c) .

Большинство элементов C ₁ не являются циклами, например a+b, 2a+5b-c и т. д. не являются циклами. Чтобы формально определить цикл, мы сначала определяем границы . Границу ребра обозначают $\partial _{1}$ оператор и определяется как его цель минус его источник, поэтому $\partial _{1}(a)=y-x,~\partial _{1}(b)=z-y,~\partial _{1}(c)=\partial _{1}(d)=x-z.$ Так $\partial _{1}$ является отображением группы C ₁ в группу C ₀ . c,d являются генераторами C1 _{Поскольку a,b ,} , это $\partial _{1}$ естественным образом продолжается до группового гомоморфизма из C ₁ в C ₀ . В этом гомоморфизме $\partial _{1}(a+b+c)=\partial _{1}(a)+\partial _{1}(b)+\partial _{1}(c)=(y-x)+(z-y)+(x-z)=0$. Сходным образом, $\partial _{1}$ отображает любой цикл в C ₁ в нулевой элемент C ₀ . Другими словами, набор циклов в C ₁ порождает нулевое пространство (ядро ) $\partial _{1}$. В этом случае ядро $\partial _{1}$ имеет два образующих: один соответствует a+b+c, другой — a+b+d (третий цикл cd представляет собой линейную комбинацию первых двух). Итак, кер $\partial _{1}$изоморфен Z ² .

В общем топологическом пространстве мы бы определили цепи более высокой размерности. В частности, C2 _{будет свободной абелевой группой} на множестве двумерных объектов. Однако в графе таких объектов нет, поэтому C2 _— тривиальная группа. Поэтому образ второго граничного оператора $\partial _{2}$, тоже тривиально. Поэтому:

$$H_{1}(X)=\ker \partial _{1}{\big /}\operatorname {im} \partial _{2}\cong \mathbb {Z} ^{2}/\mathbb {Z} ^{0}=\mathbb {Z} ^{2}$$

Это соответствует интуитивному факту, что в графе есть две «дыры». Показатель степени – это количество дырок.

Общий случай

Приведенный выше пример можно обобщить на произвольный связный граф G = ( V , E ). Пусть T — дерево группы G. остовное Каждое ребро в E \ T соответствует циклу; это именно линейно независимые циклы. Следовательно, первая группа гомологий H ₁ графа — это свободная абелева группа с | Э \ Т | генераторы. Это число равно | Е |-| В |+1; так:

$$H_{1}(X)\cong \mathbb {Z} ^{|E|-|V|+1}.$$

В несвязном графе, когда C представляет собой набор связных компонентов, аналогичные вычисления показывают:

$$H_{1}(X)\cong \mathbb {Z} ^{|E|-|V|+|C|}.$$

В частности, первая группа тривиальна тогда и только тогда, когда X — лес .

0-я группа гомологии

Общая формула 0-й группы гомологий топологического пространства X :

$$H_{0}(X):=\ker \partial _{0}{\big /}\operatorname {im} \partial _{1}$$

Пример

Возвращаемся к графу с 3 вершинами {x,y,z} и 4 ребрами {a: x→y, b: y→z, c: z→x, d: z→x}. Напомним, что группа C ₀ порождается множеством вершин. Поскольку (−1)-мерных элементов нет, группа C ₋₁ тривиальна, и поэтому вся группа C0 _{является} ядром соответствующего граничного оператора: $\ker \partial _{0}=C_{0}$ = свободная абелева группа, порожденная {x,y,z}.

Образ $\partial _{1}$ содержит элемент для каждой пары вершин, являющихся границами ребра, т. е. порождается разностями {y−x, z−y, x−z}. Чтобы вычислить факторгруппу, удобно подумать обо всех элементах $\operatorname {im} \partial _{1}$ как «эквивалентный нулю». Это означает, что x, y и z эквивалентны — они находятся в одном классе эквивалентности фактора. Другими словами, $H_{0}(X)$ генерируется одним элементом (его может генерировать любая вершина). Таким образом, он изоморфен Z .

Общий случай

Приведенный выше пример можно обобщить на любой связный граф . Начиная с любой вершины, можно попасть в любую другую вершину, добавив к ней одно или несколько выражений, соответствующих ребрам (например, начиная с x, можно попасть в z, сложив yx и zy). Поскольку элементы $\operatorname {im} \partial _{1}$ все вершины графа эквивалентны нулю, это означает, что все вершины графа принадлежат одному классу эквивалентности, и, следовательно, $H_{0}(X)$ изоморфен Z .

В общем случае граф может иметь несколько компонент связности . Пусть C — множество компонентов. Тогда каждая компонента связности является классом эквивалентности в факторгруппе. Поэтому:

$$H_{0}(X)\cong \mathbb {Z} ^{|C|}.$$

Его можно сгенерировать любым | C |-кортеж вершин, по одной от каждого компонента.

Уменьшенная

Часто удобно предполагать, что 0-я гомология связного графа тривиальна (так что, если граф содержит одну точку, то все его гомологии тривиальны). Это приводит к определению приведенной гомологии . Для графа приведенная 0-я гомология равна:

$${\tilde {H_{0}}}(X)\cong \mathbb {Z} ^{|C|-1}.$$

Эта «редукция» затрагивает только 0-ю гомологию; приведенные гомологии высших размерностей равны стандартным гомологиям.

высших

Граф имеет только вершины (0-мерные элементы) и ребра (1-мерные элементы). Мы можем обобщить граф до абстрактного симплициального комплекса , добавив элементы более высокого измерения. Затем понятие гомологии графов обобщается понятием симплициальной гомологии .

Пример

В приведенном выше примере графика мы можем добавить двумерную «ячейку», заключенную между ребрами c и d; назовем его А и предположим, что он ориентирован по часовой стрелке. Определим C ₂ как свободную абелеву группу, порожденную набором двумерных ячеек, который в данном случае является одноэлементным {A}. Каждый элемент C ₂ называется двумерной цепью .

Точно так же, как граничный оператор от C ₁ до C ₀ , который мы обозначаем через $\partial _{1}$, существует граничный оператор из C ₂ в C ₁ , который мы обозначим через $\partial _{2}$. В частности, границей двумерной ячейки A являются одномерные ребра c и d, где c находится в «правильной» ориентации, а d — в «обратной» ориентации; поэтому: $\partial _{2}(A)=c-d$. Последовательность цепочек и граничных операторов можно представить следующим образом:

$$C_{2}\xrightarrow {\partial _{2}} C_{1}\xrightarrow {\partial _{1}} C_{0}$$

Добавление двумерной ячейки A означает, что ее граница cd больше не представляет собой дырку (она гомотопна одной точке). Следовательно, группа «дырок» теперь имеет единственный образующий, а именно a+b+c (он гомотопен a+b+d). Первая группа гомологии теперь определяется как факторгруппа :

$$H_{1}(X):=\ker \partial _{1}{\big /}\operatorname {im} \partial _{2}$$

Здесь, $\ker \partial _{1}$ — группа одномерных циклов, изоморфная Z ² , и $\operatorname {im} \partial _{2}$ — группа одномерных циклов, являющихся границами двумерных ячеек, изоморфная Z . Следовательно, их фактор H ₁ изоморфен Z . Это соответствует тому факту, что X теперь имеет одну дырку. Ранее. образ $\partial _{2}$ была тривиальной группой , поэтому частное было равно $\ker \partial _{1}$. Предположим теперь, что мы добавим еще одну ориентированную двумерную ячейку B между ребрами c и d, такую, что $\partial _{2}(B)=\partial _{2}(A)=c-d$. Теперь C ₂ — свободная абелева группа, порожденная {A,B}. Это не меняет H ₁ — он по-прежнему изоморфен Z (X по-прежнему имеет одну одномерную дырку). Но теперь C2 _{поэтому} содержит двумерный цикл AB, $\partial _{2}$ имеет нетривиальное ядро. Этот цикл порождает вторую группу гомологии, соответствующую факту наличия единственной двумерной дыры:

$$H_{2}(X):=\ker \partial _{2}\cong \mathbb {Z}$$

Мы можем продолжить и добавить 3-клетку — твердый 3-мерный объект (называемый C), ограниченный A и B. Определим C ₃ как свободную абелеву группу, порожденную {C}, и граничный оператор $\partial _{3}:C_{3}\to C_{2}$. Мы можем ориентировать C так, чтобы $\partial _{3}(C)=A-B$; заметим, что граница C является циклом в C ₂ . Теперь вторая группа гомологии:

$$H_{2}(X):=\ker \partial _{2}{\big /}\operatorname {im} \partial _{3}\cong {0}$$

соответствующее тому факту, что двумерных дыр нет (C «заполняет дыру» между A и B).

Общий случай

В общем, можно определить цепи любой размерности. Если максимальная размерность цепочки равна k , то мы получаем следующую последовательность групп:

$$C_{k}\xrightarrow {\partial _{k}} C_{k-1}\cdots C_{1}\xrightarrow {\partial _{1}} C_{0}$$

Можно доказать, что любая граница ( k +1)-мерной клетки является k -мерным циклом. Другими словами, для k любого $\operatorname {im} \partial _{k+1}$(группа границ из k +1 элементов) содержится в $\ker \partial _{k}$ (группа k -мерных циклов). Следовательно, частное $\ker \partial _{k}{\big /}\operatorname {im} \partial _{k+1}$ корректно определена и определяется как k -я группа гомологии:

$$H_{k}(X):=\ker \partial _{k}{\big /}\operatorname {im} \partial _{k+1}$$