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

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

Определение

Позволять $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-е электронное издание находится в свободном доступе на сайте автора).

См. также

• велосипедное пространство
• вырезать пространство