Do you know what a graph isomorphism is ?
Here is an easy one to check your understanding:
How many non-isomorphic spanning trees does this graph have ?
Hi,
I am a little bit stuck in understanding this question ....
Can someone please help me with this and explain how I find the answer?
"In a directed graph every vertex has an "in-degree" and an "out-degree".
The "in-degree" is the number of heads of edges (arrows) adjacent to a vertex, and the "out-degree" is the number of tails of edges adjacent to a vertex.
A tree is called a "rooted tree" if one vertex has been designated the root, which by definition must have an in-degree of 0 and an out-degree of 1.
All the other vertices must have an in-degree of 1.
Below is given an undirected tree. How many non-isomorphic "rooted trees" can be created from this tree by choosing an appropriate root?"
I would say you can create "10" trees here ... because there are 10 points where you can create a root of.
I just don't get the "non-isomorphic "rooted trees" part here ... kind of confuses me ...
Or is the answer "5" because I can only pick the vertices that are on "on the "left sides" and the vertices that are starting from below?
Or is the answer "1" because there is no way you can redraw this tree in another way?
Or is the answer 106 ... that we need to try to create a tree and see how many combinations is possible with 10 vertices?
I am kind of confused here ...
Thanks,
isomorphism is that you can create a different shape of the graph by just only moving the vertices.
So you have 2 different shapes (graphs) for the eye ... but if you move the vertices around you can move back and forward between the 2 graphs:
example: with pictures I found here --> Graph isomorphism - Wikipedia, the free encyclopedia
And I have no clue what the answer is to your question ... maybe you can explain that ?
Can't you make each of the 14 vertices a root? Many of the resulting trees will be isomorphic, though.
You need to find the number of rooted trees such that there is no isomorphism between any pair of them. If you understand isomorphism, the question should be clear. I assume that we are considering unordered trees, i.e., one can change the order of children of any vertex without making it a different tree. This is important for seeing that the trees with the root in the leftmost vertex and in the topmost vertex are isomorphic.I just don't get the "non-isomorphic "rooted trees" part here ... kind of confuses me ...
I see 4 non-isomorphic trees rooted at the leftmost vertex, second left, central bottom and the one just above it, but this needs to be double-checked.