求解建路图

常来 · 发表于 2008-7-12 10:18:34

三座房子在场地的一边,要求各建三条路到场地另一边的学校,邮局,医院.这九条路不能交叉,谁能解出来,谢谢

色盲 · 发表于 2008-7-15 20:01:03

谢谢两位指点

www.ddhw.org---

据说这世界是彩色的？

idiot94 · 发表于 2008-7-14 19:57:45

图论中有如下基本结论：

（定义：平面图是指一个可以在平面上“实现”的图，也就是说：所有的顶点和边都在同一个平面上，而且任何两条边除了在顶点处，互不相交。不能在平面上实现的图就叫做非平面图。）

任何一个非平面图，都存在一个子图（就是从整个图中切下来个某个部分），要么和三阶完全偶图同构，要么和五阶完全图同构。

楼主的题目其实就是要证明三阶完全偶图不能在平面上实现。

一般图论中标准的证明都是通过那个著名的欧拉定理来证的，我们在中学立体几何里面学习过这个定理：三维空间中的简单多面体，如果记其面数为S, 边数为E, 顶点数为V, 那么 S+V-E=2.

当时这个定理的证明就是把多面体展平成为一个平面图来做的，简单而有趣（大家不妨试着回忆一下。。）。

如果使用这个定理，在结合您的思路，就很容易写出一个简单明了的证明了。：）

哦，另外，图论中还有一个定理，就是说，任何一个图，都可以在三维空间中实现。

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

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

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

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

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

证毕。

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

孜孜不倦@. · 发表于 2008-7-14 09:30:55

但如果是电线的话，hmmm，可以从房子底下通过，或者电路板，电路很薄，也是可以压在C以下。。。呵呵，要是严格说的话当然不行了，只博大家一乐罢了。

www.ddhw.org---

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

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

呵呵呵呵 · 发表于 2008-7-14 09:19:29

这是不可能的.这个图形在图论中称为kuratowski图，是不可平面化的。

孜孜不倦@. · 发表于 2008-7-14 09:05:35

www.ddhw.org---

孜孜不倦@. · 发表于 2008-7-14 08:54:26

1提醒，偶也想起来了

www.ddhw.org---

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

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

常来 · 发表于 2008-7-14 06:50:26

要是建路太大工程,那就换牵九条平面不相交的电线好了,我在初中的时候好像见过这题,应该有解

开开心心 · 发表于 2008-7-14 02:40:45

在roundabout內行车，沒人会说在那条路上，只会说第一个exit去第一间屋.......第六个exit去医院去，分得清楚，是沒有交叉的

至於增加成本做九条路解决问题方法由你继续想好啦

色盲 · 发表于 2008-7-14 01:51:52

车辆从不同路径走到roundabout然后离开，走的轨迹有交叉。这就算路交叉了。另外，人家要求建9条路呀。

www.ddhw.org---

据说这世界是彩色的？

开开心心 · 发表于 2008-7-13 23:47:36

我这个玩法只是回应色盲MM一条路思维而已，那动画图並不是用来回答楼主问题[:-M]

本贴由[开开心心]最后编辑于：2008-7-13 16:36:9

东北逍遥客 · 发表于 2008-7-13 23:32:01

玩小聪明投机取巧不可取

开开心心 · 发表于 2008-7-13 23:04:45

所有路都是独立，路之间並沒有交叉，车轮是要先离开一条路才可以进入另一条路，同一车轮亦不能同时佔用两条路面，说重合亦不对。

就是沒必要多建路这么笨吧。

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

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

开开心心 · 发表于 2008-7-13 22:06:10

问题是roundabout不是路，亦不属於任何一条路，车轮在roundabout內行驶，完全乎合问题要求，6条路都沒有相交点，全不需要经过其它路就能直接进入roundabout，只是要经过那个 roundabout自由出入去目的地去而已

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

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

开开心心 · 发表于 2008-7-13 21:20:37

crossing才算双交，roundabout是不属于任何一条路的，原理只有共用，並沒有相交

还有，6条路不但沒有相交也沒有重合呢，我看你不明白什么是roundabout吧

本贴由[开开心心]最后编辑于：2008-7-13 13:30:36

本贴由[开开心心]最后编辑于：2008-7-13 13:39:34

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

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

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

salmonfish · 发表于 2008-7-13 20:52:45

