一个图论题

zhiqiang十一月 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问题, 图论, 难题 »

魔方里的数学今天香港中文大学的Prof. Cai给我们上graph algorithm。第一节课上教我们玩魔方，先给每人发了一个。我喜欢这样的教学...

5条留言 -> 跳到留言表格

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]
At 2008.06.19 22:30, hcnw631 said:

如果走1步只能走1个顶点,那么走2步自然走了2个顶点,就是2倍.如果只走1步,就只能走1个顶点,不能是2倍.

[Reply]

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

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

一个图论题

阅微堂