文档介绍：§ 图的连通与割集
1、图的连通
图中路:一个点和边交替序列称为中由到的路,记为。若图是简单图时,路可以用点的序列。
简单路:边不重的路
初级路:点不重的路
回路:在G中,一条至少包含一条边并且的路
简单回路:边不重的回路
初级回路:点不重的回路
点i和j点是连通的:G中存在一条(i,j)路
G是连通的:G中任意两点都是连通的
连通分支T:G的极大连通子图 T(即在G中找不到真包含 T的连通子图)
寻找G的连通分支:从任一点i出发,寻找与i连通的所有点,构成集合N1,则G[N1]是G的一个连通分支。再在剩下的点中类似地寻找其它连通分支。
设G有p个连通分支,则G的邻接矩阵可以表示成分块矩阵
有向图中有向路:一个点和弧交替序列称为中由到的有向路,记为。若图是简单有向图时,路可以用点的序列。
简单有向路:弧不重的有向路
初级有向路:点不重的有向路
有向回路:在G中,一条至少包含一条边并且的路
简单有向回路:弧不重的有向回路
初级有向回路:点不重的有向回路
点i和点j是强连通的:G中存在一条(i,j)有向路,也存在一条(j,i)有向路

G是强连通的:G中任意两点都是强连通的
G的强连通分支:G的极大连通子图
寻找G的强连通分支:从任一点i出发,寻找与i强连通的所有点,构成集合N1,则G[N1]是G的一个强连通分支。再在剩下的点中类似地寻找其它强连通分支。
图G的割边:如果从G中删去它就使图的连通分支数严格增加的边

中边都是割边,而不是割边。
G的一条边是割边当且仅当这条边不包含在G的任何回路中。
边集合{S,T}