Math Is Fun Forum

dangermulan1988

Member

Registered: 2011-06-11

Posts: 18

question about graphs / undirected tree

please delete

Last edited by iwan_ccie (2011-07-11 01:39:35)

Bob

Administrator

Registered: 2010-06-20

Posts: 10,623

Re: question about graphs / undirected tree

hi iwan_ccie

I'd not met indegree and outdegree before so I had to look it up.

There's a good definition with diagram at

http://en.wikipedia.org/wiki/Indegree#I … _outdegree

so I recommend you start there.

Directed means the edges are made one-way by means of arrows.

So you have got to put on arrows, making just one vertex into the root (= source on Wiki).

10 would be correct of you ignored "non-isomorphic".

Two directed graphs will be isomorphic if one can be distorted into the other by rotating, reflecting etc. whilst keeping the number of vertices, edges and the placement of arrows constant (ie. topologically equivalent).

Hope that helps to get you started.    Post again if you need to and I'll spend longer on the answer.

Bob

Last edited by Bob (2011-06-11 23:28:41)

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

dangermulan1988

Member

Registered: 2011-06-11

Posts: 18

Re: question about graphs / undirected tree

Bob,

Thanks for looking into this ... are you saying that:
- if I want to assign a root I need to add arrows to the tree?

I still don't know how to find out what the answer is ... I am not really good at math ... so due to this question I had to dig allot and find out what everything means...
I know what a tree is and a graph, and in-degrees and out-degrees and a root, and what non-isomorphic is ...

And putting all this together should result that I can answer the question ... but I just can't.

The question is basically "How many non-isomorphic "rooted trees" can be created from this tree (undirected-tree) by choosing an appropriate root?"
And we need to come up with a NUMBER of trees ...

If I look at the definition of "rooted-tree" I see a few sample pics here --> http://mathworld.wolfram.com/RootedTree.html

So I still don't know how to determine this ...

Bob

Administrator

Registered: 2010-06-20

Posts: 10,623

Re: question about graphs / undirected tree

hi iwan_ccie

If I'm understanding this question correctly, you have to create all the trees you can like the one below.  (see diagram)

The left hand vertex is the root.

But don't count, for example, the mirror image of this one.

Looking at my diagram, it has just occured to me that you can create a new tree just by reversing one of the middle arrows, so the total may be a few more than I originally thought.

(But you cannot reverse any of the vertices with one edge or you have more than one root)

Bob

Last edited by Bob (2011-06-12 01:01:29)

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: question about graphs / undirected tree

Hi iwan_ccie,

I found some references:

http://www.math.northwestern.edu/~mlerm … ctrees.pdf

http://theory.cs.uvic.ca/inf/tree/PlaneRootedTree.html

The second link contains a formula, but no derivation.
I'll get back if I understand it further.

---

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."