Graph (topology)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In topology, a subject in 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

(disjoint union)

under the quotient map used for gluing, where is the 0-skeleton (consisting one point for each vertex ) and are the intervals ("closed one-dimensional unit balls") glued to it, one for each edge .[1]

The topology on this space is called the graph topology.[2]

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 iff it is contractible as a topological space.[1]

Properties[edit]

  • Every connected graph contains a 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.[2]
  • The associated topological space of a graph is connected (with respect to the graph topology) if and only if the original graph is connected.[2]
  • Every covering space projecting to a graph is also a graph.[1]

Applications[edit]

Using the above properties of graphs, one can prove the Nielsen–Schreier theorem.[1]

See also[edit]

References[edit]

  1. ^ a b c d e f g h Hatcher, Allen (2002). Algebraic Topology. Cambridge University Press. p. 83ff. ISBN 0-521-79540-0. 
  2. ^ a b c Michael Slone (8 May 2003). "graph topology". PlanetMath. Retrieved 1 February 2017.