《图论及其应用》课程教学课件（PPT讲稿）第一章 图的基本概念 1-3 子图、图运算、路与连通性

第一章图的基本概念 本次课主要内容 子图、图运算、路与连通性 (一)、子图的相关概念 (二)、图运算 (三)、路与连通性

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 1 第一章 图的基本概念 本次课主要内容 子图、图运算、路与连通性 (一)、子图的相关概念 (三)、路与连通性 (二)、图运算

(一)、子图的相关概念 1、子图 简单地说，图G的任意一部分（包括本身）都称为是图G的 的一个子图。 定义1如果 V(H)二V(G),E(H)sE(G) 且H中边的重数不超过G中对应边的条数，则称为 G的子图，记为H三G 当 HG,H≠G 时，称H是G的真子图，记为 H二

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 2 1、子图 简单地说，图G的任意一部分(包括本身)都称为是图G的 的一个子图。 定义1 如果 (一)、子图的相关概念 V H V G E H E G ( ) ( ), ( ) ( )   且H中边的重数不超过G中对应边的条数，则称H为 G的子图，记为 H G  当 H G H G   , 时，称H是G的真子图，记为 H G

2、点与边的导出子图 (1)图G的顶点导出子图 定义2如果V'三V(G) 则以V为顶点集， 以两个端点均在V中的边集组成的图，称为 图G的点导出子图。记为：GΨ门 例1如图所示，求 G[V]。其中V'={1,3,5} 2 3 图G

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 3 2、点与边的导出子图 (1) 图G的顶点导出子图 定义2 如果 ，则以 为顶点集， 以两个端点均在 中的边集组成的图，称为 图G的点导出子图。记为： V V G   ( ) G V[ ] V V 例1 如图所示，求 G V[ ] 。其中 V =1,3,5 1 2 3 4 5 图G

解：由点导出子图的定义得： GIV'] (2)图G的边导出子图 定义3如果E'=E(G), 则以E'为边集， 以E”中边的所有端点为顶点集组成的图，称为 图G的边导出子图。记为：GE'] 例2如图所示，求 GLE']。其中E={13,24,35}

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 4 解：由点导出子图的定义得： G V[ ] 1 3 5 (2) 图G的边导出子图 定义3 如果 ，则以 为边集， 以 中边的所有端点为顶点集组成的图，称为 图G的边导出子图。记为： E E G   ( ) E E G E[ ] 例2 如图所示，求 G E[ ] 。其中 E =13,24,35

图G 解：由边导出子图的定义得： 3 GIE'T

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 5 解：由边导出子图的定义得： 1 2 3 4 5 图G G E[ ] 1 2 3 4 5

3、图的生成子图 定义3如果图G的一个子图包含G的所有顶点，称 该子图为G的一个生成子图 例2如图所示，求G的所有生成子图 图G 解：按边数分别求出 /

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 3、图的生成子图 定义3 如果图G的一个子图包含G的所有顶点，称 该子图为G的一个生成子图 例2 如图所示，求G的所有生成子图 1 2 3 图G 解：按边数分别求出

定理：简单图G=(m,m)的所有生成子图个数为2m (二)、图运算 在图论中，将两个或更多的图按照某种方式合并，或者对 一个图作某种形式的操作，可以得到很有意义的新图。将图 合并或对一个图进行操作，称为图运算。图运算形式很多。 1、图的删点、删边运算 (1)、图的删点运算 设V'V(G), 在G中删去V 中的顶点和G中与之关 联的所有边的操作，称为删点运算。记为G一V 特别地，如果只删去一个点v,则记为Gv

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 定理：简单图G=(n,m)的所有生成子图个数为2 m (二)、图运算 在图论中，将两个或更多的图按照某种方式合并，或者对 一个图作某种形式的操作，可以得到很有意义的新图。将图 合并或对一个图进行操作，称为图运算。图运算形式很多。 1、图的删点、删边运算 (1)、图的删点运算 设 ，在G中删去 中的顶点和G中与之关 联的所有边的操作，称为删点运算。记为 V V G   ( ) V G V−  特别地，如果只删去一个点v，则记为G-v

(2)、图的删边运算 E'二E(G),在G中删去E'中的所有边的操作， 设 为删边运算。记为G一E 特别地，如果只删去一条边e,则记为G-e. 注：删点、删边后得到的图是原图的子图。 2、图的并运算 设G1,G,是G的两个子图，G,与G,并是指由V(G)UV(G2) 为 顶点集，以E(G)UE(G2) 为边集组成的子图。记为： GUG2 特别是， 如果G,G2不相交（没有公共顶点），称它们的并为直接并， 可以记为： G1+G2

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 8 (2)、图的删边运算 设 ，在G中删去 中的所有边的操作， 称为删边运算。记为 E E G   ( ) E G E−  特别地，如果只删去一条边e，则记为G-e. 注：删点、删边后得到的图是原图的子图。 2、图的并运算 设G1 ,G2是G的两个子图，G1与G2并是指由 为 顶点集，以 为边集组成的子图。记为： 1 2 V G V G ( ) ( ) 1 2 E G E G ( ) ( ) G G 1 2 特别是，如果G1 ,G2不相交(没有公共顶点)，称它们的并为直接并， 可以记为： G G 1 2 +

2、图的交运算 设G,G2是G的两个子图，G,与G,交是指由V(G)∩V(G2)为 顶点集，以E(G)⌒E(G2)为边集组成的子图。记为： G∩G2 3、图的差运算 设G1,G,是两个图，G,与G2的差是指从G,中删去G2中的边得到的 新图。记为G1-G2 4、图的对称差运算（或环和运算） 设G1,G2是两个图，G1与G,的对称差定义为： G△G2=(GUG2)-(G1∩G2)

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 9 2、图的交运算 设G1 ,G2是G的两个子图，G1与G2交是指由 为 顶点集，以 为边集组成的子图。记为： 1 2 V G V G ( ) ( ) 1 2 E G E G ( ) ( ) G G 1 2 设G1 ,G2是两个图，G1与G2的差是指从G1中删去G2中的边得到的 新图。记为G1 -G2 . 3、图的差运算 4、图的对称差运算(或环和运算) 设G1 ,G2是两个图，G1与G2的对称差定义为： 1 2 1 2 1 2 G G G G G G  = − ( ) ( )

例3已知G,与G2,求 GUG G1∩G2 G1-G2 G2-G G1△G2 3 G 解：由相应运算定义得下面结果： d 3 GUG2 G1∩G2 10

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 10 例3 已知G1与G2，求 G G 1 2 G G1 2  G G 1 2 G G 1 2 − G G 2 1 − 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 h 5 g i j G G 1 2 2 3 4 c d e G G 1 2