强连通图与单向连通图的判定定理
定理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