求解建路图

冷眼看戏的Lili · 发表于 2008-7-13 06:28:37

好像不切合题意。

学生说的无解，倒是可以证明。

冷眼看戏的Lili · 发表于 2008-7-13 13:04:27

It's my pleasure to show the details. 但想先看看还有没有对所提问题给出“有解”结论的帖子。

冷眼看戏的Lili · 发表于 2008-7-13 21:06:00

要求是九条互不相交的路。你那些路实际是相交（部分重合）的。

如果允许相交或重合，还用得着动脑子吗？修一条干道从三所房子附近直通学校、邮局、医院附近，干道两头再修分叉通各处不就得了。

冷眼看戏的Lili · 发表于 2008-7-13 21:48:03

你画出图来让大家瞧瞧！“共用”不就是部分“重合”？它和“相交”有什么本质的区别？

冷眼看戏的Lili · 发表于 2008-7-13 22:23:22

用逐行打字母、恰当排列留空档的办法，可以大略显示平面几何图形。

冷眼看戏的Lili · 发表于 2008-7-14 06:58:01

俺老师说，上世纪六、七十年代，设计印刷电路版时就会遇到类似的问题。

冷眼看戏的Lili · 发表于 2008-7-14 09:23:45

在你的图中，从A到3的那条可以不通过C，直接从上绕过B往下就行。但是，从A到2就不得不通过C，这实际上就是与从C到1的路交叉了。无论如何，在二维空间（例如，平面、球面、抛物面）中，按题中要求连结ABC和123的9条曲线必有至少一个交叉点。如果画8条，倒是可以做到无交叉点的。

冷眼看戏的Lili · 发表于 2008-7-14 09:55:16

就沿用孜孜老兄的平面上任给的六点ABC与123。可以不妨假设，所用的任何连结两点的连线不通过任何第三点（否则，早就“交叉”了）。

（1）连结AB和12的四条不交曲线构成一个封闭图形，它把平面分为两个除了边界外的不交（无公共部分）区域。

（2）连结AB和123的六条不交曲线构成两个封闭图形，它把平面分为三个除了边界外的不交区域。123都在边界上，且每个区域的边界只含有123之中的两个点，另一个点必在此区域之外。

（3）无论C在哪个区域，从C到该区域外的点的连线必与边界交叉。

证毕。

注：俺没学过图论，证明中如有不对（不妥）的地方，请高人指正。

		自动登录	找回密码
密码			立即注册

动态微博