Subject: Re: How to construct a tree from a given structure and elements

From: "Richard A. O'Keefe" <[email-masked]>
Date: Mon, 11 Dec 2000 14:53:42 +1300 (NZDT)

> (it is not a tree, because node3a appears twice in it),
	
	I can't agree, but please correct me if the definition of tree says
	that all nodes must have different names and tell me whats the right
	name for this kind of graph.
	
I am assuming here a one to one correspondence between nodes and node labels,
because Prolog has no other way to refer to a node.

    "Foundations of Computer Science"
    Alfred V. Aho & Jeffrey D. Ullman
    Computer Science Press, 1992.
[A *great* introduction to computer science.  Perhaps not the best idea
to introduce a Pascal book as Pascal's star was setting, but Pascal was
a great introductory language.]

    Chapter 5, "The Tree Data Model",
    section 5.2 "Basic Terminology", page 208.

	We can define a tree as a set of points called nodes
	and a set of lines called edges, where an edge connects
	two distinct nodes.  A tree has three properties:
	1.  One node is distinguished and called the root.
	2.  Every node c other than the root is connected by an
	    edge to some other node p called the parent of c.
        3.  A tree is connected in the secons that if we start at
	    any node other than the root, move to the parent of
	    n, to the parent of the parent of n, and so on, we
	    eventually reach the root of the tree.
	If p is the parent of ndoe c, we also say that c is a child
	of p.  A node may have zero or more children, but every node
	other than the root has exactly one parent.
--------------------------------^^^^^^^^^^^^^^^^^^

Related concepts:

    Directed graph (Digraph).
    Directed Acyclic graph (DAG).
    Forest (each node has no or one incoming edge, no cycles).
    Tree (only one node, the root, has no incoming edge).
    Binary tree.

The particular example appears to be a DAG.