В математической дисциплине теории графов пространство ребер и пространство вершин неориентированного графа представляют собой векторные пространства , определенные через множества ребер и вершин соответственно. Эти векторные пространства позволяют использовать методы линейной алгебры при изучении графа.
Пусть – конечный неориентированный граф. Вершинное пространство G — это векторное пространство над конечным полем двух элементов всех функций . Каждый элемент естественно соответствует подмножеству V , которое присваивает своим вершинам 1. Кроме того, каждое подмножество V однозначно представлено своей характеристической функцией. Реберное пространство — это -векторное пространство , свободно порожденное множеством ребер E. Таким образом, размерность пространства вершин — это количество вершин графа, а размерность пространства ребер — это количество ребер.
Эти определения можно сделать более явными. Например, мы можем описать краевое пространство следующим образом:
Одноэлементные подмножества E образуют основу для .
Можно также думать о наборе степеней V , превращенном в векторное пространство с аналогичным векторным сложением и скалярным умножением, как определено для .
Матрица инцидентности графа определяет одно возможное линейное преобразование.
между реберным пространством и пространством вершин . Матрица инцидентности , как линейное преобразование, отображает каждое ребро в две инцидентные вершины. Пусть будет грань между и тогда
Пространство цикла и пространство разреза являются линейными подпространствами реберного пространства.
