[seqfan] Re: Enumerating DFS on multigraphs

[Li-yao Xia]

On 03/02/2017 11:51 AM, Antti Karttunen wrote:
> On Thu, Mar 2, 2017 at 3:54 PM, Li-yao Xia <lysxia at gmail.com> wrote:
>
>> Hello Antti,
>>
>> Thank you very much for your feedback, and the bijection! Indeed, this
>> is the behavior I had in mind. Some illustrations would be a good
>> idea, attached are crude ones in ASCII for n=1 to 3, where (tree- and
>> back-) edges around some vertices are explicitly numbered, indicating
>> the presence of back edges and to disambiguate the two subtle cases.
>>
> I guess you mean this same pair that I also meant:
>
>   o
>   |
> 1|
>   o
>   |\2
>   |/
>   *
>
>   o
>   |
> 2|
>   o
>   |\1
>   |/
>   *
>
>
> But I wonder, shouldn't those edges be labeled instead like this:
>
>   o
>   |
>   |
>   o
> 1|\2
>   |/
>   *
>
>   o
>   |
>   |
>   o
> 2|\1
>   |/
>   *
>
>
> ?
>
> Or am I missing some subtle point?

After re-reading your previous mail I can see where we are diverging.
The distinction to make in this example is not which of thetwo
edges incident to the root is the back edge, in fact in both cases
I mean the edge on the right to be the back edge. This is consistent
with this other case where I imagine the two back edges to be on the
right.

o
|\\
|//
*

With the numbers I am defining an order on edges going out of the
middle node, assuming that edges are directed as such: a tree edge
goes from the parent to the child, and a back edge from the
descendant to the ancestor. (I just realized this is actually not
equivalent to the description of multigraphs with permutations
I gave in my blog post.)

This structure captures different possible executions of a DFS:
for every node which is not the root, there is one edge from which
we arrive to it for the first time, this is the tree edge leading to
its parent, and then we need to choose an order in which to visit
the other incident edges. This does not quite correspond to an
arbitrary order on all edges, because some of them may be crossed
out as back edges in the meantime.

So in the above "subtle cases", you start in an unlabelled multigraph
from the root, go to the node in the middle by taking any of the two
initially undistinguishable edges (I admit that may sound a bit counter-
intuitive), then you are faced with two options, whether to take the
edge going up first, or the remaining edge coming back to the root.
The trees above characterize the two possibleoutcomes of this choice.

> I'll make nicer pictures later if I have the time. As you mention,
>> there are a couple of parameters to tweak and it would be interesting
>> to see what other sequences arise out of that.
>>
> In graph-wise context, I guess forgetting the relative position (or "side",
> in relation to "uplinks") at which of the back-links come back (towards the
> root) might make sense? In that case, the above two cases would collapse to
> just one, and the enumerating sequence would start as  1, 1, 3, 11, ...
> In wonder if that sequence is already in OEIS?
> http://oeis.org/search?q=1%2C+1%2C+3%2C+11&sort=&language=&go=Search
>
>
>> de Bruijn indices offer a mechanical way to encode back edges which
>> is convenient for implementation.
>
> Does the condition "*every vertex is a binder" *specify an interesting
> subset of all lambda-forms? What about the lambda-forms where not every
> vertex is a binder?
> Would that subset be e.g. closed regarding the application of its elements
> (lambda-forms) to each other? (Maybe I should re-read
> http://dkeenan.com/Lambda/ )

This is an odd question because for lambda terms, "binders", or
"abstractions", areunary ((\ x. T) binds a variable x to be used in
the inner term T, usage of this variablecorresponds to back edges),
and there is a separate branching construct (application (T U)),
and it is only binary.

Maybe there is a relation to beta-normal forms: they must be either
an abtraction \x. T with a body T also in normal form, or a variable
applied to zero or more terms in normal forms.

(((x T1) ...) Tn)

We can restrict this a bit more, requiring an alternation of abstractions
and applications, to get a structure isomorphic to trees with back edges.
We can define inductively a set I of terms that are either single
variables (corresponding to back edges)

x

or an abstraction over an application (corresponding to an n-ary vertex),
with terms T1 ... Tn also in I:

\ x. (((x T1) ...) Tn)

This construct is in fact a standard method (continuation passing style)
of encoding tuples (T1, ..., Tn) in lambda calculus, so from that
perspective it is no surprise that the set I represents trees of some kind.

Li-yao