Bus route
koh
zbi74583 at boat.zero.ad.jp
Thu Oct 4 03:19:36 CEST 2007
Hello Seqfans.
I considered about "Bus route problem".
If we made bus routes on a graph G, the roots should satisfy the following conditions.
1. One and only one route exists on all edges of G
2. Terminals of two different routes don't meet on the same point
This definition is equivalence with "Partition of graph G into strokes" without direction.
It is defined as follows.
Given an undirected graph G=(V,E), its partition into strokes is a collection of directed edge-disjoint paths (viewed as sets of directed edges) on V such that (i) union of any two paths is not a path; (ii)union of corresponding undirected paths is E.
So, the case of undirected paths is the following.
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.
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
I wonder if no mathematician have thought this problem.
Yasutoshi
More information about the SeqFan
mailing list