In topology, a branch of mathematics, a graph is a topological space which arises from a usual graph by replacing vertices by points and each edge by a copy of the unit interval , where is identified with the point associated to and with the point associated to . 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

under the quotient map used for gluing. Here is the 0-skeleton (consisting of one point for each vertex ), are the closed intervals glued to it, one for each edge , and is the disjoint union.[1]

The topology on this space is called the graph topology.

Subgraphs and trees

edit

A subgraph of a graph   is a subspace   which is also a graph and whose nodes are all contained in the 0-skeleton of  .   is a subgraph if and only if it consists of vertices and edges from   and is closed.[1]

A subgraph   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

edit
  • 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   contains at least one maximal tree  , that is, a tree that is maximal with respect to the order induced by set inclusion on the subgraphs of   which are trees.[1]
  • If   is a graph and   a maximal tree, then the fundamental group   equals the free group generated by elements  , where the   correspond bijectively to the edges of  ; in fact,   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

edit

References

edit
  1. ^ a b c d e f g Hatcher, Allen (2002). Algebraic Topology. Cambridge University Press. p. 83ff. ISBN 0-521-79540-0.