一个看上去简单实际上 OPEN 的图论题

作者: , 共 414 字 , 共阅读 0

孙博告诉我的,求证

在任意简单有向图$ 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 多年的问题...

Q. E. D.

类似文章:
相似度: 0.122
今天香港中文大学的Prof. Cai给我们上 graph algorithm。第一节课上教我们玩魔方,先给每人发了一个。我喜欢这样的教学方法 :) 。
利用线性代数可以给某些问题很精妙的证明,Matrix67 就给出了一个这样的例子,这也让我想起以前看见的另外一个例子,分享如下:
注: 这个问题来自China Theory Week 2008的 Open Problems Session。
「杀人」,英文名为"Mafia Game",广泛流传于国内外。上个星期我们在玩的时候被Elchanan Mossel发现,然后他给了一个 talk ,内容就是杀人的理论分析。
后一篇:
很多人一看到 NP-hard ,就从字面上理解成为比 NP 还难的问题。但如果这里的「更难」指得是解决问题所花费时间更长的话,这个论断是不正确的。从算法角度来看, NP-hard 问题的确比 NP 难,但比 NP 还难(指花费时间更多)的问题却不见得是 NP-hard 的。