考虑从左到右,从下到上编号1 -- N^2
则左向连接1 到 N
再对之间除了1外每个点向上 下向连接上面的点直到遇到平方数点
上向连接1 到 N(N-1) + 1
再对之间除了1外每个点向右 右向连接右面的点直到遇到平方数点
然后相邻点如果没连接,则进行从大编号到小编号的方向的连接
这么得到的一个图乃很有规律的图 另外,每个点和相邻点的连接必然存在出和入两个方向,不能都出,不能都入 所以N=3时,考虑四个角和中心点
则可能数量是2^4 * 4 * 3
而不是2^9
对大的N也能得到小的组合数
回复 23# 无心人 的帖子
呵呵, 无心人又开始争论了:)在n较大时,那些边边角角的限制产生的影响就很小了。
主要的剪枝手段是除去各种对称变换下的同构。但是这个问题中比较明显的变幻好像只是转置,除数太小
另一个重要特征是顶点度小于等于4,但还不知如何利用 考虑f(N)为组合数
n = N
$f(N) < 2^4 * 2^{4(N-3)} * 2^{4(N-2)} * f(N-2)$ 大家可以同走格子线路统计问题比较一下看看,是否可以有类似的方法 现在提法有边缘“路口”的问题。试着改进一下,也不知是好是坏?
假设四周路口新增“南北或北南”、“东西或西东”2n 条直达单向隧道,
(本想说“空中航线”的,但单向规定不合理)
即:有 n xx n 个路口,之间有 2n^2 条网状单行道联通,
要求从任意路口间至少存在一条路线到达另一个任意路口。请问共有多少种方案?
如果是 m xx n 个路口呢?(将有 2 m n 条单行道)
新的提法,将使每个“路口”均正好与另外四个路口有联系而成为“相邻路口”。
再说明一下,这是我瞎编胡造的,只是出于对数学美的追求而已。 添加了以后,所有"路口"就都是十字路口了,比较美观一些:)
不过四面添加的4n条单向隧道定向对内部没有影响,它们的定向还是不要计算在里面. 弄明白了,gxqcn想要添加的是直接沟通东西和南北的2n条互不交叉的高架或地下隧道.
这样处理以后任何方向道路变成环路,这个就是另外一个比较有趣的题目了 我不知道改编后,难度是提升了还是下降了,
只是感到比较有趣。:)