MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Determining if a directed graph is a rooted tree


Please could you give some precisions about what definition you take for a
rooted tree.

For example:

1) given the graph of 5 vertices: A,B,C,D,E and the edges:
{A,B}, {C,B}, {C, D}, {E, C}
Do you consider that it is a rooted tree? And what is the root?


2) given the graph of 8 vertices A, B, C, D, E, F, G, H
and the edges:
{C,A}, {C,B}, {D, C}, {D, E},{E, D},{E,F}, {F,G}, {F, H}
Do you consider that it is a rooted tree? And what is the root?

3) given the graph of 7 vertices A, B, C, D,  F, G, H
and the edges:
{C,A}, {C,B}, {D, C}, {D, F}, {F,G}, {F, H}
Do you consider that it is a rooted tree? And what is the root?



a) how the fact that the graph is oriented interact with the concept of rooted
tree?
b) how do you choose the root?

Jacquelien Zizi

Tony Duran wrote:

> Dear MathGroup,
>
> I'm trying to find an algorithm that will determine if a directed graph is a
> rooted tree.  Does anybody have any ideas?



  • Prev by Date: Re: make directory command for W2K?
  • Next by Date: Re: matrix
  • Previous by thread: Re: Determining if a directed graph is a rooted tree
  • Next by thread: Re: Determining if a directed graph is a rooted tree