图论课件子图的相关概念.ppt

* * 图论及其应用 应用数学学院 第一章 图的基本概念 本次课主要内容 子图、图运算、路与连通性 (一)、子图的相关概念 (三)、路与连通性 (二)、图运算 1、子图 简单地说，图G的任意一部分(包括本身)都称为是图G的 的一个子图。 定义1 如果 (一)、子图的相关概念 且H中边的重数不超过G中对应边的条数，则称H为 G的子图，记为 当 时，称H是G的真子图，记为 2、点与边的导出子图 (1) 图G的顶点导出子图 定义2 如果 ，则以 为顶点集， 以两个端点均在 中的边集组成的图，称为 图G的点导出子图。记为： 例1 如图所示，求 。其中 1 2 3 4 5 图G 解：由点导出子图的定义得： 1 3 5 (2) 图G的边导出子图 定义3 如果 ，则以 为边集， 以 中边的所有端点为顶点集组成的图，称为 图G的边导出子图。记为： 例2 如图所示，求 。其中 解：由边导出子图的定义得： 1 2 3 4 5 图G 1 2 3 4 5 3、图的生成子图 定义3 如果图G的一个子图包含G的所有顶点，称 该子图为G的一个生成子图 例2 如图所示，求G的所有生成子图 1 2 3 图G 解：按边数分别求出 定理：简单图G=(n,m)的所有生成子图个数为2m (二)、图运算 在图论中，将两个或更多的图按照某种方式合并，或者对一个图作某种形式的操作，可以得到很有意义的新图。将图合并或对一个图进行操作，称为图运算。图运算形式很多。 1、图的删点、删边运算 (1)、图的删点运算 设 ，在G中删去 中的顶点和G中与之关联的所有边的操作，称为删点运算。记为 特别地，如果只删去一个点v，则记为G-v. (2)、图的删边运算 设 ，在G中删去 中的所有边的操作，称为删边运算。记为 特别地，如果只删去一条边e，则记为G-e. 注：删点、删边后得到的图是原图的子图。 2、图的并运算 设G1,G2是G的两个子图，G1与G2并是指由 为顶点集，以 为边集组成的子图。记为： 特别是，如果G1,G2不相交(没有公共顶点)，称它们的并为直接并，可以记为： 2、图的交运算 设G1,G2是G的两个子图，G1与G2交是指由 为顶点集，以 为边集组成的子图。记为： 设G1,G2是两个图，G1与G2的差是指从G1中删去G2中的边得到的新图。记为G1-G2. 3、图的差运算 4、图的对称差运算(或环和运算) 设G1,G2是两个图，G1与G2的对称差定义为： 例3 已知G1与G2，求 1 2 3 4 a b c d e f G1 h 2 3 5 4 c d e g i j G2 解：由相应运算定义得下面结果： 1 2 3 4 a b c d e f 5 h g i j 2 3 4 c d e 1 2 3 a b f h 2 3 5 4 g i j 1 2 3 4 a b f 5 h g i j 5、图的联运算 设G1,G2是两个不相交的图，作G1+G2，并且将G1中每个顶点和G2中的每个顶点连接，这样得到的新图称为G1与G2的联图。记为 ： 例4 已知G1与G2，求 2 1 G1 3 4 5 G2 解：由联图的定义得： 2 1 3 4 5 6、图的积图 设 是两个图。对点集 的任意两个点u=(u1,u2)与v=(v1,v2),当(u1=v1和u2adjv2) 或(u2=v2和u1adjv1)时，把u与v相连。如此得到的新图称为G1与G2的积图。记为 例5 已知G1与G2，求 G1 1 2 G2 3 4 5 (1,4) (1,3) (1,5) (2,3) (2,4) (2,5) 6、图的合成图 设 是两个图。对点集