第9章图论 9.2路和回路 定义9.2.1设G=<V,E>是图，G中的结点与边的交替序列L: oeye22…e,叫做到yn的路。其中y1与y,是e,的端点 , l,…,n。v和yn分别叫做路L的始点和终点。路L中边的条数 叫做该路的长度。 例如，在图9.11中， L1:Vsesv4e2e6V5e7y3是从y到y的路，y是始点， y是终点，长度为4。 L2:ve vze3v3 是从y到y的路，y是始点， v,是终点，长度为2。 在简单图中没有平行边和环，路L:oe11e22℃ny,完全 由它的结点序列y2…v确定。所以，在简单图中的路可以 用结点序列表示
第9章 图论 9.2 路和回路 定义9.2.1 设G=V,E是图，G中的结点与边的交替序列L： v0 e1 v1 e2 v2…en vn叫做v0到vn的路。其中vi-1与vi是ei的端点， i=1,…,n。v0和vn分别叫做路L的始点和终点。路L中边的条数 叫做该路的长度。 例如，在图9.11中， L1：v5 e8 v4 e5 v2 e6 v5 e7 v3 是从v5到v3的路，v5是始点， v3是终点，长度为4。 L2：v1 e1 v2 e3 v3 是从v1到v3的路，v1是始点， v3是终点，长度为2。 在简单图中没有平行边和环，路L：v0 e1 v1 e2 v2…en vn完全 由它的结点序列v0 v1 v2… vn确定。所以，在简单图中的路可以 用结点序列表示
第9章图论 定义9.2.2设G=<V,E>是图，L是 从v到yn的路。若y。=yn,则称L为回路。 若L中所有边各异，则称L为简单路。 e 若此时又有v。=yn,则称L为简单回路。 e3 若L中所有结点各异，则称L为基本路。 V3 若此时又有y。=yn,则称L为基本回路。 es 若L既是简单路，又是基本路，则称L es e6 为初级路。若此时又有v。=vn’ 则称L为 e7 初级回路。 在图9.11中，L是一条简单路。L2 es 是一条简单路、基本路、初级路。。 图9.11
第 9 章 图论 定义9.2.2 设 G = V, E 是图， L 是 从 v 0 到 v n的路。若 v 0 = v n，则称 L为回路。 若 L中所有边各异，则称 L为简单路。 若此时又有 v 0 = v n，则称 L为简单回路。 若 L中所有结点各异，则称 L为基本路。 若此时又有 v 0 = v n，则称 L为基本回路。 若 L既是简单路，又是基本路，则称 L 为初级路。若此时又有 v 0 = v n，则称 L 为 初级回路。 在图9.11中， L 1是一条简单路。 L 2 是一条简单路、基本路、初级路
第9章图论 定理9.2.1 在n阶图G中，若从结点，到yy抖)存在一 条路，则必存在长度小于等于-1的路。 证明：设L:,ve1ye22ey是G中一条从结点，到y长 度为的路，路上有+1个结点。 若l≤n-1,则定理已证。 否则，1>n1,此时，+1>n,即路L上的结点数+1 大于图G中的结点数，此路上必有相同结点。设y和v,相 同。于是，此路两次通过同一个结点y(y,),所以在L上存 在v,到自身的回路Ck。在L上删除Cks上的一切边和除v,以 外的一切结点，得路L1:ve vervsevoL,仍为从结点y 到y,的路，且长度至少比L减少1。若路，的长度小于等于 n-1,则定理己证。否则，重复上述过程。由于G有n个结 点，经过有限步后，必得到从y到y,长度小于等于1的路
第9章 图论 定理9.2.1 在n阶图G中，若从结点vi到vj (vi ≠vj )存在一 条路，则必存在长度小于等于n-1的路。 证明：设L：vi e1 v1 e2 v2…ej vj是G中一条从结点vi到vj长 度为l的路，路上有l+1个结点。 若l≤n-1，则定理已证。 否则，l＞n-1，此时，l+1＞n，即路L上的结点数l+1 大于图G中的结点数n，此路上必有相同结点。设vk和vs相 同。于是，此路两次通过同一个结点vk (vs )，所以在L上存 在vs到自身的回路Cks。在L上删除Cks上的一切边和除vs以 外的一切结点，得路L1：vi e1 v1…ek vs…ej vj。L1仍为从结点vi 到vj的路，且长度至少比L减少1。若路L1的长度小于等于 n-1，则定理已证。否则，重复上述过程。由于G有n个结 点，经过有限步后，必得到从vi到vj长度小于等于n-1的路
第9章图论 推论在n阶图G中，若从结点y,到y,y,y,)存在路，则 必存在长度小于等于-1的初级路。 由定理9.2.1的证明过程知，本推论成立。 类似的可证明下列定理和推论。 定理9.2.2在n阶图G中，若存在结点y,到自身的回路 则必存在v,到自身长度小于等于n的回路。 推论在n阶图G中，若存在结点y,到自身的简单回路， 则必存在y,到自身长度小于等于的初级回路。 返回章目录
第9章 图论 推论 在n阶图G中，若从结点vi到vj (vi ≠vj )存在路，则 必存在长度小于等于n-1的初级路。 由定理9.2.1的证明过程知，本推论成立。 类似的可证明下列定理和推论。 定理9.2.2 在n阶图G中，若存在结点vi到自身的回路， 则必存在vi到自身长度小于等于n的回路。 推论 在n阶图G中，若存在结点vi到自身的简单回路， 则必存在vi到自身长度小于等于n的初级回路。 返回章目录
第9章图论 9.3连通图 9.3.1无向连通图 定义9.3.1在无向图G中，如果结点u和结点v之间存在 条路，则称结点和结点v连通。记为u~v。规定，G中任 意结点v和自身连通，即v~v 在无向图中，如果结点u和结点v连通，即u~v,那么， 结点v和结点连通，即v~u。所以，无向图结点间的连通 是对称的。 设G=<V,E>是无向图，在图G的结点集V上建立一个二 元关系R: R-<u,>|u∈V∧v∈V个u和v连通 R叫做无向图G的结点集V上的连通关系。 因为R是自反的、对称的、传递的，所以R是V上的等 价关系。无向图G的结点集V上的连通关系是等价关系
第9章 图论 9.3连通图 9.3.1无向连通图 定义9.3.1 在无向图G中，如果结点u和结点v之间存在 一条路，则称结点u和结点v连通。记为u～v。规定，G中任 意结点v和自身连通，即v～v。 在无向图中，如果结点u和结点v连通，即u～v，那么， 结点v和结点u连通，即v～u。所以，无向图结点间的连通 是对称的。 设G=V,E是无向图，在图G的结点集V上建立一个二 元关系R： R=u,v | uV∧vV∧u和v连通 R叫做无向图G的结点集V上的连通关系。 因为R是自反的、对称的、传递的，所以R是V上的等 价关系。无向图G的结点集V上的连通关系是等价关系