离散数学第10章陈瑜.ppt

陈瑜,Email：yu2023/10/17,离散数学,计算机学院,2023/10/17,计算机科学与工程学院,2,10.1 图的基本概念,2023/10/17,计算机科学与工程学院,3,主要内容,图的基本概念什么是图图的分类结点的度数 握手定理子图与补图 完全图补图图的同构,2023/10/17,计算机科学与工程学院,4,10.1 图的基本概念,无序积的定义：设A,B 为任意集合，称集合A&B(a,b)|aA，bB为A 与B 的无序积，（a,b）称为无序对。与序偶不同，无论a,b是否相等，均有：(a,b)(b,a)。,2023/10/17,计算机科学与工程学院,5,10.1 图的基本概念,无序积的定义：设A,B 为任意集合，称集合A&B(a,b)|aA，bB为A 与B 的无序积，（a,b）称为无序对。与序偶不同，无论a,b是否相等，均有：(a,b)(b,a)。,2023/10/17,计算机科学与工程学院,6,图的定义,定义10-1.1一个图是一个序偶，记为,G，其中：1）V（G）v1,v2,v3,vn是一个有限的非空集合，vi(i1,2,3,n)称为结点,简称点，V为结点集；2）E（G）e1,e2,e3,em是一个有限的集合，ei(i1,2,3,m)称为边，E为边集，E中的每个元素都是由V中不同结点所构成的无序对，且不含重复元素。3）图G的结点数称为G的阶，用n表示，G的边数用m表示，也可表示成(G)=m。,2023/10/17,计算机科学与工程学院,7,图的定义,定义10-1.1一个图是一个序偶，记为,G，其中：1）V（G）v1,v2,v3,vn是一个有限的非空集合，vi(i1,2,3,n)称为结点,简称点，V为结点集；2）E（G）e1,e2,e3,em是一个有限的集合，ei(i1,2,3,m)称为边，E为边集，E中的每个元素都是由V中不同结点所构成的无序对，且不含重复元素。3）图G的结点数称为G的阶，用n表示，G的边数用m表示，也可表示成(G)=m。,2023/10/17,计算机科学与工程学院,8,图的定义,定义10-1.1一个图是一个序偶，记为,G，其中：1）V（G）v1,v2,v3,vn是一个有限的非空集合，vi(i1,2,3,n)称为结点,简称点，V为结点集；2）E（G）e1,e2,e3,em是一个有限的集合，ei(i1,2,3,m)称为边，E为边集，E中的每个元素都是由V中不同结点所构成的无序对，且不含重复元素。3）图G的结点数称为G的阶，用n表示，G的边数用m表示，也可表示成(G)=m。,2023/10/17,计算机科学与工程学院,9,图的分类(按边的方向),若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e(u，v)，这时称u，v是边e的两个端点；若边e与有序结点对相对应，则称边e为有向边，记为e，这时称u是边e的始点。v是边e的终点，统称为e的端点；e是u的出边，是v的入边。每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图；有些边是无向边，而另一些是有向边的图称为混合图。,用小圆圈表示V中的结点，用由u指向v的有向线段表示，无向线段表示(u,v)。,2023/10/17,计算机科学与工程学院,10,图的分类(按边的方向),若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e(u，v)，这时称u，v是边e的两个端点；若边e与有序结点对相对应，则称边e为有向边，记为e，这时称u是边e的始点。v是边e的终点，统称为e的端点；e是u的出边，是v的入边。每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图；有些边是无向边，而另一些是有向边的图称为混合图。,用小圆圈表示V中的结点，用由u指向v的有向线段表示，无向线段表示(u,v)。,2023/10/17,计算机科学与工程学院,11,图的分类(按边的方向),若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e(u，v)，这时称u，v是边e的两个端点；若边e与有序结点对相对应，则称边e为有向边，记为e，这时称u是边e的始点。v是边e的终点，统称为e的端点；e是u的出边，是v的入边。每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图；有些边是无向边，而另一些是有向边的图称为混合图。,用小圆圈表示V中的结点，用由u指向v的有向线段表示，无向线段表示(u,v)。,2023/10/17,计算机科学与工程学院,12,图的分类(按边的方向),若边e与无序结点对(u，v)相对应，则称边e为无向边,记为e(u，v)，这时称u，v是边e的两个端点；若边e与有序结点对相对应，则称边e为有向边，记为e，这时称u是边e的始点。v是边e的终点，统称为e的端点；e是u的出边，是v的入边。每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图；有些边是无向边，而另一些是有向边的图称为混合图。,用小圆圈表示V中的结点，用由u指向v的有向线段表示，无向线段表示(u,v)。,2023/10/17,计算机科学与工程学院,13,几个概念,在一个图中，关联结点vi和vj的边e，无论是有向的还是无向的，均称边e与结点vI和vj相关联，而vi和vj称为邻接点，否则称为不邻接的；,关联于同一个结点的两条边称为邻接边；图中关联同一个结点的边称为环(或自回路)；图中不与任何结点相邻接的结点称为孤立结点；仅由孤立结点组成的图称为零图；仅含一个结点的零图称为平凡图；含有n个结点、m条边的图称为(n，m)图；,2023/10/17,计算机科学与工程学院,14,几个概念,在一个图中，关联结点vi和vj的边e，无论是有向的还是无向的，均称边e与结点vI和vj相关联，而vi和vj称为邻接点，否则称为不邻接的；,关联于同一个结点的两条边称为邻接边；图中关联同一个结点的边称为环(或自回路)；图中不与任何结点相邻接的结点称为孤立结点；仅由孤立结点组成的图称为零图；仅含一个结点的零图称为平凡图；含有n个结点、m条边的图称为(n，m)图；,2023/10/17,计算机科学与工程学院,15,几个概念,在一个图中，关联结点vi和vj的边e，无论是有向的还是无向的，均称边e与结点vI和vj相关联，而vi和vj称为邻接点，否则称为不邻接的；,关联于同一个结点的两条边称为邻接边；图中关联同一个结点的边称为环(或自回路)；图中不与任何结点相邻接的结点称为孤立结点；仅由孤立结点组成的图称为零图；仅含一个结点的零图称为平凡图；含有n个结点、m条边的图称为(n，m)图；,2023/10/17,计算机科学与工程学院,16,图的分类(按边的重数),在有向图中，两个结点间(包括结点自身间)若有同始点和同终点的几条边，则这几条边称为平行边。在无向图中，两个结点间(包括结点自身间)若有几条边，则这几条边称为平行边；含有平行边的图称为多重图；含有环的多重图称为广义图（伪图）；满足定义9-1.1的图称为简单图。将多重图和广义图中的平行边代之以一条边，去掉环，可以得到一个简单图，称为原来图的基图。,2023/10/17,计算机科学与工程学院,17,图的分类(按边的重数),在有向图中，两个结点间(包括结点自身间)若有同始点和同终点的几条边，则这几条边称为平行边。在无向图中，两个结点间(包括结点自身间)若有几条边，则这几条边称为平行边；含有平行边的图称为多重图；含有环的多重图称为广义图（伪图）；满足定义10-1.1的图称为简单图。将多重图和广义图中的平行边代之以一条边，去掉环，可以得到一个简单图，称为原来图的基图。,2023/10/17,计算机科学与工程学院,18,图的分类(按边的重数),在有向图中，两个结点间(包括结点自身间)若有同始点和同终点的几条边，则这几条边称为平行边。在无向图中，两个结点间(包括结点自身间)若有几条边，则这几条边称为平行边；含有平行边的图称为多重图；含有环的多重图称为广义图（伪图）；满足定义10-1.1的图称为简单图。将多重图和广义图中的平行边代之以一条边，去掉环，可以得到一个简单图，称为原来图的基图。,2023/10/17,计算机科学与工程学院,19,图的分类(按权),赋权图G是一个三重组，其中V是结点集合，E是边的集合，g是边E上的权值。非赋权图称为无权图。,v3,v2,v1,v4,G1,2023/10/17,计算机科学与工程学院,20,结点的度数,在无向图G中，与结点v(vV)关联的边的条数（有环时计算两次），称为该结点的度数，记为deg(v)；最大点度和最小点度分别记为和。在有向图G中，以结点v为始点引出的边的条数，称为该结点的出度,记为deg+(v)；以结点v为终点引入的边的条数，称为该结点的入度,记为deg-(v)；而结点的引出度数和引入度数之和称为该结点的度数，记为deg(v)，即deg(v)deg+(v)+deg-(v)；,2023/10/17,计算机科学与工程学院,21,结点的度数,在无向图G中，与结点v(vV)关联的边的条数（有环时计算两次），称为该结点的度数，记为deg(v)；最大点度和最小点度分别记为和。在有向图G中，以结点v为始点引出的边的条数，称为该结点的出度,记为deg+(v)；以结点v为终点引入的边的条数，称为该结点的入度,记为deg-(v)；而结点的引出度数和引入度数之和称为该结点的度数，记为deg(v)，即deg(v)deg+(v)+deg-(v)；,2023/10/17,计算机科学与工程学院,22,对于图G，度数为0的结点称为孤立结点；只由孤立结点构成的图G=（V，）称为零图；只由一个孤立结点构成的图称为平凡图；在图G中，称度数为奇数的结点为奇度数结点，度数为偶数的结点为偶度数结点。各点度数相等的图称为正则图，特别将点度为k的正则图称为k度正则图。,2023/10/17,计算机科学与工程学院,23,对于图G，度数为0的结点称为孤立结点；只由孤立结点构成的图G=（V，）称为零图；只由一个孤立结点构成的图称为平凡图；在图G中，称度数为奇数的结点为奇度数结点，度数为偶数的结点为偶度数结点。各点度数相等的图称为正则图，特别将点度为k的正则图称为k度正则图。,2023/10/17,计算机科学与工程学院,24,对于图G，度数为0的结点称为孤立结点；只由孤立结点构成的图G=（V，）称为零图；只由一个孤立结点构成的图称为平凡图；在图G中，称度数为奇数的结点为奇度数结点，度数为偶数的结点为偶度数结点。各点度数相等的图称为正则图，特别将点度为k的正则图称为k度正则图。,2023/10/17,计算机科学与工程学院,25,例10.1,deg(v1)3，deg+(v1)2，deg-(v1)1；,deg(v2)3，deg+(v2)2，deg-(v2)1；deg(v3)5，deg+(v3)2，deg-(v3)3；deg(v4)1，deg+(v4)0，deg-(v4)1；deg(v5)deg+(v5)deg-(v5)0；,2023/10/17,计算机科学与工程学院,26,例10.1,deg(v1)3，deg+(v1)2，deg-(v1)1；,deg(v2)3，deg+(v2)2，deg-(v2)1；deg(v3)5，deg+(v3)2，deg-(v3)3；deg(v4)1，deg+(v4)0，deg-(v4)1；deg(v5)deg+(v5)deg-(v5)0；,2023/10/17,计算机科学与工程学院,27,例10.1,deg(v1)3，deg+(v1)2，deg-(v1)1；,deg(v2)3，deg+(v2)2，deg-(v2)1；deg(v3)5，deg+(v3)2，deg-(v3)3；deg(v4)1，deg+(v4)0，deg-(v4)1；deg(v5)deg+(v5)deg-(v5)0；,2023/10/17,计算机科学与工程学院,28,例10.1,deg(v1)3，deg+(v1)2，deg-(v1)1；,deg(v2)3，deg+(v2)2，deg-(v2)1；deg(v3)5，deg+(v3)2，deg-(v3)3；deg(v4)1，deg+(v4)0，deg-(v4)1；deg(v5)deg+(v5)deg-(v5)0；,2023/10/17,计算机科学与工程学院,29,例10.1,deg(v1)3，deg+(v1)2，deg-(v1)1；,deg(v2)3，deg+(v2)2，deg-(v2)1；deg(v3)5，deg+(v3)2，deg-(v3)3；deg(v4)1，deg+(v4)0，deg-(v4)1；deg(v5)deg+(v5)deg-(v5)0；,2023/10/17,计算机科学与工程学院,30,握手定理（Euler,1736年）,定理10-1.1（握手定理）对于任何（n,m）图G=（V，E），所有结点的度数的总和等于边数的两倍，即：证明：根据结点度数的定义，在计算结点度数时每条边对于它所关联的结点被计算了两次，因此，G中结点度数的总和恰好为边数m的2倍。,2023/10/17,计算机科学与工程学院,31,在图G中，其Vv1,v2,v3,vn，E,e1，e2，em，度数为奇数的结点个数为偶数。,证明设V1v|vV且deg(v)奇数，V2v|vV且deg(v)偶数。显然，V1V2，且V1V2V，于是有：,由于上式中的2m和|V2|(偶数之和为偶数)均为偶数，因而也为偶数。于是|V1|为偶数(因为V1中的结点v之deg(v)都为奇数)，即奇度数的结点个数为偶数。,2023/10/17,计算机科学与工程学院,32,在图G中，其Vv1,v2,v3,vn，E,e1，e2，em，度数为奇数的结点个数为偶数。,证明设V1v|vV且deg(v)奇数，V2v|vV且deg(v)偶数。显然，V1V2，且V1V2V，于是有：,由于上式中的2m和|V2|(偶数之和为偶数)均为偶数，因而也为偶数。于是|V1|为偶数(因为V1中的结点v之deg(v)都为奇数)，即奇度数的结点个数为偶数。,2023/10/17,计算机科学与工程学院,33,在图G中，其Vv1,v2,v3,vn，E,e1，e2，em，度数为奇数的结点个数为偶数。,证明设V1v|vV且deg(v)奇数，V2v|vV且deg(v)偶数。显然，V1V2，且V1V2V，于是有：,由于上式中的2m和|V2|(偶数之和为偶数)均为偶数，因而也为偶数。于是|V1|为偶数(因为V1中的结点v之deg(v)都为奇数)，即奇度数的结点个数为偶数。,2023/10/17,计算机科学与工程学院,34,定理10-1.2：对于任何（n,m）有向图G=（V，E），则所有结点的引出度数之和等于所有结点的引入度数之和，所有结点的度数的总和等于边数的两倍，即：,证明：（略）。,2023/10/17,计算机科学与工程学院,35,度数序列,设Vv1,v2,vn为图G的结点集，称(deg(v1),deg(v2),deg(vn)为G的度数序列。,上图的度数序列为（3,3,5,1,0）。,2023/10/17,计算机科学与工程学院,36,度数序列,设Vv1,v2,vn为图G的结点集，称(deg(v1),deg(v2),deg(vn)为G的度数序列。,上图的度数序列为（3,3,5,1,0）。,2023/10/17,计算机科学与工程学院,37,子图,定义10-1.4 设有图G和图H。若V2V1，E2E1，则称H是G的子图，记为HG。即V2V1或E2E1，则称H是G的真子图，记为HG。若V2=V1，则称H是G的生成子图。设V2=V1且E2=E1或E2=，则称H是G的平凡子图。设v是图G的一个结点，从G中删去结点v及其关联的全部边后得到的图称为G的删点子图，简记为Gv。,2023/10/17,计算机科学与工程学院,38,子图,定义10-1.4 设有图G和图H。若V2V1，E2E1，则称H是G的子图，记为HG。即V2V1或E2E1，则称H是G的真子图，记为HG。若V2=V1，则称H是G的生成子图。设V2=V1且E2=E1或E2=，则称H是G的平凡子图。设v是图G的一个结点，从G中删去结点v及其关联的全部边后得到的图称为G的删点子图，简记为Gv。,2023/10/17,计算机科学与工程学院,39,子图,定义10-1.4 设有图G和图H。若V2V1，E2E1，则称H是G的子图，记为HG。即V2V1或E2E1，则称H是G的真子图，记为HG。若V2=V1，则称H是G的生成子图。设V2=V1且E2=E1或E2=，则称H是G的平凡子图。设v是图G的一个结点，从G中删去结点v及其关联的全部边后得到的图称为G的删点子图，简记为Gv。,2023/10/17,计算机科学与工程学院,40,设e是图G的一条边，从G中删去边e后得到的图称为G删边子图，简记为Ge。图G，SV，则G(S)=(S，E)是一个以S为结点，以E=uv|u,vS,uvE为边集的图，称为G的点诱导子图。图G，TE且T，则G（T）是一个以T为边集，以T中各边关联的全部结点为结点集的图，称为G的边诱导子图。,2023/10/17,计算机科学与工程学院,41,设e是图G的一条边，从G中删去边e后得到的图称为G删边子图，简记为Ge。图G，SV，则G(S)=(S，E)是一个以S为结点，以E=uv|u,vS,uvE为边集的图，称为G的点诱导子图。图G，TE且T，则G（T）是一个以T为边集，以T中各边关联的全部结点为结点集的图，称为G的边诱导子图。,2023/10/17,计算机科学与工程学院,42,设e是图G的一条边，从G中删去边e后得到的图称为G删边子图，简记为Ge。图G，SV，则G(S)=(S，E)是一个以S为结点，以E=uv|u,vS,uvE为边集的图，称为G的点诱导子图。图G，TE且T，则G（T）是一个以T为边集，以T中各边关联的全部结点为结点集的图，称为G的边诱导子图。,2023/10/17,计算机科学与工程学院,43,G1,v,G1-V,G2,e1,e2,G2-e1,e2,e3,e2,e1,v2,v1,G3,e3,e2,e1,v2,v1,删点子图,删边子图,点诱导子图G3(v1,v2),边诱导子图G3(e1,e2,e3),例10.2,2023/10/17,计算机科学与工程学院,44,G1,v,G1-V,G2,e1,e2,G2-e1,e2,e3,e2,e1,v2,v1,G3,e3,e2,e1,v2,v1,删点子图,删边子图,点诱导子图G3(v1,v2),边诱导子图G3(e1,e2,e3),例10.2,2023/10/17,计算机科学与工程学院,45,完全图,设G为一个具有n个结点的无向简单图，如果G中任一个结点都与其余n-1个结点相邻接，则称G为无向完全图，简称G为完全图，记为Kn。设G为一个具有n个结点的有向简单图，若对于任意u,vV(uv)，既有有向边，又有有向边，则称G为有向完全图，在不发生误解的情况下，也记为Kn。,无向完全图Kn的边数为=n(n-1)，有向完全图Kn的边数为=n(n-1)。,2023/10/17,计算机科学与工程学院,46,完全图,设G为一个具有n个结点的无向简单图，如果G中任一个结点都与其余n-1个结点相邻接，则称G为无向完全图，简称G为完全图，记为Kn。设G为一个具有n个结点的有向简单图，若对于任意u,vV(uv)，既有有向边，又有有向边，则称G为有向完全图，在不发生误解的情况下，也记为Kn。,无向完全图Kn的边数为=n(n-1)，有向完全图Kn的边数为=n(n-1)。,2023/10/17,计算机科学与工程学院,47,完全图,设G为一个具有n个结点的无向简单图，如果G中任一个结点都与其余n-1个结点相邻接，则称G为无向完全图，简称G为完全图，记为Kn。设G为一个具有n个结点的有向简单图，若对于任意u,vV(uv)，既有有向边，又有有向边，则称G为有向完全图，在不发生误解的情况下，也记为Kn。,无向完全图Kn的边数为=n(n-1)，有向完全图Kn的边数为=n(n-1)。,2023/10/17,计算机科学与工程学院,48,补图,设G为具有n个结点的简单图,从完全图Kn中删去G中的所有边而得到的图称为G相对于完全图Kn的补图，简称G的补图，记为。这里，当G为有向图时，则Kn为有向完全图；当G为无向图时，则Kn为无向完全图。,显然，G与 互为补图，即。,2023/10/17,计算机科学与工程学院,49,补图,设G为具有n个结点的简单图,从完全图Kn中删去G中的所有边而得到的图称为G相对于完全图Kn的补图，简称G的补图，记为。这里，当G为有向图时，则Kn为有向完全图；当G为无向图时，则Kn为无向完全图。,显然，G与 互为补图，即。,2023/10/17,计算机科学与工程学院,50,例10.3,2023/10/17,计算机科学与工程学院,51,二部图,设图G=，如果它的结点集可以划分成两个子集X和Y，使得它的每一条边的一个关联结点在X中，另一个关联结点在Y中，则这样的图称为二部图。设|X|=n1，|Y|=n2。如果X中的每一个结点与Y中的全部结点都邻接，则称G为完全二部图，并记为Kn1,n2。,2023/10/17,计算机科学与工程学院,52,二部图,设图G=，如果它的结点集可以划分成两个子集X和Y，使得它的每一条边的一个关联结点在X中，另一个关联结点在Y中，则这样的图称为二部图。设|X|=n1，|Y|=n2。如果X中的每一个结点与Y中的全部结点都邻接，则称G为完全二部图，并记为Kn1,n2。,2023/10/17,计算机科学与工程学院,53,图的同构,2023/10/17,计算机科学与工程学院,54,定义10-1.6,设两个图G=和G=，如果存在双射函数g：VV，使得对于任意的e=(vi,vj)（或者）E当且仅当e(g(vi),g(vj)（或者）E，则称G与G同构，记为GG。（同构是指两个图的边1-1对应）图的同构关系是图集上的等价关系。,2023/10/17,计算机科学与工程学院,55,定义10-1.6,设两个图G=和G=，如果存在双射函数g：VV，使得对于任意的e=(vi,vj)（或者）E当且仅当e(g(vi),g(vj)（或者）E，则称G与G同构，记为GG。（同构是指两个图的边1-1对应）图的同构关系是图集上的等价关系。,2023/10/17,计算机科学与工程学院,56,例10.4,G1G2：av1，bv2，cv3，dv4，ev5,G3G4：av1，bv4，cv2，dv5，ev3；,2023/10/17,计算机科学与工程学院,57,例10.5,G5G6：av1，bv2，cv3，dv4，ev7，fv6，gv9，hv8，iv5，jv10,彼得森图,2023/10/17,计算机科学与工程学院,58,两个图同构的必要条件,结点数目相同；边数相同；度数相同的结点数相同。,注意：这三个条件并不是充分条件。例如下面两个图满足这三个条件，但它们不同构。,2023/10/17,计算机科学与工程学院,59,两个图同构的必要条件,结点数目相同；边数相同；度数相同的结点数相同。,注意：这三个条件并不是充分条件。例如下面两个图满足这三个条件，但它们不同构。,2023/10/17,计算机科学与工程学院,60,两个图同构的必要条件,结点数目相同；边数相同；度数相同的结点数相同。,注意：这三个条件并不是充分条件。例如下面两个图满足这三个条件，但它们不同构。,若图的结点可以任意挪动位置，而边,是完全弹性的，只要在不拉断的条件下，一个图可以变形为另一个图，那么这两个图是同构的。如下图所示：,2023/10/17,计算机科学与工程学院,61,G7与G8不同构为什么？,例10.6,2023/10/17,计算机科学与工程学院,62,G7与G8不同构为什么？,例10.6,2023/10/17,计算机科学与工程学院,63,G7与G8不同构为什么？,例10.6,这说明上述三个条件仅仅是必要而不充分,2023/10/17,计算机科学与工程学院,64,习题,P206 1、3(1)(4)、4、7、8,2023/10/17,计算机科学与工程学院,65,10.2 道路与回路,2023/10/17,计算机科学与工程学院,66,10.2 道路与回路,定义10-2.1 图G中结点和边相继交错出现的序列P=v0e1v1e2v2ekvk，若P中边ei的两端点是vi-1和vi（G是有向图时要求vi-1与vi分别是ei的始点和终点，即方向一致。），则称P为结点v0到结点vk的道路。简记为v0，vk。v0和vk分别称为此道路的起点和终点，统称为道路的端点。其余结点称为内部结点。道路中边的数目k称为此道路的长度。如P=v0，称为零道路，其长度为零。若v0vk，称为开道路，否则称为闭道路。,2023/10/17,计算机科学与工程学院,67,10.2 道路与回路,定义10-2.1 图G中结点和边相继交错出现的序列P=v0e1v1e2v2ekvk，若P中边ei的两端点是vi-1和vi（G是有向图时要求vi-1与vi分别是ei的始点和终点，即方向一致。），则称P为结点v0到结点vk的道路。简记为v0，vk。v0和vk分别称为此道路的起点和终点，统称为道路的端点。其余结点称为内部结点。道路中边的数目k称为此道路的长度。如P=v0，称为零道路，其长度为零。若v0vk，称为开道路，否则称为闭道路。,2023/10/17,计算机科学与工程学院,68,简单道路与基本道路,若道路中的所有边e1，e2，ek（有向边）互不相同，则称此道路为简单道路；闭的简单道路称为回路。若道路中的所有结点v0，v1，vk互不相同（从而所有边互不相同），则称此道路为基本道路；若回路中除v0vk外的所有结点v0，v1，vk-1互不相同（从而所有边互不相同），则称此回路为基本回路或者圈。基本道路(或基本回路)一定是简单道路(或简单回路)，但反之则不一定。为什么？,2023/10/17,计算机科学与工程学院,69,简单道路与基本道路,若道路中的所有边e1，e2，ek（有向边）互不相同，则称此道路为简单道路；闭的简单道路称为回路。若道路中的所有结点v0，v1，vk互不相同（从而所有边互不相同），则称此道路为基本道路；若回路中除v0vk外的所有结点v0，v1，vk-1互不相同（从而所有边互不相同），则称此回路为基本回路或者圈。基本道路(或基本回路)一定是简单道路(或简单回路)，但反之则不一定。为什么？,2023/10/17,计算机科学与工程学院,70,简单道路与基本道路,若道路中的所有边e1，e2，ek（有向边）互不相同，则称此道路为简单道路；闭的简单道路称为回路。若道路中的所有结点v0，v1，vk互不相同（从而所有边互不相同），则称此道路为基本道路；若回路中除v0vk外的所有结点v0，v1，vk-1互不相同（从而所有边互不相同），则称此回路为基本回路或者圈。基本道路(或基本回路)一定是简单道路(或简单回路)，但反之则不一定。为什么？,2023/10/17,计算机科学与工程学院,71,例10.7,在图G1中：v1e1v2e2v3e3v4e4v5e7v6：基本道路 v1e1v2e5v4e3v3e2v2e9v6:简单道路V2e10v2e2v3e3v4e5v2:回路V2e2v3e3v4e5v2:圈,e10,2023/10/17,计算机科学与工程学院,72,在图G2中：v1e2v5e3v2e6v4e8v3e9v3e5v2e1v1：回路v5e3v2e4v5：圈,2023/10/17,计算机科学与工程学院,73,注：,在不会引起误解的情况下，一条道路v0e1v1e2v2envn也可以用边的序列e1e2en来表示，这种表示方法对于有向图来说较为方便。在简单图中，一条道路v0e1v1e2v2envn也可以用结点的序列v0v1v2vn来表示。,2023/10/17,计算机科学与工程学院,74,注：,在不会引起误解的情况下，一条道路v0e1v1e2v2envn也可以用边的序列e1e2en来表示，这种表示方法对于有向图来说较为方便。在简单图中，一条道路v0e1v1e2v2envn也可以用结点的序列v0v1v2vn来表示。,2023/10/17,计算机科学与工程学院,75,道路图和圈图,若一个图能以一条基本道路表示出来，则称此图为道路图。n阶的道路图记为Pn。若一个图能以一个圈表示出来，则称此图为圈图。n阶的圈图记为Cn。例10.12,P5,C6,2023/10/17,计算机科学与工程学院,76,道路图和圈图,若一个图能以一条基本道路表示出来，则称此图为道路图。n阶的道路图记为Pn。若一个图能以一个圈表示出来，则称此图为圈图。n阶的圈图记为Cn。例10.12,P5,C6,2023/10/17,计算机科学与工程学院,77,道路图和圈图,若一个图能以一条基本道路表示出来，则称此图为道路图。n阶的道路图记为Pn。若一个图能以一个圈表示出来，则称此图为圈图。n阶的圈图记为Cn。例10.12,P5,C6,2023/10/17,计算机科学与工程学院,78,定理10-2.1,在一个具有n个结点的图中，如果从结点vi到结点vj(vivj)存在一条道路，则从vi到vj存在一条不多于n-1条边的道路。,证明:设vi0,vi1,vik为从vi到vj的长度为k的一条通路，其中vi0=vi，vik=vj。此通路上有k+1个结点。若kn-1，这条通路即为所求。若kn1，则此通路上的结点数k+1n，必存在一个结点在此通路中不止一次出现，设vis=vit，其中，0stk。去掉vis到vit中间的通路，至少去掉一条边，得通路vi0,vi1,vis,vit+1,vik，此通路比原通路的长度至少少1。如此重复进行下去，必可得一条从vi到vj不多于n-1条边的通路。,2023/10/17,计算机科学与工程学院,79,定理10-2.1,在一个具有n个结点的图中，如果从结点vi到结点vj(vivj)存在一条道路，则从vi到vj存在一条不多于n-1条边的道路。,证明:设vi0,vi1,vik为从vi到vj的长度为k的一条道路，其中vi0=vi，vik=vj。此道路上有k+1个结点。若kn-1，这条道路即为所求。若kn1，则此道路上的结点数k+1n，必存在一个结点在此道路中不止一次出现，设vis=vit，其中，0stk。去掉vis到vit中间的道路，至少去掉一条边，得道路vi0,vi1,vis,vit+1,vik，此道路比原道路的长度至少少1。如此重复进行下去，必可得一条从vi到vj不多于n-1条边的道路。,2023/10/17,计算机科学与工程学院,80,定理10-2.1,在一个具有n个结点的图中，如果从结点vi到结点vj(vivj)存在一条道路，则从vi到vj存在一条不多于n-1条边的道路。,证明:设vi0,vi1,vik为从vi到vj的长度为k的一条道路，其中vi0=vi，vik=vj。此道路上有k+1个结点。若kn-1，这条道路即为所求。若kn1，则此道路上的结点数k+1n，必存在一个结点在此道路中不止一次出现，设vis=vit，其中，0stk。去掉vis到vit中间的道路，至少去掉一条边，得道路vi0,vi1,vis,vit+1,vik，此道路比原道路的长度至少少1。如此重复进行下去，必可得一条从vi到vj不多于n-1条边的道路。,2023/10/17,计算机科学与工程学院,81,定理10-2.1,在一个具有n个结点的图中，如果从结点vi到结点vj(vivj)存在一条道路，则从vi到vj存在一条不多于n-1条边的道路。,证明:设vi0,vi1,vik为从vi到vj的长度为k的一条道路，其中vi0=vi，vik=vj。此道路上有k+1个结点。若kn-1，这条道路即为所求。若kn1，则此道路上的结点数k+1n，必存在一个结点在此道路中不止一次出现，设vis=vit，其中，0stk。去掉vis到vit中间的道路，至少去掉一条边，得道路vi0,vi1,vis,vit+1,vik，此道路比原道路的长度至少少1。如此重复进行下去，必可得一条从vi到vj不多于n-1条边的道路。,2023/10/17,计算机科学与工程学院,82,定理10-2.1,在一个具有n个结点的图中，如果从结点vi到结点vj(vivj)存在一条道路，则从vi到vj存在一条不多于n-1条边的道路。,证明:设vi0,vi1,vik为从vi到vj的长度为k的一条道路，其中vi0=vi，vik=vj。此道路上有k+1个结点。若kn-1，这条道路即为所求。若kn1，则此道路上的结点数k+1n，必存在一个结点在此道路中不止一次出现，设vis=vit，其中，0stk。去掉vis到vit中间的道路，至少去掉一条边，得道路vi0,vi1,vis,vit+1,vik，此道路比原道路的长度至少少1。如此重复进行下去，必可得一条从vi到vj不多于n-1条边的道路。,2023/10/17,计算机科学与工程学院,83,定理10-2.1,在一个具有n个结点的图中，如果从结点vi到结点vj(vivj)存在一条道路，则从vi到vj存在一条不多于n-1条边的道路。,证明:设vi0,vi1,vik为从vi到vj的长度为k的一条道路，其中vi0=vi，vik=vj。此道路上有k+1个结点。若kn-1，这条道路即为所求。若kn1，则此道路上的结点数k+1n，必存在一个结点在此道路中不止一次出现，设vis=vit，其中，0stk。去掉vis到vit中间的道路，至少去掉一条边，得道路vi0,vi1,vis,vit+1,vik，此道路比原道路的长度至少少1。如此重复进行下去，必可得一条从vi到vj不多于n-1条边的道路。,2023/10/17,计算机科学与工程学院,84,10.3 图的连通性,2023/10/17,计算机科学与工程学院,85,无向图的连通性,定义10-3.1 设u,v为无向图G中的两个结点，若u,v之间存在道路，则称结点u,v是连通的，记为uv。对任意结点u，规定uu。,无向图中结点之间的连通关系是等价关系。,我们可以利用连通关系对G的结点集进行一个划分:V1，V2，Vk（显然，Vi是一个等价类），使得G中 的任意两个结点u和v连通当且仅当u和v同属于一个 Vi(1ik)。则点诱导子图G（Vi）(1ik)是G的极 大连通子图，称为G的支。图G的分支数记为（G）。,2023/10/17,计算机科学与工程学院,86,无向图的连通性,定义10-3.1 设u,v为无向图G中的两个结点，若u,v之间存在道路，则称结点u,v是连通的，记为uv。对任意结点u，规定uu。,无向图中结点之间的连通关系是等价关系。,我们可以利用连通关系对G的结点集进行一个划分:V1，V2，Vk（显然，Vi是一个等价类），使得G中 的任意两个结点u和v连通当且仅当u和v同属于一个 Vi(1ik)。则点诱导子图G（Vi）(1ik)是G的极 大连通子图，称为G的支。图G的分支数记为（G）。,2023/10/17,计算机科学与工程学院,87,无向图的连通性,定义10-3.1 设u,v为无向图G中的两个结点，若u,v之间存在道路，则称结点u,v是连通的，记为uv。对任意结点u，规定uu。,无向图中结点之间的连通关系是等价关系。,我们可以利用连通关系对G的结点集进行一个划分:V1，V2，Vk（显然，Vi是一个等价类），使得G中 的任意两个结点u和v连通当且仅当u和v同属于一个 Vi(1ik)。则点诱导子图G（Vi）(1ik)是G的极 大连通子图，称为G的支。图G的分支数记为（G）。,2023/10/17,计算机科学与工程学院,88,连通图,定义10-3.2 若无向图G中任意两个结点都是连通的，则称G是连通图，否则称G是非连通图(或分离图)。定义10-3.2只有一个分支的无向图称为连通图，支数大于1的无向图称为非连通图。无向完全图Kn（n1）都是连通图，而多于一个结点的零图都是非连通图。,2023/10/17,计算机科学与工程学院,89,连通图,定义10-3.2 若无向图G中任意两个结点都是连通的，则称G是连通图，否则称G是非连通图(或分离图)。定义10-3.2只有一个分支的无向图称为连通图，支数大于1的无向图称为非连通图。无向完全图Kn（n1）都是连通图，而多于一个结点的零图都是非连通图。,2