一道图论命题的猜想并进行证明

test4ever · 发表于 2010-1-20 21:32:45

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

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

×

这个命题是后边算法的基础,十分重要

对于一个圆盘图（Unit disk graph） G=(V,E), 总是存在两个节点 u, v ∈ V 对于任意节点 x ∈ V − {u, v}, Hopdist(x, u) ≤ d/2 or Hopdist(x, u) ≤ d/2 , hopdist(x,u)指两节点之间最远的跳跃数， d为图G的直径（任意两点间的最小跳跃数的最大值）

test4ever · 发表于 2010-1-20 21:33:47

厄，难道还有长度限制？
继续....
UDG的wiki解释http://en.wikipedia.org/wiki/Unit_disk_graph
简单的说 UDG所有节点必须可达，两点可达的条件是以节点为中心的圆相交

现用程序跑未发现反例，可是在数学证明上出了问题，尝试反正归纳都卡了壳，思路受阻，希望大家给些意见

test4ever · 发表于 2010-1-21 21:29:24

总是发帖成功并没有显示出来，很奇怪

test4ever · 发表于 2010-1-21 21:35:25

圆盘图就是所有点必须在规定的半径范围内可达，两点可达的条件是以节点为中心的圆相交
是wiki链接里面右边那个图

gxqcn · 发表于 2010-1-21 21:40:12

总是发帖成功并没有显示出来，很奇怪
test4ever 发表于 2010-1-21 21:29

注意到你已受该问题困扰了好几次，但先前没有接到他人类似的报告。

请把操作步骤描述具体点，以便分析原因。
比如是发主题帖不成功，还是回帖不成功？从哪里点击进来的，等等。。。

test4ever · 发表于 2010-1-24 18:35:13

短一点就可以，win7+firefox

test4ever · 发表于 2010-1-24 18:35:47

留言稍微长一些就不行了

gxqcn · 发表于 2010-1-25 09:08:03

论坛规定帖子字数的范围是：最小4字节，最大是20000字节。
一般来说，帖子一般是容易撞到下限（比如空贴），而很难撞到下限。

请问，你要发的帖子很长很长吗？超过一万个汉字？

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

[猜想] 一道图论命题的猜想并进行证明

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