[Tutorial] Tree Isomorphism

Правка en1, от 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,

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский Olympia 2022-03-18 19:31:26 5
en6 Английский Olympia 2022-03-18 19:30:49 0 (published)
en5 Английский Olympia 2022-03-18 19:30:35 4605 Tiny change: 'ring concactenation.' -> 'ring concatenation.'
en4 Английский Olympia 2022-03-18 19:08:23 403
en3 Английский 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 Английский 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 Английский Olympia 2022-03-18 17:54:29 495 Initial revision (saved to drafts)