单行道

cfan2021

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

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

ipeuric

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

ivamvanibumiq

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

oabipalehov

你这是一笔画问题的变形阿
就是求你规定的图形的一笔画的解的数量吧

现在，反射和对称算不同么？

iciugun

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

isebufusiza

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

icakeekohude

明白了

  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组

Dennislem

等价于一笔画后
再进行其他点的连接

现在问题是
相同的一笔画的结构

其他点连接是否唯一？？

obibohazek

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

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

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

epezzaqegazeu

关于gxqcn的想法,可以看下面的图:这个图中,所有点都有进入和出去的边,但是没有从右边到左边的路径.


其实这个问题用图论描述就是对这个无向图每条边定向,使得结果的有向图强连通.