Graph (topology)

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

${\displaystyle X_0\bigsqcup \underset{e\in E}{⨆}{I}_e}$

under the quotient map used for gluing. Here ${\displaystyle X_0}$ is the 0-skeleton (consisting of one point for each vertex ${\displaystyle x\in V}$), ${\displaystyle I_e}$ are the closed intervals glued to it, one for each edge ${\displaystyle e\in E}$, and ${\displaystyle \bigsqcup }$ is the disjoint union.^[1]

The topology on this space is called the graph topology.

A subgraph of a graph ${\displaystyle X}$ is a subspace ${\displaystyle Y\subseteq X}$ which is also a graph and whose nodes are all contained in the 0-skeleton of ${\displaystyle X}$. ${\displaystyle Y}$ is a subgraph if and only if it consists of vertices and edges from ${\displaystyle X}$ and is closed.^[1]

A subgraph ${\displaystyle T\subseteq X}$ 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.

• 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 ${\displaystyle X}$ contains at least one maximal tree ${\displaystyle T\subseteq X}$, that is, a tree that is maximal with respect to the order induced by set inclusion on the subgraphs of ${\displaystyle X}$ which are trees.^[1]
• If ${\displaystyle X}$ is a graph and ${\displaystyle T\subseteq X}$ a maximal tree, then the fundamental group ${\displaystyle {\pi }_1(X)}$ equals the free group generated by elements ${\displaystyle (f_{\alpha }{)}_{\alpha \in A}}$, where the ${\displaystyle \{f_{\alpha }\}}$ correspond bijectively to the edges of ${\displaystyle X\setminus T}$; in fact, ${\displaystyle X}$ 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]

• Graph homology
• Topological graph theory
• Nielsen–Schreier theorem, whose standard proof makes use of this concept.

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