
From:  Jon Wilson 
Subject:  Re: [wanted] automagic generation of graphs 
Date:  Tue, 24 Jul 2007 13:49:14 0400 
Useragent:  Thunderbird 1.5.0.12 (X11/20070604) 
Marco Maggi wrote:
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.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?
Are you trying to represent graphs or digraphs? I. you are representing graphsThe answer is no. (a (b c) c) contains a cycle abca, but does not contain an (a . body) with a in body form.
II. you are representing digraphsThe 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
[Prev in Thread]  Current Thread  [Next in Thread] 