Determining if a directed graph is a rooted tree

[Tony Duran]

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?

[Seth Chandler]

The wonderful built-in package DiscreteMath`Combinatorica has a function
TreeQ that should give you the answer. You will have to represent your
directed graph in the way the package desires, but this is rather
straightforward.

Seth J. Chandler
Assoc. Prof.
University of Houston Law Center

"Tony Duran" <rad...@pop.uky.edu> wrote in message
news:9b8ogd$7...@smc.vnet.net...

[Matthias Hertel]

Tony,

In a tree, all nodes but the root have exactly one incident edge. (The
root has no incident edge.) This is a necessary condition for
tree-ness, but not sufficient. It's also met by a graph that contains
a tree and a few disconnected cycles. So we need to check if all nodes
are reachable from the supposed root node.

I use adjacency matrices as the representation: adj[[i, j]]==1 iff
there is an edge from node i to node j; otherwise it's 0.

The translation to Mathematica is quite straightforward:

children[n_?NumberQ, adj_?MatrixQ] := First /@ Position[adj[[n]], 1]

children[n : {_?NumberQ ..}, adj_?MatrixQ] :=
Join @@ (children[#, adj] & /@ n)

descendants[{}, _] := {}

descendants[n : {_?NumberQ ..}, adj_?MatrixQ] :=
Join[n, descendants[children[n, adj], adj]]

istree[adj_?MatrixQ] :=
Module[{n = Length[adj], in = Plus @@@ Transpose[adj]},
Count[in, 0] == 1 && Count[in, 1] == n - 1 &&
Length[descendants[First /@ Position[in, 0], adj]] == n]]]

Let's try it:

{ A->C, B->C } is not a tree, while { C->A, C->B } is:

In[12]:= g = {{0, 0, 1}, {0, 0, 1}, {0, 0, 0}};

In[13]:= istree[g]
Out[2]:= False

In[14]:= istree[Transpose[g]]
Out[14]= True

{ A->B, B->A, C } is one of the graphs that defeat the simple check
(counting incident edges):

In[22]:= g = {{0, 1, 0}, {1, 0, 0}, {0, 0, 0}};

In[23]:= Plus @@@ g
Out[23]= {1, 1, 0} (* looks good, but... *)

In[24]:= descendants[{3}, g]
Out[24]= {3} (* ...this does not. Therefore: *)

In[25]:= istree[g]
Out[25]= False

If you're going to use the descendants function somewhere else, take
care. If the part of the graph that it works on contains cycles, it
won't voluntarily stop recursing (that's why it's called last in the
istree function).

Regards,
Matthias

[Jacqueline Zizi]

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