企源知识库

一个有向图G是强连通的,当且仅当G中含有一个包含所有顶点的回路。
【正确答案】：证明:充分性  G中含有一个包含所有顶点的回路P。
 ∀u,v∈G,u,v∈p,u到v及v到u之间有路存在。故G是强连通的。
 必要性  G是有向强连通图,∀u,v∈G,u到v之间有路P₁存在,而v到u之间有路P₂存在。设P=P₁+P₂,则p是一个回路。
 若p中已包含G中的全部顶点,则结论成立,否则若存在顶点w∈G,但w ∉p寻找p中任一点x,则w,x之间及x,w之间必有路,将这两段路加入p中,得到P₁。依此类推,将G中不属于回路的顶点依次加入进来,直到回路中包含所有顶点为止。