Re: [wanted] automagic generation of graphs

[Jon Wilson]

Marco Maggi wrote:
> Thanks to all. Am I correct in saying that with a form like:
>
>   (a . body)
>
> if the symbol 'a' appears in 'body' the graph is cyclic,
> while if the symbol does not appear in its own body the
> graph is Acyclic?
Well, it is immediately obvious that any graph (or digraph) which has 
such a form has a cycle.  So if a graph is acyclic, then no such form 
appears.  But you also want the converse or its contrapositive: if no 
such form appears, then the graph is acyclic; if a graph is cyclic, then 
such a form appears.

Are you trying to represent graphs or digraphs?


I. you are representing graphs

The answer is no.  (a (b c) c) contains a cycle a-b-c-a, but does not 
contain an (a . body) with a in body form.


II. you are representing digraphs

The answer is provisionally no.  (a (b c) (c b)) contains a cycle 
b->c->b, but no form (a . body) with a in body.  However, this graph 
could also be represented as (a (b (c b)) c), which does contain such a 
form.  Notice that in this latter representation, the first time a node 
appears, its edge list is given.

So, if we do not require the edge list to be given at the first 
appearance of a node, the answer is definitely no.  OTOH, if we do make 
such a requirement, the answer seems to be yes, but I have not proven 
this to be so.

Regards,
Jon