Tuesday 1 January 2013

Graph Homeomorphism

  Two graphs G and H are said to be homeomorphic if there is an Isomorphism from some subdivision of G to some subdivision of H. A subdivision of a Graph is obtained by adding vertices in the middle of existing edges. Homomorphism and Homeomorphism are different. Homomorphism is discussed in the previous post. If you have any doubt refer that post.

Figure Given Below Shows Graphs N, O and P which are Subdivisions of Graph M

  Two graphs are homeomorphic if and only if they have at least one common subdivision. 

The Two Graphs Shown Below are Homeomorphic to each other
 
The Common Subdivision of the Two Graphs is Shown Below

No comments:

Post a Comment