|
|
|
|
|
Homeomorphism (Graph Theory)A homeomorphism in graph theory exists between two graphs G and G′ if there exists a graph that can be found from subdivision of edges in that graph. If the edges of a graph are thought of as lines drawn from one vertex to another (as they are usually depicted in illustrations), then two graphs are homeomorphic to each other in the present sense precisely if they are homeomorphic in the sense in which the term is used in topology. Subdivision means that if we have an edge e={u, w}, we insert a new vertex v and divide e into two edges {u, v} and {v, w}. For example, if we have the graph G1 *--*--*--*--* and G2 *--*--*--* these two graphs are homeomorphic since if we have the graph: *---*---* x y subdividing edge x gives G2, and subdividing x and y gives G1.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|