词条 | Edge space |
释义 |
In the mathematical discipline of graph theory, the edge space and vertex space of an undirected graph are vector spaces defined in terms of the edge and vertex sets, respectively. These vector spaces make it possible to use techniques of linear algebra in studying the graph. DefinitionLet be a finite undirected graph. The vertex space of G is the vector space over the finite field of two elements of all functions . Every element of naturally corresponds the subset of V which assigns a 1 to its vertices. Also every subset of V is uniquely represented in by its characteristic function. The edge space is the -vector space freely generated by the edge set E. The dimension of the vertex space is thus the number of vertices of the graph, while the dimension of the edge space is the number of edges. These definitions can be made more explicit. For example, we can describe the edge space as follows:
The singleton subsets of E form a basis for . One can also think of as the power set of V made into a vector space with similar vector addition and scalar multiplication as defined for . PropertiesThe incidence matrix for a graph defines one possible linear transformation between the edge space and the vertex space of . The incidence matrix of , as a linear transformation, maps each edge to its two incident vertices. Let be the edge between and then The cycle space and the cut space are linear subspaces of the edge space. References
| last=Diestel | first=Reinhard | title=Graph Theory | publisher=Springer | year=2005 | edition=3rd | isbn=3-540-26182-6 | url=http://diestel-graph-theory.com/ }} (the electronic 3rd edition is freely available on author's site). See also
1 : Algebraic graph theory |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。