Identifying Isomorphic Trees | Graph Theory

Key Takeaways

[Music] hello and welcome my name is William and today we're diving into isomorphisms with trees a question of tree equality and what that means when we're talking about general graphs and asked whether two graphs are isomorphic we're essentially asking whether they're structurally the same in the middle of this slide you'll see two graphs G 1 and G 2 they are labeled differently and kind of appear different but they are structurally the same graph so they're isomorphic you could for example conceptually unfold the graph on the right to match the one on the left and then real able its vertices and you would have two identical graphs we can also define the notion of a graph isomorphism more rigorously because saying that two graphs have the same structure is not very well defined so if we define a graph G 1 as the set of edges e1 and the vertices V 1 and another graph G 2 in the same manner we say that the two graphs G 1 and G 2 are isomorphic if there exists a bi junction between the sets of vertices v1 and v2 such that for all the pairs of vertices which form an edge in G 1 applying the function Phi to the nodes of all those edges always results in an edge which is present in G 2 so in layman's terms this means that for an isomorphism to exist there needs to be a function which can map all the nodes and edges in G 1 2 G 2 and vice versa as it turns out determining if two graphs are isomorphic is not only not obvious to the human eye but is actually also a very difficult problem for it is still an open question as to whether the graph isomorphism problem is np-complete however luckily for us there are many polynomial time algorithms which exists for specialized graph types including trees for determining whether they're isomorphic or not let's have a look at a few examples I'm going to show you two trees and you have to tell me whether they're isomorphic or not so our tree 1 and tree 2 isomorphic no they're not because they're structurally different what about 3 3 and 3/4 yes they're isomorphic in terms of writing an algorithm for identifying isomorphic trees there are several very quick probabilistic usually hash of heuristic based algorithms for identifying isomorphic trees these algorithms tend to be very fast but also more error-prone due to hash collisions in a limited integer space however they do have their place when it comes to competitive programming and testing the Equality of absolutely enormous trees however the method we'll be looking at today involves serializing a tree into a unique encoding this encoding is simply a string that represents the tree and if another tree has the same encoding then we say that both trees are isomorphic when we're going about encoding a tree you can either directly serialize the unrooted tree but in practice I find it much easier to write the code to serialize a rooted tree this is just my personal preference however one small caveat to watch out for if you're going for the rooted tree approach is to make sure you route both of your trees t1 and t2 with the same root node before you begin the serialization process otherwise you get two different encodings one trick we can use to help ourselves select a common node between both trees is to reuse what we learned in the last video about finding the center of a tree now let's have a look at the entire flow of how encoding a tree is going to work first we start out with two trees t1 and t2 which may or may not be isomorphic that's what we're trying to figure out from here find the center of both trees for now don't worry about the case where one of the trees has more than one Center we'll see how to handle this later next route the trees at their center nodes then generate the encoding for each tree and compare the serialized tree values for equality the dream coding is simply a sequence of left and right brackets however you can also think of them as zeros and ones which is just a really large number if you prefer from this encoding it should also be possible to reconstruct the original tree solely based on this encoding I will leave this as an exercise to the reader the ahu algorithm short for the initials of the three authors who created the algorithm is a clever serialization technique for representing a tree as a unique string unlike many tree isomorphism invariance in heuristics ahu is able to capture a complete history of a trees degree spectrum and structure in turn this ensures a deterministic method of checking for tree isomorphisms let's take a closer look at how this works suppose we have this tree and we wish to encode it the first thing we do is assign all leaf nodes Knuth tuples which are a pair of left and right brackets after that for all the nodes with greyed out children combine their children's labels and wrap them in a new pair of brackets it's clearer if I highlight how the brackets were combined if you look at the leftmost branch you can see that we combined the labels from node six and node seven and then wrapped them in a new bracket set to create the label for node two if we continue and process all nodes which have greyed out children which is currently only node one then you see that we've combined the labels from node four and node five to create node one's new label one thing you'll notice is that in the combining phase the child labels need to get sorted this is very important because it is what ensures uniqueness now we get to process the last node here we combine and sort the labels from nodes two one and three to create the final serialised encoding which is always at the root note in hindsight this algorithm isn't too complicated but I find it extremely clever props to the original authors who created it in summary of what we just looked at one leaf nodes are assigned Knuth tuples consisting of a left and right bracket to begin with two every time you move up a layer the labels of the previous sub trees and need to get sorted lexicographically and then wrapped in brackets three you cannot process a node until you have processed all its children okay good now let's have a look at some pseudocode for testing tree isomorphisms the trees are isomorphic method takes in two undirected trees as input tree one and tree two both of which are stored as adjacency lists the first thing we do is find the center node or nodes of these two trees this is a method I'm borrowing from one slide deck ago after that a root tree one using the first center node which there will always be at least one of the root tree method is the same one we covered two videos ago check the description if you need a refresher on that now as a reminder I'm storing rooted trees in this code as tree node objects defined on this slide I do this to facilitate writing recursive algorithms but also to keep our tree data structure organized once we have rooted our tree we can serialize it with encode method let's take a closer look at what's going on there the encode method is the one which generates the unique string for our tree the first thing I do is handle the base case where we have a null node for this we can return an empty string which will cause all leaf nodes to have a left and right bracket as a starting value upon the callback for each node we maintain a list of labels for all the sub trees to generate the labels iterate through all the children of this node and recursively call the encode method adding the results to the labels list after the for loop the recursive calls have returned and the labels list is populated and ready to be sorted afterwards concatenate the labels and wrap the result in brackets coming back to the main method now the next thing we want to do is encode the second tree and compare the encoded results but if the tree has two centers we don't know which center node in the second tree is the correct one so we need to try both for this iterate over both centers and root the tree comparing the encoded result with the one from the first tree if there's any match then we know for sure that the trees are isomorphic awesome thank you for watching and if you learned something please give this video a thumbs up and subscribe for more than that like some keep your science videos thank you