Homeomorphism (graph theory)
|
|
In graph theory, a homeomorphism exists between two graphs G and G′ if there exists a graph H such that both G and G′ are subdivisions of 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 graph-theoretic sense precisely if they are homeomorphic in the sense in which the term is used in topology.
In general, a subdivision of a graph G is a graph resulting from the subdivision of edges in G. The subdivision of some edge e with endpoints {u,w} yields a graph containing one new vertex v, and with an edge set replacing e by two new edges with endpoints {u,v} and {v,w}.
For example, if we have the graph G1
*--*--*--*
and G2
*--*--*--*--*
these two graphs are homeomorphic, since given the graph
*---*---* x y
subdividing edge x gives G1, and subdividing both x and y gives G2.