Graph Theory: Paths and Circuits
Isomorphism
Two graphs are thought of as equivalent and are called isomorphic if they have identical behavior in terms of graph theoretic properties.
Two graphs G and G' are said to be isomorphic to each other if there is one-to-one correspondence between their vertices and between their edges such that the incidence relationship is preserved.
In other words suppose that edge e is incident on vertieces v1 and v2 in G; then corresponding edge e' in G' must be incident on the vertices v1' and v2' that correspond to v1 and v2 respectively.
Two isomorphic graphs must have:
1. The same number of vertices.
2. The same number of edges.
3. And equal number of vertices with a given degree.
These conditions are by no means sufficient. Finding simple and efficient criteria for detection of isomorphism is still actively pursued and is an important unsolved problem in graph theory.
No comments:
Post a Comment