cfan2021 发表于 2024-4-14 16:23:06

单行道

某个城市里面所有的道路正好形成了一个n*n的方阵.
这n*n的方阵中总共有n条东西方向的直线道路和n条南北方向的直线道路.https://bbs.emath.ac.cn/static/image/common/jh.gif

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

ipeuric 发表于 2024-4-14 16:23:46

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

ivamvanibumiq 发表于 2024-4-14 16:24:42

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

oabipalehov 发表于 2024-4-14 16:25:05

https://bbs.emath.ac.cn/static/image/smiley/1/lol.gif

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

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

iciugun 发表于 2024-4-14 16:25:33

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

isebufusiza 发表于 2024-4-14 16:26:15

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

icakeekohude 发表于 2024-4-14 16:26:47

明白了

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 发表于 2024-4-14 16:26:53

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

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

其他点连接是否唯一？？

obibohazek 发表于 2024-4-14 16:27:35

刚才确实欠考虑，现在构造一个我的说法的反例：
◇→◇→◇→◇↑↑↑↓◇←◆→◆→◇↑↑↓↓◇←◆←◆→◇↑↓↓↓◇←◇←◇←◇

其中◇或◆表示路口，虽均有出入线路，但外环却无法进入到内环https://bbs.emath.ac.cn/static/image/smiley/1/sad.gif

epezzaqegazeu 发表于 2024-4-14 16:28:02

关于gxqcn的想法,可以看下面的图:这个图中,所有点都有进入和出去的边,但是没有从右边到左边的路径.
https://bbs.emath.ac.cn/data/attachment/forum/month_0806/20080616_12b3d607589db3c2e69bO3QZc4BWKIfb.gif

其实这个问题用图论描述就是对这个无向图每条边定向,使得结果的有向图强连通.
页: [1]
查看完整版本: 单行道