Пространства ребер и вершин

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

Определение [ править ]

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

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

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

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

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

Свойства [ править ]

Матрица частоты для графа определяет одно из возможного линейного преобразования${\ displaystyle H}$${\ displaystyle G}$

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

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

${\ Displaystyle H (vu) = v + u}$

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

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

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

См. Также [ править ]

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