离散数学图论-通路与回路.ppt

通路与回路,离散数学,14.2 通路、回路1、通路 1）定义：给定有向图D中的任何一个边序列L，如果其中的任何一条边的终点，都是继之出现的边(如果存在的话)的始点，则称这样的边的序列是图G的通路。若序列中首尾结点相同，则称L为回路。2）定义：有向图D中，边序列中的各条边全都是互不相同的通路，称为简单通路。（无重复边）3）定义：有向图D中，序列中的每一个结点仅出现一次的通路，称为初级通路 若序列中首尾结点相同，则称通路为初级回路或圈。（无重复点）4）定义：序列中边的条数称为它的长度2、简单通路和初级通路的关系 有向图中的每一条初级通路，也都必定是简单通路。反之不成立 回路也可分为简单回路和初级回路。3、通路的表示：可仅用通路中的边序列表示：e1e2ek 也可仅用通路中所经过的结点的序列表示：v1v2v3vk,4、性质：1）定理 在n阶图D中，若从顶点vi到vj(vivj)存在通路，则从vi到vj存在长度小于或等于(n1)的通路 若大于n-1，则存在相同节点（有回路），将回路删去可得 2）在n阶图D中，若从顶点vi到vj存在通路，则vi到vj一定存在长度小于或等于n1的初级通路(路径)3）定理 在一个n阶图D中，若存在vi到自身的回路，则一定存在vi到自身长度小于或等于n的回路 4）在一个n阶图D中，若存在vi到自身的简单回路，则一定存在长度小于或等于n的初级回路 以上概念均可用在无向图G中14.3 图的连通性 一、无向图的连通性 1、结点的连通：设无向图G，u,v V，若u，v之间存在通路，则称u,v是连通的，记作u v，u V，规定uu 2、结点的连通关系是等价关系 若定义：u，vV且 u与v之间有通路 此关系是自反，对称的，传递的，因而是V上的等价关系,3、无向图的连通图 定义1413 若无向图G是平凡图或G中任何两个顶点都是连通的，则称G 为连通图，否则称G为非连通图或分离图4、结点之间的距离 1）定义：设u，v为无向图G中任意两个顶点 若u v，称u，v之间长度最短的通路为u，v之间的短程线 短程线的长度称为u，v之间的距离，记作 d(u，v)当u，v不连通时，规定d(u，v)2）无向图结点的距离有以下性质：1d(u，v)0，u=u时，等号成立 2具有对称性：d(u，v)d(v，u)3满足三角不等式：u,v，w V(G)，则 d(u，v)+d(v，w)d(u，w)二、有向图的连通性 1、结点的可达性 定义：设D为一个有向图 vi,vj V，若从vi到vj存在通路 则称vi可达vj,记作vi vj。规定vi总是可达自身的，即vi vi,2、结点的相互可达 若vi vj 且vj vi 则称vi与vj是相互可达的，记作:vi vj 规定vi vi 3、结点的可达关系为V上的二元关系，但不是等价关系（不满足对称性）。相互可达关系为V上的二元关系，且是V上的等价关系 有向图中顶点之间的可达关系既无对称性，也无反对称性4、有向图中结点的距离 定义：设D为有向图 vi,vj V，若 vi vj，称vi到vi长度最短的通路为vi到vj的短程线 短程线的长度为vi到vj的距离，记作d 注：该定义与无向图中顶点vi与vj之间的距离d(vi，vj)的区别：无对称性 一般地：d d（可能d 不存在）5、弱连通图、单向连通图和强连通图 定义1 设DV，E)为一个有向图 若D的作为无向图是连通图，则称D是弱连通图，简称为连通图 定义2 设DV，E)为一个有向图，若 vi,vj V,vi vj与vj vi至少成立其一，则称D是单向连通图 若 vi,vj V，均有vi vj，则称D是强连通图 注：三种图的关系：强连通图一定是单向连通图，反之不成立 单向连通图一定是弱连通图反之不成立,6、有关强连通图与单向连通图的判定（1）定理：设有向图D，Vv1，v2，vn D是强连通图当且仅当D中存在经过每个顶点至少一次的回路(2)定理 设D是n阶有向图 D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路,例2设有向图D是单向连通图，但不是强连通图，问在D中至少加几条边所得图D就能成为强连通图?作业：P292 16、17、18、39、40（1、2）、4314.4 图的矩阵表示一、图的矩阵表示 用矩阵表示图之前，必须将图的顶点或边标定成顺序，使其成为标定图1、无向图的关联矩阵1）定义1424 设无向图G，Vv1,v2,，vn。E=e1,e2,e3，em，令mij为顶点vi与边ej的关联次数，则称(mij)nxm为G的关联矩阵，记作 M(G)2）关联矩阵的性质:关联矩阵是n行（结点数）m列（边数）的矩阵,(1）M(G)每列元素之和均为2，这正说明每条边关联两个顶点(环所关联的两个端点重合)mij=2(j=1，2，m)(2）M(G)第i行元素之和为结点vi的度数，i1，2，n(3)所有行的和（即矩阵所有元素之和）等于边数的2倍（该例10边数5的2倍）。d(vi)mij=2 2m，这个结果正是握手定理的内容（即各顶点的度数之和等于边数的2倍）（4）第j列与第k列相同，当且仅当边ej与ek是平行边(5)某行i的和为0（即 mij=0）,当且仅当vi是孤立点2、有向图的关联矩阵定义：设有向图D中无环，Vv1，v2，vn。Eel，e2,，em，令 1 vi为边ej的起点 mij=0 vi为边ej不关联 1 vi为边ej的终点 则称(mij)nxm，为D的关联矩阵，记作M(D）,2)有向图关联矩阵的性质（1）mij=0，j1，2，m，从而mij=0，这说明M(D)中所有元素之和为0(2)M(D)中，负1的个数等于正1的个数，都等于边数m，这正是有向图握手定理的内容（入度之和等于出度之和）（3）第i行中，正1的个数等于d+(vi)（结点的入度），负1的个数等于d-(vi)（结点的出度）（4）平行边所对应的列相同3、有向图的邻接矩阵 1）定义：设有向图D，Vv1，v2，vn，Ee1，e2，em 令：aij为顶点vi邻接到顶点vj边的条数 称(aij)nxn为D的邻接矩阵，记作A(D)，或简记为A 2）邻接矩阵的性质（1）每列元素之和为结点的入度，即 aij d+(vi)，i1，2，n 所有列的和 aij d+(vi)m，等于边数 每行元素之和为结点的出度，所有行的和也等于边数（2）邻接矩阵中元素 aij 反映了有向图中结点vi到vj通路长度为1的条数,（3）A(D)中所有元素之和为D中长度为1的（边）通路总条数。主对角线的元素值为图中结点vi长度为1 的环的条数 利用A(D)确定出D中长度为L的通路数和回路数,就需要用到邻接矩阵的幂次运算（4）A2中的元素值bij是结点vi到vj长度为2 的通路条数：说明：由矩阵的乘积定义 bij=k aik*akj 由此可推断，A3矩阵中的Cij元素值，表示了从到长度恰为3的通路条数目（5）定理1411 设A为有向图D的邻接矩阵，Vv1，v2，vn 为D的顶点集，则A的L次幂AL(L1)中元素cij为D中vi到vj长度为L的通路数，其中cii为vi到自身长度为L的回路数 cij(所有元素之和)为D中长度为L的通路总数，其中 cii为D中长度为L的回路总数推论 设BLA+A2十+AL(L1)，则BL中元素 bij为D中长度小于或等于L的通路数，其中主对角线上元素值为D中长度小于或等于L的回路数,4、有向图的可达矩阵 1）定义：设D为有向图,Vv1，v2，vn 令 1 vi可达vi pij 0 否则 称(pij)nxn为D的可达矩阵，记作P(D)，简记为P 2）可达矩阵的性质（1）主对角线元素均为1（每个结点自身可达）（2）可通过图的邻接矩阵A的n-1次幂Bn-1得到（将其非零元素换为1，主对角线元素均设为1即可）,无向图G：V=v1，v2，v3 E=(v1,v2),(v1,v2),(v2,v2),(v2,v2),(v3,v2),(v3,v2),(v1,v3),有向图D：V=v1，v2，v3 E=,返回,返回,结点数相同边数相同结点的度相同但是两个图不同构,（b),(c)互为补图,自补图,返回,