graph isomorphism
A graph isomorphism![Mathworld](http://mathworld.wolfram.com/favicon_mathworld.png)
is a bijection between the vertices of two graphs G and H:
with the property that any two vertices u and v from G are adjacent if and only if f(u) and f(v) are adjacent in H.
For example, consider these two graphs:
|
\xymatrixa\ar@-[r]\ar@-[rd]\ar@-[rdd]&gb\ar@-[ru]\ar@-[r]\ar@-[rdd]&hc\ar@-[ruu]\ar@-[r]\ar@-[rd]&id\ar@-[ruu]\ar@-[ru]\ar@-[r]&j |
|
|
\xymatrix1\ar@-[rrr]\ar@-[rd]\ar@-[ddd]&&&2&5&6\ar@-[ur]\ar@-[l]\ar@-[d]&&8\ar@-[u]\ar@-[r]\ar@-[dl]&7&4&&&3\ar@-[uuu]\ar@-[lll]\ar@-[ul] |
|
Although these graphs look very different at first, they are in fact isomorphic; one isomorphism between them is