[MUSIC] Hello everybody. Remember a couple of sessions ago we introduced graphs and the concept of graph isomorphism. So today, I want to talk about the isomorphism problem on trees. Remember I showed you a lot of different graphs and the question is, are they really so much different? So our example here, there are four graphs I claim they are all different. But for this graph here and this and this, it's pretty obvious that they are different because they are over different vertexes. But for the first graph and the second it's not so easy. However, you see this graph has an edge from zero to four and this graph doesn't. So therefore this graph are also not the same. However, re-assume they're all isomorphic, they are the same, it's just that the vertices have different names. Normally, that's the concept of a graph isomorphism informally, it means, g and h differ only in the names of their vertices. So, that's cheap talk. So, I mean, I can make definition a very key definition, say they only different in the names. However, to realy determine to see whether they are two different or they are only different in the names. It's much more difficult. Just to give you a taste that it's not so simple, look at this picture. You have a couple of graphs, all of them have ten vertices, are they the same, are they isomorphic, are they not? Okay, I'll let you figure it out by yourself, I just want to get you started. And, I want to claim that actually these two guys here are different from the rest. Why? You see here each firm has a four degree vertex, where is the other are all three regular. So, they are not isomorphic to the others. But are these two isomorphic, how about the remaining four? Well, that's a good exercise for you. So with each of them you can come up with a rather simple argument why they are isomorphic or why they are not. However, the question is, is there always a simple argument that tells you well these graphs are not isomorphic because blah blah blah blah blah. This is actually not known. So determining where the two graphs are isomorphic is whether you can do it efficiently is an open problem. Maybe if we restrict our attention to a simple graph class maybe we can do something. That's what we are going to do today. We talked about the isomorphism of trees. Here I have two trees, let's give the names and now I want to convince you that they are actually as a morphic. And I do that by renaming by naming the roteses in the right tree in way such that the isomorphism becomes evident. So the top vertex here I think this should be the vertex number three this is four, or five, six, one, two, seven. There you go staring long enough and you see that these trees are really isomorphic. But how can we algorithmically find this out? What we need is we need more structure, so we defined a tree to be a graph that is acyclic and connected but now let's add a little bit more structure, let's define rooted trees. So you have a tree and you single out one vertex to be the root vertex. Okay, that's a formal definition. And now we say two rooted trees are isomorphic, if there is an isomorphism that also maps the first root to the second root. For example here, you can easily see that these two here are isomorphic as rooted trees, but these two are not. For example here the root has two children that are leafs and here this only had one child which is a leaf. Okay so as rooted trees they are not isomorphic. To come up with an algorithm, we need even more structure. So we need to talk about not only about children but we need to talk about what is the first child, what is the second child, and so on. It means we need an ordering on children, something like this. So, formerly in order to trees I root a tree together with an ordering, linear ordering for every inner vertex. For every inner vertex knows what it's first trial, second trial and so on. That's an order to tree. And to order the tree isomorphic. If you find the isomorphism that maps the root here to the root there and also preserves the ordering of children. In we have two ordered trees it really becomes easy to check whether they're isomorphic. So you can see here, these trees are isomorphic as ordered trees, but these here are not. Because here the first child has two children, and here the first child doesn't have children. Okay, so as ordered trees they are not isomorphic. The idea is, if you have an ordered tree we can encode it in a way that from the encoding we can reconstruct it. So we can reconstruct our tree and two isomorphic ordered trees, map to the same sequence. And we can do it efficiently and this gives us a way to take isomorphism if you are given two ordered trees we simply compute the encoding and compare whether these two strings are the same. So here's where we are going to do it. We start at the root and then we do that first search. We enter the root and every time we go down, we output a one. So we go down. And we output a zero. If we go up, we output a one. Now our definite search goes back to the root. That's one we go down to zero, we go down again is zero. We go up, we go down twice it's two zero, we go up, one, two, three times. We go down, and we go up twice. And that I called pi of T. So pi of T is encoding of order to tree. Actually let me give you a recorded algorithm that tells in general how to encode it to tree. Here this, if T is a single root with no children, you return zero one. Else, T consists of a root vertex and subtrees T1, T2, up to Tk. And you return zero pi of two one up to pi of Tk and one. That's an recursive algorithm to compute an encoding. And the observation is if you have two ordered trees they are isomorphic if and only if the encoding is the same. All right, how do you encode rooted trees? Note if you have two trees that are isomorphic as rooted trees but not as ordered trees like these trees you see on the slide, the encoding will be different. Because the children have a different ordering. How can we do that? Well here is an obvious trick. Whenever we recursively compute the encoding of the children. We then sort them. Let's say from smallest to largest or something these strings. And then so by sorting first we make the ordering of the children irrelevant. And therefore it will become an encoding of rooted trees.ive For example here. These are trees all have encoding zero one. This has encoding zero, zero, one, one. This is zero, one. So here we get something like. Zero, zero one, zero zero one one one, let's call this x. So here we get something like zero, zero one x, zero one one. Whereas down here we get something else. Here again we get x. Because this is actually the same sub tree. So here we get zero x, zero one zero one one. Okay so these two encodings are the same. But now the trick will be when you recursively compute the encoding of your children you would sort them and then you stick it together. So you get the following algorithm. Looks very similar. If T is a single root you return zero one. Else, T looks like this, you have sub trees T one up to Tk and you compute pi I to be recursively I of Ti and then what you do is you sort the array. It doesn't really matter how you sort it. So for example, you put sort lexical graphically like in the order they would appear in a lexicon. And once you've sorted down, you just do the same as you did before. Just put them together you put a zero in the front a one in the end and that's it. And it is easy to see two ordered trees are isomorphic if and only if. Well to rooted trees. Two rooted trees are isomorphic if and only if they're encoded pi is the same. So how did you do that? How do you use that to solve the isomorphisms of trees. All the idea as try all roots. We do something like this, for all our one in V one and for all r two and V two. If the encoding of your rooted tree T one, r one is the same as the encoding of your rooted tree T two, r two you return true. And if none of the roots work, you return false. You can see this gives you an o of n cubed algorithm. But of course, this can be easily sped up by just not taking the first loop. In this pick r one arbitrarily. And its easy to see that it also works and it gives you o of n squared. There's actually an linear N algorithm which is a little bit, it's a little bit clever you have to look at the textbook it's nicely explain in there. And it's a method where you can't choose economical root, like they are if tree has an obvious vertex that's should be used as a root. And then you just choose this obvious vertices and then you do your isomorphism for rooted trees. And this gives you a linear end rhythm. All right, that's it for today. Thanks. [MUSIC].