1
Observe that we have lost an explicit representation of the left-to-right order of our nodes. This can be recovered in one of two ways: either from the tree addresses assigned to each node, or, if we have been careful about the order in which nodes are entered in the list, we can recover it from there as well. Otherwise, we must have one graph for the dominance relation and another for the precedence relation; i.e., a graph with one set of nodes, but two types of arc.
2
Well, actually it will work. Prolog does allow programs to modify themselves. But you're not supposed to know about that yet!
3
This is related to the fact that changing the order of records in the graph structure does not change which ``real'' graph it denotes. Put another way, the order in which nodes are visited in a recursion on the node list does not reflect any essential property of the graph that that list represents.
4
As a useful ``boundary case'' consider the graph with an empty arc-relation: no node is connected to any other! Or the other end of the scale, where every pair of nodes are symmetrically connected to each other, i.e., where the arc relation equals N× N. Here any node at all could serve as a root, and there are loops everywhere. We will need to handle both of these cases with one solution.
5
Note that if we make the selection of the starting node deterministic, say by always choosing the head of the current graph structure, then the sequence of starting nodes is now fully determined by any particular graph structure. Note further, however, that any given graph can be represented by several different graph structures, that is, lists of adjacency lists. For example, randomly permuting the list of adjacency records does not in any way affect which graph it represents.