Гомология графов - Graph homology

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

Первая группа гомологий

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

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

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

Пример

Позволять Икс быть ориентированный граф с 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.
• Третий цикл представлен циклом c-d. Здесь знак - означает, что край d перемещается назад.

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

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

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

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

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

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

Общий случай

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

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

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

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

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

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

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

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

Пример

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

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

Общий случай

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

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

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

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

Пониженная гомология

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

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

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

Гомологии более высокой размерности

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

Пример

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

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

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

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

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

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

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

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

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

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

Общий случай

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

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

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

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

Рекомендации

1. Сунада, Тошиказу (2013), Сунада, Тошиказу (ред.), "Группы гомологий графов", Топологическая кристаллография: с точки зрения дискретного геометрического анализа, Обзоры и учебные пособия по прикладным математическим наукам, Токио: Springer Japan, стр. 37–51, Дои:10.1007/978-4-431-54177-6_4, ISBN  978-4-431-54177-6
2. Вильдбергер, Норман Дж. (2012). «Введение в гомологию».
3. Вильдбергер, Норман Дж. (2012). «Вычисление групп гомологии».
4. Вильдбергер, Норман Дж. (2012). "Введение в гомологию (продолжение)".