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