[Tutorial] Tree Isomorphism

Revision en1, by Olympia, 2022-03-18 17:54:29

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,

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)