1
一个看上去简单实际上 OPEN 的图论题
source link: https://zhiqiang.org/math/a-open-graph-problem.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
一个看上去简单实际上 OPEN 的图论题
孙博告诉我的，求证
在任意简单有向图G(V,E)G(V,E) 中，存在一个顶点vv ，使得|N2(v)|≥2|N(v)||N2(v)|≥2|N(v)| ，其中N(v)={u∈V:(v,u)∈E}N(v)={u∈V:(v,u)∈E} , N2(v)={u∈V:(v,u)∈E∨∃w∈V,(v,w)∈E,(w,u)∈E}N2(v)={u∈V:(v,u)∈E∨∃w∈V,(v,w)∈E,(w,u)∈E} 。
通俗得讲就是在一个简单有向图中存在一个顶点，走至多两步能达到的顶点数至少为走一步能达到的顶点数的 2 倍。
注：简单有向图指任两点之间至多一条边。
看上去蛮简单的，事实上很不好做，是一个 OPEN 多年的问题...
Q. E. D.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK