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 🤣
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 3--------5 | | | | 1------ 4 | | 2 T2 -> 5 | | 3 -------- 4 | | 0 ---------1 --------2 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 .
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.
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
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.
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 !?
If the count of number of nodes of a particular degree is equal for two trees, it is not necessary for them to have the same structure. Consider the two cases below, I denote a node as "N", and an edge by "-" *Tree 1:* N - N - N - N - N | N 1 node degree 3, 2 nodes degree 2 and 3 nodes degree 1 *Tree 2:* N - N - N - N - N | N 1 node degree 3, 2 nodes degree 2 and 3 nodes degree 1 But they clearly don't have the same structure and hence are not isomorphic
Consider the following graphs which have the degree counts mentioned below but are not isomorhpic("x" denotes a node and the (n) beside it says that it has degree "n") 2 nodes of deg 3 1 node of deg 2 4 nodes of deg 1 (1) (1) x x \ / x(3) | x(2) | x(3) / \ x x (1) (1) (1) (1) x x \ / x(3) | (2)x---x | x(2) / x (1)
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?
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!
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?
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.
This is pretty brilliant and the applications must be extensive I can already see.
Your video is helpful and easier to follow. That's not an easy thing that other UA-camr can do
Lisp programmers: YES!!!!!!
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 🤣
It would be great if you could include the time complexities in these videos.
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 3--------5
| |
| |
1------ 4
|
|
2
T2 -> 5
|
|
3 -------- 4
|
|
0 ---------1 --------2
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 .
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.
Yes, you should be able to stop early if the number of centers differ.
Great question , I was also thinking the same
Sorting doesn't have to be lexicographic. Is it? Doesn't matter how you are sorting them as long as consistent
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
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.
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 ?
So if graph-isomorphism is NP-hard is unknown, but tree-isomorphism is easy, as shown by the AHU algorithm, right?
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 !?
If the count of number of nodes of a particular degree is equal for two trees, it is not necessary for them to have the same structure. Consider the two cases below, I denote a node as "N", and an edge by "-"
*Tree 1:*
N - N - N - N - N
|
N
1 node degree 3, 2 nodes degree 2 and 3 nodes degree 1
*Tree 2:*
N - N - N - N - N
|
N
1 node degree 3, 2 nodes degree 2 and 3 nodes degree 1
But they clearly don't have the same structure and hence are not isomorphic
Consider the following graphs which have the degree counts mentioned below but are not isomorhpic("x" denotes a node and the (n) beside it says that it has degree "n")
2 nodes of deg 3
1 node of deg 2
4 nodes of deg 1
(1) (1)
x x
\ /
x(3)
|
x(2)
|
x(3)
/ \
x x
(1) (1)
(1) (1)
x x
\ /
x(3)
|
(2)x---x
|
x(2)
/
x
(1)
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?
i had the same doubt
'(' comes before ')', hence '((' will be placed before '()'
What is the definition of sort here?
I could figure out the serializing algorithm from the brackets. Doesn't sound like a difficult algorithm for the likes of Ulam and co!
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!
Actually, lmao, turns out you explain the encoding in the video shortly thereafter. Thanks for the videos anyway!
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?
Isomorphic-ally relative. The new tree would likely have different labels.
could you point me to some resources on the probabilistic algorithms?
but the tree should be sometimes mirrored before being checked for isomorphism
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.
Exactly. I also had to stare at it for a while to convince myself that it was correct
for dumb-dumbs like me ()=01 {for simplicity =AB}
(()) =0011 {for simplicity =AABB}
when sorted the first will be AABB then AB {like a dictionary}
@@rahulmandre3895 this is helpful was confused on sort
@@WilliamFiset-videos would sorted labels of children work too ?
For practice : www.hackerrank.com/contests/hourrank-21/challenges/tree-isomorphism/problem
Say detialed about tree decompositions ........ please
detialed about tree decompositions
my pleasure