草图中糊里糊涂的还是走了"立交".我错了.

但是,如果允许在某一点,就说医院吧,有四条路径通过(三条进,一条出.原题对此无限制),则此题解.

开开心心 · 发表于 2008-7-13 19:38:22

三间屋、学校,邮局,医院各有双程路连入roundabout，由roundabout再转去那个目的地也行，总共六条双程路就可以。

色盲 · 发表于 2008-7-13 19:26:58

那是一条路还是9条路啊

www.ddhw.org---

据说这世界是彩色的？

开开心心 · 发表于 2008-7-13 18:14:30

开心

开开心心 · 发表于 2008-7-13 18:13:20

用一个大roundabout连接三间屋、学校,邮局,医院就可以啦.

色盲 · 发表于 2008-7-13 16:53:29

开心你偷换命题

www.ddhw.org---

据说这世界是彩色的？

开开心心 · 发表于 2008-7-13 15:00:03

一般性发觉地型限制后，只想着早些能吃喝玩乐去，

面子工程就会出现大堆立交桥、隧道等，成本大增，自鸣得意，只当市民全是白痴

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

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

色盲 · 发表于 2008-7-13 10:42:37

光设计费就省不少呢

www.ddhw.org---

据说这世界是彩色的？

色盲 · 发表于 2008-7-13 10:39:04

我想这个证明应该很有趣

www.ddhw.org---

据说这世界是彩色的？

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

好像不切合题意。

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

开开心心 · 发表于 2008-7-13 00:05:48

抱歉，沒办法从文字中看到可行

salmonfish · 发表于 2008-7-12 23:27:15

one, or more, road coming out from house A first goes around house B, or C, and then connects to the hospital, etc.

(can't draw it due to no graph software on hand, sorry)

开开心心 · 发表于 2008-7-12 20:32:30

一条路成本不少，天马行空，现实生活实践难，笨蛋方法不作考虑

色盲 · 发表于 2008-7-12 19:59:13

要是我就只建一条路

本贴由[色盲]最后编辑于：2008-7-12 12:3:15

www.ddhw.org---

据说这世界是彩色的？

开开心心 · 发表于 2008-7-12 19:19:43

要三间屋都可以平面不交叉互通学校,邮局,医院，英国人是不会这么笨建9条路

学生 · 发表于 2008-7-12 19:07:57

I see.

Answer: No solution.

常来 · 发表于 2008-7-12 18:24:11

回复：路也可建在场地外面

常来 · 发表于 2008-7-12 18:22:40

路可建在场地外面

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

动态微博

求解建路图

谢谢两位指点[:)][>:D<]

您的思路基本正确。很好呀！ ：）

证明“无解”

[:-M][:-M]

回复：谢谢常来，lili的提示，不知道这样是否可行还是违反了规则（图）

回复：求解建路图

谢谢常来，lili的提示，不知道这样是否可行还是违反了规则（图）

[:-Q][:-Q][:-Q]

回复：换个题意

换个题意

只是回应你的一条路方法而已[;)]

开心来看

先由头到尾看帖子再批评吧[;)]

所有题目都要按你这种想法，就别出题了，学微积分的时候为啥老师不让用画图计算器做呢？

找来一个roundabout动画图，让你理解roundabout是怎样运作[:-D]（图）

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

抱歉，我沒有画图软件[:-D]

回复：不要自以为聪明[:-T]

不要自以为聪明[:-T]

苯小子，不要看不起丫头！[:X]

我错了.[:-D][:>][:P][:((]

笨丫头，入来看帖[:-M]

那是一条路还是9条路啊[:-D]

开心[:-M]

用一个大roundabout连接三间屋、学校,邮局,医院就可以啦.[;)]

开心你偷换命题[:-K][:-K]

我看未必[:-M]

回复：愿闻其详[:)]

那也比搞九条路便宜[:-M][:-M]

愿闻其详[:)]

俺也看不懂

抱歉，沒办法从文字中看到可行[;)]

可解.

一条路成本不少，天马行空，现实生活实践难，笨蛋方法不作考虑[:-M]

要是我就只建一条路[:-M]

要三间屋都可以平面不交叉互通学校,邮局,医院，英国人是不会这么笨建9条路[:-M]

回复：回复：路也可建在场地外面

回复：路也可建在场地外面

回复：求解建路图

您的思路基本正确。很好呀！：）