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

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

Первая группа гомологий [ править ]

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

{\ displaystyle 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, c + b + a, c + a + b и т. Д. Представляют один и тот же цикл.
Второй цикл представлен циклом a + b + d.
Третий цикл представлен циклом cd. Здесь знак - означает, что край d перемещается назад.

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

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

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

В общем топологическом пространстве мы бы определяли многомерные цепи. В частности, C ₂ будет свободной абелевой группой на множестве двумерных объектов. Однако в графе таких объектов нет, поэтому C ₂ - тривиальная группа. Следовательно, образ второго граничного оператора, также тривиален. Следовательно: $\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 соответствует циклу; это в точности линейно независимые циклы. Таким образом, первая группа гомологии Н ₁ из графа является свободная абелева группа с | E \ T | генераторы. Это число равно | E | - | V | +1; итак: ^[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}

Пример [ править ]

Напомним, что группа C ₀ порождается множеством вершин. Поскольку нет -1-мерных элементов, группа C ₋₁ тривиальна, и поэтому вся группа C ₀ является ядром соответствующего граничного оператора: = свободная абелева группа, порожденная {x, y, z}. ^[3] $\ker \partial _{0}=C_{0}$

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

Общий случай [ править ]

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

В общем, граф может иметь несколько связных компонентов . Пусть 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; назовем его A и предположим, что он ориентирован по часовой стрелке. Определим C ₂ как свободную абелеву группу, порожденную множеством двумерных ячеек, которая в данном случае является одноэлементной {A}. Каждый элемент C ₂ называется двумерной цепью .

Подобно граничному оператору от C ₁ до C ₀ , который мы обозначаем , существует граничный оператор от C ₂ до C ₁ , который мы обозначаем через . В частности, границей двумерной ячейки A являются одномерные ребра c и d, где c находится в «правильной» ориентации, а d - в «обратной» ориентации; Таким образом: . Последовательность цепочек и граничных операторов можно представить следующим образом: ^[4] $\partial _{1}$ $\partial _{2}$ $\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}

Здесь есть группа 1-мерных циклы, которая изоморфна Z ² , и является группой 1-мерных циклов , которые являются границами 2-мерных клеток, которая изоморфна Z . Следовательно, их отношение Н ₁ изоморфна Z . Это соответствует тому факту, что теперь у X есть единственное отверстие. Ранее. образ был тривиальной группой , поэтому фактор был равен . Предположим теперь, что мы добавляем еще одну ориентированную двумерную ячейку B между ребрами c и d, такую что . Теперь C ₂ - свободная абелева группа

\ker \partial _{1}

\operatorname {im} \partial _{2}

\partial _{2}

\ker \partial _{1}

\partial _{2}(B)=\partial _{2}(A)=c-d

генерируется {A, B}. Это не меняет H ₁ - оно все еще изоморфно Z (X все еще имеет одну одномерную дырку). Но теперь C ₂ содержит двумерный цикл AB, поэтому имеет нетривиальное ядро. Этот цикл порождает вторую группу гомологий, соответствующую тому факту, что существует единственная двумерная дыра:

\partial _{2}

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

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

\partial _{3}:C_{3}\to C_{2}

\partial _{3}(C)=A-B

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 -мерным циклом. Другими словами, для любого к , (группа границ к +1 элементов) содержится в (группа K - мерных циклов). Следовательно, фактор-фактор корректно определен, и он определяется как k -я группа гомологий:

\operatorname {im} \partial _{k+1}

\ker \partial _{k}

\ker \partial _{k}{\big /}\operatorname {im} \partial _{k+1}

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

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

^ a b Sunada, Toshikazu (2013), Sunada, Toshikazu (ed.), «Группы гомологий графов», Топологическая кристаллография: с точки зрения дискретного геометрического анализа , обзоров и учебных пособий по прикладным математическим наукам, Токио: Springer Japan, . С. 37-51, DOI : 10.1007 / 978-4-431-54177-6_4 , ISBN 978-4-431-54177-6
^ Вильдбергер, Норман Дж. (2012). «Введение в гомологию» .
^ Вильдбергер, Норман Дж. (2012). «Вычисление групп гомологий» .
^ Вильдбергер, Норман Дж. (2012). «Введение в гомологию (продолжение)» .

[:1-1] Sunada, Toshikazu (2013), Sunada, Toshikazu (ed.), «Группы гомологий графов», Топологическая кристаллография: с точки зрения дискретного геометрического анализа , обзоров и учебных пособий по прикладным математическим наукам, Токио: Springer Japan, . С. 37-51, DOI : 10.1007 / 978-4-431-54177-6_4 , ISBN 978-4-431-54177-6

[:0-2] Вильдбергер, Норман Дж. (2012). «Введение в гомологию» .

[3] Вильдбергер, Норман Дж. (2012). «Вычисление групп гомологий» .

[4] Вильдбергер, Норман Дж. (2012). «Введение в гомологию (продолжение)» .

[1]