Namespaces
Variants
Actions

Difference between revisions of "Graph homeomorphism"

From Encyclopedia of Mathematics
Jump to: navigation, search
(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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044930/g0449301.png" /> of a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044930/g0449302.png" /> is an operation involving the addition of a new vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044930/g0449303.png" />, the removal of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044930/g0449304.png" />, and the addition of two new edges <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044930/g0449305.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044930/g0449306.png" />. Geometrically, this operation consists in addition of some (interior) point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044930/g0449307.png" /> on the line <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044930/g0449308.png" />; this point then becomes a new vertex. A graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044930/g0449309.png" /> is called a subdivision of a graph <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044930/g04493010.png" /> if it can be obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044930/g04493011.png" /> by repeating the operation of edge subdivision several times. Two graphs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044930/g04493012.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g044/g044930/g04493013.png" /> are said to be homeomorphic if they have isomorphic subdivisions (cf. [[Graph isomorphism|Graph isomorphism]]).
+
{{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=32339
This article was adapted from an original article by V.B. Alekseev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article