Isomorphism¶
|
Returns True if the graphs G1 and G2 are isomorphic and False otherwise. |
|
Returns False if graphs are definitely not isomorphic. |
|
Returns False if graphs are definitely not isomorphic. |
|
Returns False if graphs are definitely not isomorphic. |
Tree Isomorphism¶
An algorithm for finding if two undirected trees are isomorphic, and if so returns an isomorphism between the two sets of nodes.
This algorithm uses a routine to tell if two rooted trees (trees with a specified root node) are isomorphic, which may be independently useful.
This implements an algorithm from: The Design and Analysis of Computer Algorithms by Aho, Hopcroft, and Ullman Addison-Wesley Publishing 1974 Example 3.2 pp. 84-86.
A more understandable version of this algorithm is described in: Homework Assignment 5 McGill University SOCS 308-250B, Winter 2002 by Matthew Suderman http://crypto.cs.mcgill.ca/~crepeau/CS250/2004/HW5+.pdf
|
Given two rooted trees |
|
Given two undirected (or free) trees |