Identifying Isomorphic Trees | Graph Theory

Identifying and encoding isomorphic trees

Algorithms repository:

Video slides:

Video source code:

0:00 Introduction
0:24 Graph Isomorphism
3:04 Identifying Isomorphic Trees
5:39 Generating the tree encoding
7:57 Tree Encoding Summary
8:23 Unrooted tree encoding pseudocode

===================================

[zubayirhkazi]

This is pretty brilliant and the applications must be extensive I can already see.

[kevintran]

Your video is helpful and easier to follow. That's not an easy thing that other YouTuber can do

[daveturnbull]

I paused the video when you showed the second pair of trees to see if I could come up with a method to check them:
Step 1: Compare count of nodes. Same count = POSSIBLE isomorphism.
Step 2: Get degree of each node in each tree and sort by degree. Same pattern = POSSIBLE isomorphism.
Step 3: Get the degree of each connected node and sort. Same pattern = POSSIBLE isomorphism.
Step 4: Repeat step 3 until either a mismatch or all levels of connection are explored.
If at the end the data matches then they are isomorphic.
I was really pleased with myself at coming up with that then you went and burst my bubble with the much simpler method. Still, not bad for a 65 year old on his third day of trying to understand graphs 🤣

[curryeater]

It would be great if you could include the time complexities in these videos.

[Dark.Ventur]

hi brother, i think if we count the number of node having same degree in one tree and if that count holds for other tree as well then we can say both tree are isomorphic .
eg :
T1 -> 0
| |
| |
4
|
|
2

T2 -> 5
|
|
3 4
|
|
0

so now if we se, in graph T1 -> there are three node having degree as(3) and two node having degree as (2) and one node having degree as(3) .

And if we see the same thing we will find in graph T2 -> there are three node having degree as(3) and two node having degree as (2) and one node having degree as(3) .

So with we can say both the graph are isomorphic, therefor this can be one of the method also right .

Please correct me if i going in wrong direction .

[kevinlu]

Thank you so much for your videos as they are very helpful. I was just wondering, if two trees are isomorphic shouldn't it be impossible for one to have one center but the other to have two? Thus, if one has two centers while the other has one, then shouldn't they immediately be not isomorphic? I suppose it should only matter if both have two centers.

[subhamkadam]

the leaf nodes won't get to the null case right, i mean the base condition of if node==null would be checked only if the whole tree is empty otherwise even if the current node is a leaf node, no further recursion will take place, simply it will have result as empty string. And won't go in for loop for further recursive calls as its children
array is empty

[scarface]

Sorting doesn't have to be lexicographic. Is it? Doesn't matter how you are sorting them as long as consistent

[davidkoci]

So, if I understand correctly, if the tree has more than 1 "center", then I can get multiple answers that won't be identical. Because in the example from 5:40 I can also choose vertex 1 as the root of the tree and then i´ve got not same answer as you have.

[dharavathsuresh]

The sorting of kunth tuples is based on the lable on node or layer if knuth tuples that are kept one inside from the previous children ?

[moritzgro]

So if graph-isomorphism is NP-hard is unknown, but tree-isomorphism is easy, as shown by the AHU algorithm, right?

[NevilleIsGod]

I could figure out the serializing algorithm from the brackets. Doesn't sound like a difficult algorithm for the likes of Ulam and co!

[utkarshtiwari]

Can someone tell me. If nodes are getting sorted in combining phase then at 7:27 while combining node 4 and node 5, why the code for node 5 is placed before node 4?

[anuragbansal]

Why won't the following approach work !? :

Count the number of nodes for a particular degree in both the trees. If the count are equal, then it is isomorphic else not.
If there is a mismatch in degrees, again the trees are not isomorphic.

I see it is working for some test cases but not for all. (Tried on SPOJ)

Is this incorrect approach ? Or I may have missed something in the implementation !?

[matheuscardoso]

could you point me to some resources on the probabilistic algorithms?

[laural]

Wait, is there meaning behind the tree encoding or is it randomized? I thought the left bracket meant a left edge and the equivalent for right ones, but it just doesn't seem to add up.
Regardless, thanks for the video!

[fayssalelansari]

but the tree should be sometimes mirrored before being checked for isomorphism

[kyleb]

When you say it's possible to reconstruct the tree from the encoding, do you mean exactly how it was before? or, just so that it is isomorphic-ally relative? If exactly, how could that be, if the encoding is to be the same for different tree's?

[yuwang]

Shouldn't the encoding of subtree rooted at #1 be (()(())) ? Okay, I see. So you are sorting the encoded strings from the children, not the integer label of the childs.

[Kaviyugamithran]

Say detialed about tree decompositions please