数学研发论坛

 找回密码
 欢迎注册
查看: 6244|回复: 45

[擂台] 单行道

[复制链接]
发表于 2008-6-16 10:25:45 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

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

每条道路被分割成n-1段街道.所以总共有$2*n*(n-1)$段街道,而总共有$n^2$个路口(包括角落上4个只有链接两条街道的特殊路口)
现在由于车辆数目增加,政府部门决定将所有街道改成单行道(也就是汽车只能单向行驶)
但是在改变街道成为单行道以后,至少需要保证对于任意两个路口A和B,存在一条从A到B的行驶路线(同样也存在B到A的行驶路线)
请问,对于给定的n,政府部门可以选择的改变街道为单行道的方案有多少种?
比如n=2时只有两种
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-16 10:28:37 | 显示全部楼层
这个题目是我自编的,我也不知道答案是多少.而求出通项公式估计很难,所以我们的目的是对于各个不同的n,尽量用计算机求出给定n时的数目,看谁能够得到最大的n对应的结果
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-16 10:43:08 | 显示全部楼层
感觉每个路口都应保证有“入”和“出”的单向路即可。
但不知怎样建模型通过组合数学知识直接得通项公式。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-16 11:09:22 | 显示全部楼层


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

现在,反射和对称算不同么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-16 11:13:14 | 显示全部楼层
反射和对称算不同.
不同于一笔画问题,gxqcn的想法也不对
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-16 11:18:23 | 显示全部楼层
首尾相接的一笔画也不是么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-16 11:23:59 | 显示全部楼层
明白了

  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组
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-16 11:25:32 | 显示全部楼层
等价于一笔画后
再进行其他点的连接

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

其他点连接是否唯一??
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-16 11:27:56 | 显示全部楼层
刚才确实欠考虑,现在构造一个我的说法的反例:

其中◇或◆表示路口,虽均有出入线路,但外环却无法进入到内环
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-16 11:30:07 | 显示全部楼层
关于gxqcn的想法,可以看下面的图:这个图中,所有点都有进入和出去的边,但是没有从右边到左边的路径.
g1.GIF

其实这个问题用图论描述就是对这个无向图每条边定向,使得结果的有向图强连通.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-12-16 01:46 , Processed in 0.068785 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表