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

作者: , 共 315 字

孙博告诉我的,求证

在任意简单有向图 \( 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.131
今天香港中文大学的 Prof. Cai 给我们上 graph algorithm。第一节课上教我们玩魔方,先给每人发了一个。我喜欢这样的教学方法 :) 。
利用线性代数可以给某些问题很精妙的证明, Matrix67 就给出了一个这样的例子 ,这也让我想起以前看见的另外一个例子,分享如下:
注 : 这个问题来自 China Theory Week 2008 的 Open Problems Session。
相似度: 0.050
这个题目听说是 MSRA 的面试题。
在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛。规则呢,是这样。我们有 n 个人,作为一个小组来参加游戏。游戏中,主持人会给我们每人头上戴一顶帽子。帽子有黑白两种颜色,可以认为它们在我们各自头上的分布是临时随机决定的。小组中的每一个人,可以看到其他人的帽子颜色,但不知道自己的帽子颜色。每个游戏成员都被要求回答自己帽子的颜色。我们各人面前有三个按钮,可以选择「黑色」「白色」或「弃权」( 也就是 pass ,不作猜测的意思 )。小组成员彼此之间没有任何信息交流,他们必须各自独立地作出自己的选择,并且谁也不知道其他人的选择。如果小组成员全部选择了 pass ,也就是每个人都弃权,则他们输了;如果有小组成员作出了明确的猜测,但某个人猜错了,则结果也是输。只有当小组中有人做出猜测,并且每个做出猜测的人都猜对了,他们才能获胜,一起获得最后的大奖。
「杀人」,英文名为 "Mafia Game",广泛流传于国内外。上个星期我们在玩的时候被 Elchanan Mossel 发现,然后他给了一个 talk ,内容就是杀人的理论分析。
后一篇:
很多人一看到 NP-hard ,就从字面上理解成为比 NP 还难的问题。但如果这里的「更难」指得是解决问题所花费时间更长的话,这个论断是不正确的。从算法角度来看, NP-hard 问题的确比 NP 难,但比 NP 还难(指花费时间更多)的问题却不见得是 NP-hard 的。