数学吧 关注:940,572贴子:9,411,645
  • 0回复贴,共1

一道图论问题求助

只看楼主收藏回复

G=(V,E) 是无向连通简单图。取两个顶点s,t,使得这两点之间最短路径的长度大于|V|/2。(这可以说明,s t之间任两条路径必有公共点)求证:G中存在一个(不是s,t的)顶点v,使得去掉v和与其相连的边之后,s和t之间不连通。


IP属地:北京来自iPhone客户端1楼2021-07-29 18:18回复