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

路与图的连通性、1

2

3

4

5

√√√√√判断题6

7

对非连通图，可以把它分成几局部，使每一局部都是连通的，且各局部之间无公共结点。这样分成的每一局部成为该非连通图的连通分枝。8

定义在无向连通图G中：〔1〕如果去掉某一条边，图G将不连通，那么称这条边为图G的割边或桥。〔2〕与图G的任意一个割边相关联的结点称为图G的割点。〔3〕假设S为图G的至少含有一条边的子集，图G去掉S那么不连通，而去掉S的任一真子集仍然连通，那么称S为图G的割集。9

例如以下图中:(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)}不是割集。这里没有把割集和非割集全部列出。10

2、有向图的连通性定义2在一个有向图D中，假设从顶点vi到vj存在通路,那么称vi可达vj。规定：vi到自身总是可达的。v1v4v3v2e1e2e3e4e5e6v1可达v2,v4不可达v111

假设有向图D略去所有有向边的方向后所得的无向图是连通图，那么称D是(弱)连通图。特别地，假设D中任意两顶点至少一个可达另一个，那么称D是单向连通图。假设D中任意两顶点都是相互可达的，那么称D是强连通图。结论：由定义可知，假设图G是单向连通的，那么必是弱连通的；假设图G是强连通的，那么必是单向连通的，且也是弱连通的。但反之不真。12

13

定义设无向图G=〈V,E〉的结点集为边集为那么矩阵称为G的邻接矩阵，其中图的矩阵表示1.无向图的邻接矩阵14

例2写出以下图所示无向图G的邻接矩阵A(G)：15

如下图的图G，求其邻接矩阵A图7.3.1G16

2.有向图的邻接矩阵与无向图一样，有向图也能用相应的邻接矩阵表示.但注意这里A不一定是对称的。定义设有向图D=V,E,V={v1,v2,…,vn},E={e1,e2,…,em},令为顶点vi邻接到顶点vj边的条数，称()m?n为D的邻接矩阵,记作A(D),简记为A.17

3.无向图的关联矩阵定义设无向图G=〈V,E〉的结点集为边集为那么矩阵称为G的关联矩阵，其中18

例11写出以下图所示无向图G的关联矩阵M(G)：19

v4v3v2e1e2e3e4e5v1设D=V,E，V={v1,v2,…,vn}，E={e1,e2,…,em}，令称M(D)=(mij)n?m为D的关联矩阵。vi为ej的始点，vi与ej不关联，vi为ej的终点，4、有向图的关联矩阵20

谢谢大家！21