Namespaces
Variants
Actions

Difference between revisions of "Graph homeomorphism"

From Encyclopedia of Mathematics
Jump to: navigation, search
(TeX)
(Category:Combinatorics)
 
Line 1: Line 1:
 
{{TEX|done}}
 
{{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]]).
 
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]]).
 +
 +
[[Category:Combinatorics]]

Latest revision as of 17:22, 18 October 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=33818
This article was adapted from an original article by V.B. Alekseev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article