例
1是弱连通图；
2是单向连通图(当然它也是弱连通图)；
3是强连通图(当然它也是弱连通图、单向连通图)。
2013-7-22
图论
45
GGG定理
一个有向图G是强连通图当且仅当G中有一个回路，它至少包含每一个结点一次。
证明：“?”如G中有一个回路，它至少包含每个结点，则G中任何两个结点间都是相互可达的，故G为强连通图。
“?”如G是强连通图，则任意两个结点之间都是相互可达的，设G＝
2013-7-22
图论
46
弱分图、单向分图、强分图
设G＝
2013-7-22图论47
例
如上图(a)所示，有：
?由{v２}、{v６}、{v1,v３,v４,v５,v７}所导出的子图构成了该图的强分图；
?由{v1,v２,v３,v４,v５,v7}、{v1,v３,v４,v5,v６,v７}所导出的子图构成了该图的单向分图；?(a)图本身就是一个弱分图。
2013-7-22图论48