单行道

mathe

某个城市里面所有的道路正好形成了一个n*n的方阵. 这n*n的方阵中总共有n条东西方向的直线道路和n条南北方向的直线道路.

每条道路被分割成n-1段街道.所以总共有$2*n*(n-1)$段街道,而总共有$n^2$个路口(包括角落上4个只有链接两条街道的特殊路口) 现在由于车辆数目增加,政府部门决定将所有街道改成单行道(也就是汽车只能单向行驶) 但是在改变街道成为单行道以后,至少需要保证对于任意两个路口A和B,存在一条从A到B的行驶路线(同样也存在B到A的行驶路线) 请问,对于给定的n,政府部门可以选择的改变街道为单行道的方案有多少种? 比如n=2时只有两种

mathe

这个题目是我自编的,我也不知道答案是多少.而求出通项公式估计很难,所以我们的目的是对于各个不同的n,尽量用计算机求出给定n时的数目,看谁能够得到最大的n对应的结果

gxqcn

感觉每个路口都应保证有“入”和“出”的单向路即可。 但不知怎样建模型通过组合数学知识直接得通项公式。

无心人

你这是一笔画问题的变形阿 就是求你规定的图形的一笔画的解的数量吧 现在，反射和对称算不同么？

mathe

反射和对称算不同. 不同于一笔画问题,gxqcn的想法也不对

无心人

首尾相接的一笔画也不是么？

无心人

明白了 3 X 3 一个解看对不对 1 2 3 4 5 6 7 8 9 1 -> 4 -> 7 -> 8 -> 9 -> 6 -> 5 -> 2 -> 3 2 -> 1 3 -> 6 5 -> 4 8 -> 5 这个解如果对 那可以衍生出4组

无心人

等价于一笔画后 再进行其他点的连接 现在问题是 相同的一笔画的结构 其他点连接是否唯一？？

gxqcn

刚才确实欠考虑，现在构造一个我的说法的反例：

◇	→	◇	→	◇	→	◇
↑		↑		↑		↓
◇	←	◆	→	◆	→	◇
↑		↑		↓		↓
◇	←	◆	←	◆	→	◇
↑		↓		↓		↓
◇	←	◇	←	◇	←	◇

其中◇或◆表示路口，虽均有出入线路，但外环却无法进入到内环

mathe

关于gxqcn的想法,可以看下面的图:这个图中,所有点都有进入和出去的边,但是没有从右边到左边的路径. 其实这个问题用图论描述就是对这个无向图每条边定向,使得结果的有向图强连通.