       Re: Determining if a directed graph is a rooted tree

• To: mathgroup at smc.vnet.net
• Subject: [mg28418] Re: Determining if a directed graph is a rooted tree
• From: Matthias Hertel <wir95cgu at studserv.uni-leipzig.de>
• Date: Mon, 16 Apr 2001 23:54:21 -0400 (EDT)
• References: <200104140528.BAA07447@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```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.

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] :=
Join @@ (children[#, adj] & /@ n)

descendants[{}, _] := {}

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

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:= g = {{0, 0, 1}, {0, 0, 1}, {0, 0, 0}};

In:= istree[g]
Out:= False

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

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

In:= g = {{0, 1, 0}, {1, 0, 0}, {0, 0, 0}};

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

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

In:= istree[g]
Out= 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

"Tony Duran" <radura0 at pop.uky.edu> writes:
> 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: Can Mathematica be used as expert system (rule-based computations like CLIPS?)
• Next by Date: circular plot question
• Previous by thread: Re: Determining if a directed graph is a rooted tree
• Next by thread: conditionals during nonlinear regression