强连通图与单向连通图的判定定理
定理14.8 设有向图D=,V={v1,v2,…,vn}。D是强连通图当且仅当D中存在经过每个顶点至少一次的回路。
证明 充分性显然。
下面证明必要性。
由D的强连通性可知,vi→vi+1,i=1,2,…,n-1。
设Гi为vi到vi+1的通路。
又因为vn→v1,设Гn为vn到v1的通路,则Г1,Г2,…,Гn-1,Гn所围成的回路经过D中每个顶点至少一次。
定理14.9 设D是n阶有向图,D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路。
证明 略。
问题 设有向图D是单向连通图,但不是强连通图,问在D中至少加几条边所得图D 就能成为强连通图?
2022-03-22 19:18:19
1.56MB
图的基本知识
1