这个命题成立吗？

nnd · 发表于 2012-7-23 13:13:03

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

您需要登录才可以下载或查看，没有账号？欢迎注册

×

平面上的图，如果每条边（a）和其他任一条边最多有一个公共点，而且公共点必为（a）的顶点，则称这个图为不交图。平面上的不交图，满足以下条件，则称之为归一化半圆不交图： 1.它的顶点都在某条射线上，依照射线的方向依次排列为A1，A2，...，Ai 2.Aj到Aj+1（1<=j<=i-1）的距离为1 3.所有的边都是以顶点为直径的半圆那么，对所有的不交图，都有归一化半圆不交图跟它同构。因为不懂图论，所以不知道图论里是否有不交图的概念，索性自己搞一个。

hujunhua · 发表于 2012-7-23 15:00:38

就是无二重边的可平面图。多看看书，就会少辄下定义。命题是成立的，但是这样把顶点拉到一条线上有什么用呢？

nnd · 发表于 2012-7-23 19:26:41

对我这种还不习惯用图论的思维方式来考虑问题的人来说，这种图简单，少费很多脑细胞。怎么证明呢？不过估计你写出来了我也看不懂。呵呵。

hujunhua · 发表于 2012-7-24 11:56:22

证明路线： 1、将图极大化。如果极大图可，则原图可。 2、如果存在哈密顿回路，可。（顶点在射线上的位置按哈密顿通路的顺序排列） 3、惠特尼定理：极大平面图存在哈密顿回路。

账号		自动登录	找回密码
密码			欢迎注册

[原创] 这个命题成立吗？

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