Graph (Topology)

In topology, a branch of mathematics, a graph is a topological space which arises from a usual graph [math]\displaystyle{ G = (E, V) }[/math] by replacing vertices by points and each edge [math]\displaystyle{ e = xy \in E }[/math] by a copy of the unit interval [math]\displaystyle{ I = [0,1] }[/math], where [math]\displaystyle{ 0 }[/math] is identified with the point associated to [math]\displaystyle{ x }[/math] and [math]\displaystyle{ 1 }[/math] with the point associated to [math]\displaystyle{ 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]\displaystyle{ X_0 \sqcup \bigsqcup_{e \in E} I_e }[/math]

under the quotient map used for gluing. Here [math]\displaystyle{ X_0 }[/math] is the 0-skeleton (consisting of one point for each vertex [math]\displaystyle{ x \in V }[/math]), [math]\displaystyle{ I_e }[/math] are the closed intervals glued to it, one for each edge [math]\displaystyle{ e \in E }[/math], and [math]\displaystyle{ \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]\displaystyle{ X }[/math] is a subspace [math]\displaystyle{ Y \subseteq X }[/math] which is also a graph and whose nodes are all contained in the 0-skeleton of [math]\displaystyle{ X }[/math]. [math]\displaystyle{ Y }[/math] is a subgraph if and only if it consists of vertices and edges from [math]\displaystyle{ X }[/math] and is closed.^[1]

A subgraph [math]\displaystyle{ 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]\displaystyle{ X }[/math] contains at least one maximal tree [math]\displaystyle{ 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]\displaystyle{ X }[/math] which are trees.^[1]
• If [math]\displaystyle{ X }[/math] is a graph and [math]\displaystyle{ T \subseteq X }[/math] a maximal tree, then the fundamental group [math]\displaystyle{ \pi_1(X) }[/math] equals the free group generated by elements [math]\displaystyle{ (f_\alpha)_{\alpha \in A} }[/math], where the [math]\displaystyle{ \{f_\alpha\} }[/math] correspond bijectively to the edges of [math]\displaystyle{ X \setminus T }[/math]; in fact, [math]\displaystyle{ 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

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Graph (topology). Read more