离散数学讲义-图论

例

1是弱连通图；

2是单向连通图(当然它也是弱连通图)；

3是强连通图(当然它也是弱连通图、单向连通图)。

2013-7-22

图论

45

GGG定理

一个有向图G是强连通图当且仅当G中有一个回路，它至少包含每一个结点一次。

证明：“?”�犎鏕中有一个回路，它至少包含每个结点，则G中任何两个结点间都是相互可达的，故G为强连通图。

“?”�犎鏕是强连通图，则任意两个结点之间都是相互可达的，设G＝，V＝{v1,v２,v３,…,vｎ}，则v1到v2可达，v2到v3可达，v3到v4可达，……，vｎ-１到vｎ可达，vn到v1可达，由此可得到一条回路(v1，v２，v３，……，vｎ，v1)，它至少包含每个结点一次。■

2013-7-22

图论

46

弱分图、单向分图、强分图

设G＝是一个有向图，G1＝是G的子图，若G1是弱连通图(单向连通图，强连通图)，且没有包含G1的更大的子图是弱连通图(单向连通图，强连通图)，则称G1是极大弱连通子图(极大单向连通子图，极大强连通子图)或称为弱分图(单向分图，强分图)。

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