Английская Википедия:Graph (topology)
Шаблон:Short description In topology, a branch of mathematics, a graph is a topological space which arises from a usual graph <math>G = (E, V)</math> by replacing vertices by points and each edge <math>e = xy \in E</math> by a copy of the unit interval <math>I = [0,1]</math>, where <math>0</math> is identified with the point associated to <math>x</math> and <math>1</math> with the point associated to <math>y</math>. That is, as topological spaces, graphs are exactly the simplicial 1-complexes and also exactly the one-dimensional CW complexes.[1]
Thus, in particular, it bears the quotient topology of the set
- <math>X_0 \sqcup \bigsqcup_{e \in E} I_e</math>
under the quotient map used for gluing. Here <math>X_0</math> is the 0-skeleton (consisting of one point for each vertex <math>x \in V</math>), <math>I_e</math> are the closed intervals glued to it, one for each edge <math>e \in E</math>, and <math>\sqcup</math> is the disjoint union.[1]
The topology on this space is called the graph topology.
Subgraphs and trees
A subgraph of a graph <math>X</math> is a subspace <math>Y \subseteq X</math> which is also a graph and whose nodes are all contained in the 0-skeleton of <math>X</math>. <math>Y</math> is a subgraph if and only if it consists of vertices and edges from <math>X</math> and is closed.[1]
A subgraph <math>T \subseteq X</math> is called a tree if it is contractible as a topological space.[1] This can be shown equivalent to the usual definition of a tree in graph theory, namely a connected graph without cycles.
Properties
- The associated topological space of a graph is connected (with respect to the graph topology) if and only if the original graph is connected.
- Every connected graph <math>X</math> contains at least one maximal tree <math>T \subseteq X</math>, that is, a tree that is maximal with respect to the order induced by set inclusion on the subgraphs of <math>X</math> which are trees.[1]
- If <math>X</math> is a graph and <math>T \subseteq X</math> a maximal tree, then the fundamental group <math>\pi_1(X)</math> equals the free group generated by elements <math>(f_\alpha)_{\alpha \in A}</math>, where the <math>\{f_\alpha\}</math> correspond bijectively to the edges of <math>X \setminus T</math>; in fact, <math>X</math> is homotopy equivalent to a wedge sum of circles.[1]
- Forming the topological space associated to a graph as above amounts to a functor from the category of graphs to the category of topological spaces.
- Every covering space projecting to a graph is also a graph.[1]
See also
- Graph homology
- Topological graph theory
- Nielsen–Schreier theorem, whose standard proof makes use of this concept.
References
