[Tutorial] Tree Isomorphism

Revision en2, by Olympia, 2022-03-18 18:55:22

I have no school right now, and there's no tutorials on Tree Isomorphism on Codeforces, so I decided to write one :).

What is a tree isomorphism?

Maybe you recognize the word isomorphic: in the context of abstract algebra when two objects are effectively the same, but are labelled differently. We can extend this to trees as well: two trees are isomorphic if they are the same, but may have different node labels. For example,

 are isomorphic because we can relabel the nodes. If you want a more rigorous definition, then two trees $$$T_1 = (V_1, E_1)$$$ and $$$T_2 = (V_2, E_2)$$$ are isomorphic iff there exists a $$$\phi$$$ for which $$$\phi(E_1) = E_2$$$ and a $$$\phi^{-1}$$$ for which $$$\phi^{-1} (E_2) = E_1$$$.

Does a tree being unrooted really matter?

No, not in the meaningful sense. We can transform our original problem of checking if two trees are isomorphic into checking if two rooted trees are isomorphic easily. How? We can find the centroids of our first tree and our centroids of our second tree, and then root them at their centroids. So now, we have transformed our unrooted case into a rooted case.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English Olympia 2022-03-18 19:31:26 5
en6 English Olympia 2022-03-18 19:30:49 0 (published)
en5 English Olympia 2022-03-18 19:30:35 4605 Tiny change: 'ring concactenation.' -> 'ring concatenation.'
en4 English Olympia 2022-03-18 19:08:23 403
en3 English Olympia 2022-03-18 19:06:12 1187 Tiny change: 'rees?_\n\nNo, not in the meaningful sense. We can t' -> 'rees?_\n\nYes. We can t'
en2 English Olympia 2022-03-18 18:55:22 731 Tiny change: '39-AM.png)' -> '39-AM.png)\nare isomorphic because we can relabel the nodes.'
en1 English Olympia 2022-03-18 17:54:29 495 Initial revision (saved to drafts)