图的连通性与矩阵表示.ppt

计算机数学 定义 在无向连通图G中： （1）如果去掉某一条边，图G将不连通，则称这条边为图G的割边或桥。 （2）与图G的任意一个割边相关联的结点称为图G的割点。 （3）若S为图G的至少含有一条边的子集，图G去掉S则不连通，而去掉S的任一真子集仍然连通，则称S为图G的割集。 例如下图中: (b,c)、(d,i)是割边，b、c、d、i是割点，{(b,c)} 、{(d,i)} 、{(a,b), (a,f)} 、{(a,f) , (b,f) , (f,g)}是割集，而{(a,b)}、{(a,b), (b,g)}不是割集。这里没有把割集和非割集全部列出。 2.有向图的邻接矩阵 与无向图一样， 有向图也能用相应的邻接矩阵表示. √ √ √ √ √ 判 断 题 对非连通图，可以把它分成几部分，使每一部分 都是连通的，且各部分之间无公共结点。这样分 成的每一部分成为该非连通图的连通分枝。 2、有向图的连通性 定义2 在一个有向图D中，若从顶点vi 到vj 存在通路,则称vi 可达vj 。 规定：vi 到自身总是可达的。 v1 v4 v3 v2 e1 e2 e3 e4 e5 e6 v1可达v2, v4不可达v1 若有向图D略去所有有向边的方向后所得的无向图是连通图，则称D是(弱)连通图。 特别地，若D中任意两顶点至少一个可达另一个， 则称D是单向连通图。 若D中任意两顶点都是相互可达的， 则称D是强连通图。 结论： 由定义可知，若图G是单向连通的，则必是弱连通的； 若图G是强连通的，则必是单向连通的，且也是弱连通的。 但反之不真。 定义 设无向图G =〈V,E〉的结点集为 边集为 则矩阵 称为G的邻接矩阵， 其中 图的矩阵表示 1.无向图的邻接矩阵 例2 写出下图所示无向图G的邻接矩阵A(G)： 如图7.3.1所示的图G， 求其邻接矩阵A 图7.3.1 G 但注意这里A 不一定是对称的。 定义 设有向图D=V,E, V={v1, v2, …, vn}, E={e1, e2, …, em}, 令 为顶点vi邻接到顶点vj边的条数，称( )m?n为D的邻接矩阵, 记作A(D), 简记为A. 3.无向图的关联矩阵 定义 设无向图G =〈V,E〉的结点集为 边集为 则矩阵 称为G的关联矩阵， 其中 例11 写出下图所示无向图G的关联矩阵M(G)： v4 v3 v2 e1 e2 e3 e4 e5 v1 设D = V, E，V ={v1, v2, …, vn}，E ={e1, e2, …, em}， 令 称M(D) = (mij)n?m为D的关联矩阵。 vi为ej的始点， vi与ej不关联， vi为ej的终点， 4、有向图的关联矩阵