图论3课件1.ppt

定义9.3.2 在图G = V, E中，vi, vj∈V。 如果从vi到vj存在通路，则称vi到vj是可达的，否则称vi到vj不可达。规定：任何结点到自己都是可达的。 如果vi到vj可达，则称长度最短的通路为从vi到vj的短程线(Geodesic)； 从vi到vj的短程线的长度称为从vi到vj的距离(Distance)，记为d(vi, vj)。如果vi到vj不可达，则通常记为d(vi, vj) = ∞。 定理9.3.2 在一个具有n个结点的图中，如果从结点vi到结点vj（vi≠vj）存在一条通路，则从vi到vj存在一条长度不大于n-1的通路。 几个结论 推论9.3.1 在一个具有n个结点的图中，如果从结点vi到结点vj（vi≠vj）存在一条通路，则从vi到vj存在一条长度不大于n-1的基本通路。 定理9.3.3 在一个具有n个结点的图中，如果存在经过结点vi回路，则存在一条经过vi的长度不大于n的回路。 推论9.3.2 在一个具有n个结点的图中，如果存在经过结点vi回路，则存在一条经过vi的长度不大于n的基本回路。 利用邻接矩阵判断可达 利用定理9.3.2和定理9.3.3，我们可以通过计算图的邻接矩阵及其幂的方法来判断从vi到vj是否可达，以及从vi到vj的距离。 定理9.3.4 设G = V, E为线图，V = {v1, v2, …, vn}，A = (aij)nxn为G的邻接矩阵，Am = ( )nxn，m=1, 2, …, n；Bn = ( )nxn = A+A2+A3+…+An。则有：如果 ＞0，那么从vi到vj可达，否则不可达；并且 例9.3.3 判断右图中图G中结点之间的可达关系，并求任两结点间的距离。 解 在图中，G的邻接矩阵及其2、3、4次幂分别为： 解(续) 从而有 定义9.3.3 设G = V, E是一个线图，其中V = {v1, v2, ..., vn}，并假定结点已经有了从v1到vn的次序，称n阶方阵P = (pij)nxn为图G的可达性矩阵(Accessibility Matrix)，其中 定理9.3.5 设G = V, E为线图，A、P分别是G的邻接矩阵和可达性矩阵，则有 例9.3.4 求右图中图G中的可达性矩阵。 例9.3.4(续1) 例9.3.4(续2) 于是该图的可达性矩阵为： 9.3.2 无向图的连通性 定义9.3.4 若无向图G中的任何两个结点都是可达的，则称G是连通图(Connected Graph)，否则称G是非连通图(Unconnected Graph)或分离图(Separated Graph)。 无向完全图Kn（n≥1）都是连通图，而多于一个结点的零图都是非连通图。 定理9.3.6 无向图G=V, E中结点之间的可达关系R定义如下： R={u, v|u, v∈V，u到v可达}， 则R是V上的等价关系。 分析 利用等价关系的定义，很容易证明R是自反、对称、传递的。 定义9.3.5 无向图G=V, E中结点之间的可达关系R的每个等价类导出的子图都称为G的一个连通分支(Connected Component)。用p(G)表示G中的连通分支个数。 显然，无向图G是连通图当且仅当p(G) = 1；每个结点和每条边都在且仅在一个连通分支中。 例9.3.5 判断下图中图G1和G2的连通性，并求其连通分支个数。 9.3.3 有向图的连通性 定义9.3.5 设G = V, E是一个有向图， 略去G中所有有向边的方向得无向图G’，如果无向图G’是连通图，则称有向图G是连通图或称为弱连通图(Weakly Connected Graph)。否则称G是非连通图； 若G中任何一对结点之间至少有一个结点到另一个结点是可达的，则称G是单向连通图(Unilaterally Connected Graph)； 若G中任何一对结点之间都是相互可达的，则称G是强连通图(Strongly Connected Graph)。 例9.3.6 判断下图中4个图的连通性。 定理9.3.7 有向图G是强连通图的充分必要条件是G中存在一条经过所有结点的回路。 定义9.3.6 在有向图G = V, E中，设G’是G的子图，如果 （1）G’是强连通的（单向连通的、弱连通的）； （2）对任意G“ G，若G’ G，则G不是强连通的（单向连通的、弱连通的）； 那么称G’为G的强连通分支（单向连通分支、弱连通分支）(Strongly/Unilaterally/weakly Connected Component)，或称为强分图（单向分图、弱分图）。 例9.3.7 求下面2个图的强、单向和弱连通分支。 解 在图G1中，由{v2}，{v6}和{v1, v3, v4, v5,