Bus route

[Max Alekseyev]

On 10/3/07, koh <zbi74583 at boat.zero.ad.jp> wrote:

>     Given an undirected graph G=(V,E), its partition into strokes is a collection of edge-disjoint paths (viewed as sets of edges) on V such that (i) union of any two paths is not a path; (ii)union of paths is E.

Construction of such a partition can be done as follows:

1) For every vertex v in the graph define a maximum matching on the
incident edges, maybe leaving one edge unmatched (if the degree d of v
is odd), and replace v and the incident edges with floor(d/2) copies
of v on connected pairs of matched edges and possibly one (if d is
odd) copy of v as an endpoint of the unmatched edge.

E.g., for vertex v with three incident edges A=(a,v), B=(b,v),
C=(c,v), a maximum matching {(A,B),C} will result in edges (a,v1),
(v1,b), (c,v2) where v1 and v2 are copies of v.

Note that there total number of maximum matchings for a vertex v of degree d is
d! / 2^floor(d/2) / floor(d/2)!

2) Described transformation results in a decomposition of the original
graph into paths and cycles where no two paths share an endpoint. For
every cycle we need to choose one vertex different from endpoints of
the paths and from vertices chosen in other cycles (here "different"
means that vertices are not copies of the same vertex from the
original graph), and cut the cycle at the chosen vertex into a
"circular" path (whose endpoints coincide with the chosen vertex).

As the result we will have a partition of the graph into undirected
strokes as defined above. Moreover, every such partition can be
obtained this way.

>     I wanted to know the numbers of "Bus routes" on n x n grid graphs.
>     ._._._._.
>     |_|_|_|_|    n=4
>     |_|_|_|_|
>     |_|_|_|_|
>     |_|_|_|_|
>
>     But it is too difficult to calculate by hand, so I count the case of 1 x n.
>     ._._._._.
>     |_|_|_|_|
>
>     S : 1,4,14,46
>     off set = 0

It seems that you lost a factor 2 for S(3). It should be S(3)=92.
I've got the following general formula:

For n>=2, S(n) = 3^(2*(n-1)) + 3^(n-1) + 2 + (3^n + 27 - 18*n)/4

S : 1, 4, 14, 92, 767, 6689, 59456, 532694, 4786769, 43058171,
387454898, 3486887696, 31381369571, 282430466453, 2541868618340

Regards,
Max