单行道
某个城市里面所有的道路正好形成了一个n*n的方阵.这n*n的方阵中总共有n条东西方向的直线道路和n条南北方向的直线道路.原创且有难度、有趣味的问题
每条道路被分割成n-1段街道.所以总共有$2*n*(n-1)$段街道,而总共有$n^2$个路口(包括角落上4个只有链接两条街道的特殊路口)
现在由于车辆数目增加,政府部门决定将所有街道改成单行道(也就是汽车只能单向行驶)
但是在改变街道成为单行道以后,至少需要保证对于任意两个路口A和B,存在一条从A到B的行驶路线(同样也存在B到A的行驶路线)
请问,对于给定的n,政府部门可以选择的改变街道为单行道的方案有多少种?
比如n=2时只有两种 这个题目是我自编的,我也不知道答案是多少.而求出通项公式估计很难,所以我们的目的是对于各个不同的n,尽量用计算机求出给定n时的数目,看谁能够得到最大的n对应的结果 感觉每个路口都应保证有“入”和“出”的单向路即可。
但不知怎样建模型通过组合数学知识直接得通项公式。 :lol
你这是一笔画问题的变形阿
就是求你规定的图形的一笔画的解的数量吧
现在，反射和对称算不同么？ 反射和对称算不同.
不同于一笔画问题,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的想法,可以看下面的图:这个图中,所有点都有进入和出去的边,但是没有从右边到左边的路径.
其实这个问题用图论描述就是对这个无向图每条边定向,使得结果的有向图强连通.