Краевые и вершинные пространства

В математической дисциплине теории графов и пространство ребер пространство вершин неориентированного графа представляют собой векторные пространства, определенные в терминах наборов ребер и вершин соответственно. Эти векторные пространства позволяют использовать методы линейной алгебры при изучении графа.

Определение

Позволять $G:=(V,E)$ — конечный неориентированный граф. Вершинное пространство ${\mathcal {V}}(G)$ группы G — векторное пространство над конечным полем двух элементов $\mathbb {Z} /2\mathbb {Z} :=\lbrace 0,1\rbrace$ всех функций $V\rightarrow \mathbb {Z} /2\mathbb {Z}$ . Каждый элемент ${\mathcal {V}}(G)$ естественно соответствует подмножеству V , которое присваивает своим вершинам 1. Кроме того, каждое подмножество V уникально представлено в ${\mathcal {V}}(G)$ по своей характерной функции. Краевое пространство ${\mathcal {E}}(G)$ это $\mathbb {Z} /2\mathbb {Z}$ -векторное пространство, свободно порожденное множеством ребер E . Таким образом, размерность пространства вершин — это количество вершин графа, а размерность пространства ребер — это количество ребер.

Эти определения можно сделать более явными. Например, мы можем описать краевое пространство следующим образом:

элементы являются подмножествами $E$ , то есть как набор ${\mathcal {E}}(G)$ - мощности набор E
Сложение векторов определяется как симметричная разность : $P+Q:=P\triangle Q\qquad P,Q\in {\mathcal {E}}(G)$
скалярное умножение определяется следующим образом:
- $0\cdot P:=\emptyset \qquad P\in {\mathcal {E}}(G)$
- $1\cdot P:=P\qquad P\in {\mathcal {E}}(G)$

Одноэлементные образуют подмножества E основу для ${\mathcal {E}}(G)$ .

Можно также подумать о ${\mathcal {V}}(G)$ как набор степеней V, преобразованный в векторное пространство с аналогичным сложением векторов и скалярным умножением, как определено для ${\mathcal {E}}(G)$ .

Характеристики

Матрица заболеваемости $H$ для графика $G$ определяет одно возможное линейное преобразование

H:{\mathcal {E}}(G)\to {\mathcal {V}}(G)

между реберным пространством и пространством вершин $G$ . Матрица заболеваемости $G$ , как линейное преобразование, отображает каждое ребро в две инцидентные ему вершины. Позволять $vu$ быть границей между $v$ и $u$ затем

H(vu)=v+u

и Пространство цикла пространство разреза являются линейными подпространствами реберного пространства.

Ссылки

Дистель, Рейнхард (2005), Теория графов (3-е изд.), Springer , ISBN 3-540-26182-6 (3-е электронное издание находится в свободном доступе на сайте автора).

См. также