In English: Hey guys, welcome to a new tutorial, this time we're talking about Prüfer sequences, specifically, how you go from a sequence to a tree, as well as get to a tree from a sequence. So this is an example that I've got: (5, 3, 5, 3, 5) And I'm gunna 'translate' this sequence into a tree. First step is to write down the vertices of the actual tree, (since there's 5 things in the Prüfer sequence, there'll be 5 + 2 = 7 vertices numbered from 1 to 7). Now I'll just mark the vertices that don't appear in the sequence.. 1,2,4,6,7. So then I CONNECT the first one in the sequence (5) with the minimum from the list of available vertices on top, then I'll mark that one, this time it's 1. So now vertices 1 and 5 are connected. Then I cross both 1 and 5 out. (from the top and the bottom list respectively). Now since the 5 appears again later in the sequence, I can't cross it out from the top. Then so I know 3 and 2 are connected (because 2 is the min from on top and 3 is the next number in the sequence) so I can cross both of those out. Now the three appears again later in the sequence (so I can't cross it out from the top)... Then 5 and 4, ... the 5 appears again later in the sequence, so now 3 and 6, I can cross both those out. So at this point I've already used the last three (3, 5, 5). (as in, (I think), they already appear in my drawing). So now 5 is the next number in the sequence and 3 is the minimum, so 3 and 5 are connected. Now there's two numbers left (5 and 7) so that means they are connected. That's the last step. So now we've drawn the tree. Now I'm gunna go from the tree to the sequence and this is relatively easy...
ok i now understand most of it..i just have one question ...Why did you add 6 and 7? why not just 6 im bad in german so i dont understand for exemple if code vas 7778 woud i type 12345 above or 123456?
The 6 and 7 are added because the prufer code can represent a tree on n nodes by a sequence of n-2 numbers. 7778 wouldn't exist as a prufer code, because it is only length 4 and so would represent a tree with 6 nodes. Modifying your code to be 777778, this tree would be on 8 nodes, and is actually a star with 7 as the internal node
In English:
Hey guys, welcome to a new tutorial, this time we're talking about Prüfer sequences, specifically, how you go from a sequence to a tree, as well as get to a tree from a sequence. So this is an example that I've got: (5, 3, 5, 3, 5) And I'm gunna 'translate' this sequence into a tree. First step is to write down the vertices of the actual tree, (since there's 5 things in the Prüfer sequence, there'll be 5 + 2 = 7 vertices numbered from 1 to 7). Now I'll just mark the vertices that don't appear in the sequence.. 1,2,4,6,7. So then I CONNECT the first one in the sequence (5) with the minimum from the list of available vertices on top, then I'll mark that one, this time it's 1. So now vertices 1 and 5 are connected. Then I cross both 1 and 5 out. (from the top and the bottom list respectively). Now since the 5 appears again later in the sequence, I can't cross it out from the top. Then so I know 3 and 2 are connected (because 2 is the min from on top and 3 is the next number in the sequence) so I can cross both of those out. Now the three appears again later in the sequence (so I can't cross it out from the top)... Then 5 and 4, ... the 5 appears again later in the sequence, so now 3 and 6, I can cross both those out. So at this point I've already used the last three (3, 5, 5). (as in, (I think), they already appear in my drawing). So now 5 is the next number in the sequence and 3 is the minimum, so 3 and 5 are connected. Now there's two numbers left (5 and 7) so that means they are connected. That's the last step. So now we've drawn the tree. Now I'm gunna go from the tree to the sequence and this is relatively easy...
This deserves upvotes
our hero our hero claims a warrior's heart
This is funny, don't know a word in German but I get it thank you very much :D
same here. more comprehensible then anything else on the internet. thanks
Didn't understand a single word except prufer, yet understood the procedure :) Thanks. But please next time made videos in English.
Szary Wilk yeah that could work too, but will take more time than learning prufer from books :)
Prufer code is 4541191 what will be it's tree structure
super video danke dir
cool :D
ok i now understand most of it..i just have one question ...Why did you add 6 and 7? why not just 6 im bad in german so i dont understand for exemple if code vas 7778 woud i type 12345 above or 123456?
The 6 and 7 are added because the prufer code can represent a tree on n nodes by a sequence of n-2 numbers. 7778 wouldn't exist as a prufer code, because it is only length 4 and so would represent a tree with 6 nodes. Modifying your code to be 777778, this tree would be on 8 nodes, and is actually a star with 7 as the internal node
i dont speak german either, but i could understand (im dutch), danke schön! :D
I don't speak German but it helped me anyways. Thanks!
Danke, you are great at this, thank you!
Explain me then please.
thank you :)
Yeah, habs verstanden! Danke dir!
Vielen Dank! Sehr hilfreich.
Danke my friends
Danke schön
danke schoen
Danke Schoen!!
Danke :D
türkçe anlarsanıza olum ta