第章图论 9,2路和回路 定义921设G=<VE>是图,G中的结点与边的交替序列L gave2"2…envn叫做v到υn的路。其中v1与v是e的端点, i=1,…n。v和vn分别叫做路L的始点和终点。路L中边的条数 叫做该路的长度 例如,在图9.11中, L1;v; eovesvoevsev3是从v到v3的路,v是始点 v3是终点,长度为4。 2: V1e1v2e3v3 是从v到v3的路,v1是始点, 是终点,长度为2 在简单图中没有平行边和环,路L:ve1ve2v2…enn完全 由它的结点序列vv1n2…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确定。所以，在简单图中的路可以 用结点序列表示
第章图论 定义922设G=<VE>是图,L是 从v到vn的路。若v。=Vn,则称L为回路 若L中所有边各异,则称L为简单路 若此时又有v=Vn,则称L为简单回路。 若L中所有结点各异,则称L为基本路。" 若此时又有v=v,则称L为基本回路。 若L既是简单路,又是基本路,则称L 为初级路。若此时又有v=n,则称L为 初级回路。 在图9中,L1是一条简单路。L20c 是一条简单路、基本路、初级路 图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 是一条简单路、基本路、初级路
第章图论 定理921在n阶图G中,若从结点v到v(v扣)存在 条路,则必存在长度小于等于n-1的路 证明:设L:Ve1ve22…e是G中一条从结点v到v长 度为的路,路上有H1个结点。 若Kn-1,则定理已证 否则,1>n-1,此时,H+1>n,即路L上的结点数H1 大于图G中的结点数n,此路上必有相同结点。设v和v相 同。于是,此路两次通过同一个结点v(),所以在L上存 在v到自身的回路C。在L上删除C上的一切边和除v以 外的一切结点,得路L1:vev1en巳,。L1仍为从结点v 到v的路,且长度至少比L减少1。若路L1的长度小于等于 n-1,则定理已证。否则,重复上述过程。由于G有n个结 点,经过有限步后,必得到从ν到v长度小于等于n-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的路
第章图论 推论在m阶图G中,若从结点到y()存在路,则 必存在长度小于等于n-1的初级路 由定理92.1的证明过程知,本推论成立。 类似的可证明下列定理和推论。 定理92.2在m阶图G中,若存在结点ν到自身的回路, 则必存在v到自身长度小于等于n的回路 推论在n阶图G中,若存在结点ν到自身的简单回路, 则必存在v到自身长度小于等于n的初级回路。 返回章目录
第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的初级回路。 返回章目录
第章图论 93连通图 9.3.1无向连通图 定义9.3.1在无向图G中,如果结点和结点v之间存在 条路,则称结点v和结点ν连通。记为w~ν。规定,G中任 意结点v和自身连通,即y~v 在无向图中,如果结点v和结点ν连通,即~v,那么, 结点v和结点连通,即y。所以,无向图结点间的连通 是对称的 设G=<V,E>是无向图,在图G的结点集建立一个二 元关系R: R=1<lD>|v∈T∧v∈A和v连通 R叫做无向图G的结点集上的连通关系。 因为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上的连通关系是等价关系