# Bus route

koh zbi74583 at boat.zero.ad.jp
Sun Oct 7 08:14:42 CEST 2007

```    Max wrote :

> 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.
>

These sentences are difficult for me.
I would like you to draw the figures of constructions on a white board and explain them.

>>     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
>

Are you sure that your calculation is correct?

My early result S(3)=46 is not correct.
I re-counted it.

I list all partitions with their figures.

._._._.
|_|_|_|

._._._.
|_._|_| +   |            12
._. ._.      _
|_|_|_| +                8
._._._.
|_| ._| +   ._|          8
._._._.
|_._._| +   | |          4
._._.      _.
|_|_|   +  _|            12
._. ._.   ._.
|_._._| + | |            2
._._.     ._.
|_| |  + _._|            8
._._.            _.
|_._|  +  |  +   _|      4
._.       ._._.
|_|_   +    |_|          8
._.       _     ._.
|_|_   +     +  |_|      16
._.            _._.
|_|    +  _| +   _|      8
._.       _    ._.
|_|    +  _  + |_|       4
._.       _.    _.
|_|    +  _| +  _|       4

So, S(3)=98 .

Yasutoshi

```