一个图论题

zhiqiangNovember 22, 2007 科学

孙博告诉我的，求证

在任意简单有向图 $G(V,E)$ 中，存在一个顶点 $v$ ，使得 $|N^2(v)|\geq 2|N(v)|$ ，其中 $N(v)=\{u\in V:(v,u)\in E\}$ , $N^2(v)=\{u\in V:(v,u)\in E \vee\exists w\in V, (v,w)\in E,(w,u)\in E\}$ 。

通俗得讲就是在一个简单有向图中存在一个顶点，走至多两步能达到的顶点数至少为走一步能达到的顶点数的2倍。

注：简单有向图指任两点之间至多一条边。

看上去蛮简单的，事实上很不好做，是一个OPEN多年的问题...

open问题 图论 难题

你可能感兴趣的

魔方里的数学

4条留言

At 2007.11.23 23:40, 漫步 said:

如果方便的话，请你参与我组织的博客串联活动怎么样，谢谢。详情见
http://roamlog.cn/archives/5-questions-about-you.html

[Reply]
At 2007.11.26 11:28, PSKing said:

这个题果然很复杂。。。。。
头疼ing。。。。

[Reply]
At 2007.11.29 18:41, 幼峰 said:

好像弄一个wp来，可是没有php的空间郁闷中我在自己的本机上已经用上wp了它的魅力实在太大了

[Reply]
At 2007.12.01 20:53, Chen Wang said:

怎么又把这么old的问题拿出来了……btw:最近有啥新问题写写吧

[Reply]

« 加速blog：选择合适的服务器

加速blog：网站响应缓慢的因素 »

一个图论题

open问题图论难题

4条留言

阅微堂