The Student Room Group
Uni students - Complete our survey >>
Uni students - Complete our survey >>
Uni students - Complete our survey >>

How many different trees can be drawn with 5 vertices and 4 arcs?

Hi, can someone please help me with this question? I'm kinda screwed since I'm not good at self study and I hate modelling with algorithms
Original post by lilnini252
Hi, can someone please help me with this question? I'm kinda screwed since I'm not good at self study and I hate modelling with algorithms


This should help:

http://www-math.mit.edu/~djk/18.310/18.310F04/counting_trees.html
Reply 2
Avatar for lilnini252
lilnini252
OP
6
Thank you, according to the website and other websites the answer should be 125, but apparently it's wrong...

Original post by RDKGames
Original post by lilnini252
Thank you, according to the website and other websites the answer should be 125, but apparently it's wrong...


If the vertices are labeled, then two trees on 3 vertices might be 1-2-3 and 1-3-2, and that's what they're doing.

But if you neglect the labelling of the vertices then they represent the same tree structure. x-x-x And in fact there is only one type of tree on 3 vertices.

So, if your question is for an unlabeled graph, then I suggest starting by considering the longest path.


How many trees have a longest path of length five? Then four? Etc.

There are only

Spoiler


Addendum: If you don't need to use all the vertices and arcs, then they may want you to include trees that can be drawn on just 4 vertices as well, and 3, and so on.
(edited 4 years ago)
Reply 4
Avatar for lilnini252
lilnini252
OP
6
Original post by ghostwalker
If the vertices are labeled, then two trees on 3 vertices might be 1-2-3 and 1-3-2, and that's what they're doing.

But if you neglect the labelling of the vertices then they represent the same tree structure. x-x-x And in fact there is only one type of tree on 3 vertices.

So, if your question is for an unlabeled graph, then I suggest starting by considering the longest path.


How many trees have a longest path of length five? Then four? Etc.

There are only

Spoiler


Addendum: If you don't need to use all the vertices and arcs, then they may want you to include trees that can be drawn on just 4 vertices as well, and 3, and so on.

ohh I see, thank you so much

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you