Difference between revisions of "Graph homeomorphism"
From Encyclopedia of Mathematics
(Importing text file) |
(TeX) |
||
| Line 1: | Line 1: | ||
| − | An equivalence relation on the set of graphs, characterizing their geometric properties. The notion of a graph homeomorphism is defined as follows. Subdivision of an edge | + | {{TEX|done}} |
| + | An equivalence relation on the set of graphs, characterizing their geometric properties. The notion of a graph homeomorphism is defined as follows. Subdivision of an edge $(a,b)$ of a graph $G$ is an operation involving the addition of a new vertex $v$, the removal of $(a,b)$, and the addition of two new edges $(a,v)$ and $(v,b)$. Geometrically, this operation consists in addition of some (interior) point $v$ on the line $(a,b)$; this point then becomes a new vertex. A graph $G'$ is called a subdivision of a graph $G$ if it can be obtained from $G$ by repeating the operation of edge subdivision several times. Two graphs $G_1$ and $G_2$ are said to be homeomorphic if they have isomorphic subdivisions (cf. [[Graph isomorphism|Graph isomorphism]]). | ||
Revision as of 11:37, 29 June 2014
An equivalence relation on the set of graphs, characterizing their geometric properties. The notion of a graph homeomorphism is defined as follows. Subdivision of an edge $(a,b)$ of a graph $G$ is an operation involving the addition of a new vertex $v$, the removal of $(a,b)$, and the addition of two new edges $(a,v)$ and $(v,b)$. Geometrically, this operation consists in addition of some (interior) point $v$ on the line $(a,b)$; this point then becomes a new vertex. A graph $G'$ is called a subdivision of a graph $G$ if it can be obtained from $G$ by repeating the operation of edge subdivision several times. Two graphs $G_1$ and $G_2$ are said to be homeomorphic if they have isomorphic subdivisions (cf. Graph isomorphism).
How to Cite This Entry:
Graph homeomorphism. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Graph_homeomorphism&oldid=16244
Graph homeomorphism. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Graph_homeomorphism&oldid=16244
This article was adapted from an original article by V.B. Alekseev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article