孙博告诉我的,求证
在任意简单有向图中,存在一个顶点,使得,其中, 。
通俗得讲就是在一个简单有向图中存在一个顶点,走至多两步能达到的顶点数至少为走一步能达到的顶点数的2倍。
注:简单有向图指任两点之间至多一条边。
看上去蛮简单的,事实上很不好做,是一个OPEN多年的问题...
孙博告诉我的,求证
在任意简单有向图中,存在一个顶点,使得,其中, 。
通俗得讲就是在一个简单有向图中存在一个顶点,走至多两步能达到的顶点数至少为走一步能达到的顶点数的2倍。
注:简单有向图指任两点之间至多一条边。
看上去蛮简单的,事实上很不好做,是一个OPEN多年的问题...