Гомология графов - Википедия - Graph homology

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

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

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

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

Пример

Позволять Икс быть ориентированный граф с 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

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

Большинство элементов C1 не являются циклами, например a + b, 2a + 5b-c и т. д. не являются циклами. Чтобы формально определить цикл, сначала определим границы. Граница ребра обозначается значком оператор и определяется как его цель минус его источник, поэтому Так это отображение из C1 к C0. Поскольку a, b, c, d являются генераторами C1, это естественно распространяется на групповой гомоморфизм из C1 к C0. В этом гомоморфизме . По аналогии, отображает любой цикл в C1 к нулевому элементу C0. Другими словами, множество циклов в C1 точно нулевое пространство (ядро) из . В этом случае ядро имеет два образующих: один соответствует a + b + c, а другой - a + b + d (третий цикл, c-d, представляет собой линейную комбинацию первых двух). Так кер изоморфен Z2.

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

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

Общий случай

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

.

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

.

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

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

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

Пример

Напомним, что группа C0 порождается множеством вершин. Поскольку нет -1-мерных элементов, группа C−1 тривиальна, поэтому вся группа C0 является ядром соответствующего граничного оператора: = свободная абелева группа, порожденная {x, y, z}.[3]

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

Общий случай

Приведенный выше пример можно обобщить на любой связный граф. Начиная с любой вершины, можно попасть в любую другую вершину, добавив к ней одно или несколько выражений, соответствующих ребрам (например, начиная с x, можно добраться до z, добавив y-x и z-y). Поскольку элементы все равны нулю, это означает, что все вершины графа находятся в одном классе эквивалентности, и поэтому изоморфен Z.

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

.

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

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

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

.

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

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

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

Пример

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

Как и граничный оператор из C1 к C0, который обозначим через , существует граничный оператор из C2 к C1, который обозначим через . В частности, границей двумерной ячейки A являются одномерные ребра c и d, где c находится в «правильной» ориентации, а d - в «обратной» ориентации; следовательно: . Последовательность цепочек и граничных операторов можно представить следующим образом:[4]

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

Здесь, - группа одномерных циклов, изоморфная Z2, и - группа одномерных циклов, являющихся границами двумерных ячеек, изоморфная Z. Следовательно, их частное ЧАС1 изоморфен Z. Это соответствует тому, что Икс теперь есть единственное отверстие. Ранее. образ был тривиальная группа, поэтому частное было равно . Предположим теперь, что мы добавляем еще одну ориентированную двумерную ячейку B между ребрами c и d, такую ​​что . Сейчас же C2 это свободная абелева группа генерируется {A, B}. Это не меняет ЧАС1 - он все еще изоморфен Z (X все еще имеет одну одномерную дырку). Но сейчас C2 содержит двумерный цикл A-B, поэтому имеет нетривиальное ядро. Этот цикл порождает вторую группу гомологий, соответствующую тому факту, что существует единственная двумерная дыра:

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

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

Общий случай

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

Можно доказать, что любая граница a (k+1) -мерная ячейка является k-мерный цикл. Другими словами, для любого k, (группа границ k+1 элементов) содержится в (группа k-мерные циклы). Следовательно, частное хорошо определен, и он определяется как k-я группа гомологий:

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

  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). "Введение в гомологию (продолжение)".