电子摊越女学 elveraity af Beetronle Sclence and Techaelogy af Cha /936 3、图的生成子图 定义3如果图G的一个子图包含G的所有顶点，称 该子图为G的一个生成子图。 例2如图所示，求G的所有生成子图。 ò3 解：按边数分别求出： 图G 。一
3、图的生成子图 定义3 如果图G的一个子图包含G的所有顶点，称 该子图为G的一个生成子图。 例2 如图所示，求G的所有生成子图。 1 2 3 图G 解：按边数分别求出：
电子摊越女学 elveraity af Beetronle Sclence and Techaelogy af Cha /956 定理1简单图G=(n,m)的所有生成子图个数为2m. 二、图运算 在图论中，将两个或更多的图按照某种方式合并，或者对 一个图作某种形式的操作，可以得到很有意义的新图。将图 合并或对一个图进行操作，称为图运算。图运算形式很多。 (一)、图的删点、删边运算 设V'三V(G), 在G中删去V"中的顶点和G中与之关联 的所有边的操作， 称为删点运算。记为G-P. 特别地，如果只删去一个点v,则记为G-V
定理1 简单图G=(n, m) 的所有生成子图个数为2m. 二、图运算 在图论中，将两个或更多的图按照某种方式合并，或者对 一个图作某种形式的操作，可以得到很有意义的新图。将图 合并或对一个图进行操作，称为图运算。图运算形式很多。 (一)、图的删点、删边运算 设 ，在G中删去 中的顶点和G中与之关联 的所有边的操作，称为删点运算。记为 . 特别地，如果只删去一个点v，则记为G-v
电子特越女学 elveraityaf Bectrole Sclece and Techaology af Chaa /936 V2 V2 G G-[v3,V4] (2)、图的删边运算 设E'三E(G),在G中删去 E'中的所有边的操作，称为 删边运算。记为G一E'· 特别地，如果只删去一条边e,则记为G-e
v4 v3 v2 v1 G v2 v1 G-{v3, v4} (2)、图的删边运算 设 ，在G中删去 中的所有边的操作，称为 删边运算。记为 . 特别地，如果只删去一条边e，则记为G-e
电子摊越女学 elveraityaf Bectrole Sclece and Techaology af Chaa 1956 e VA 。N4 c c 3 e6 es E5 G G-[e1,eg,e6,e5] 注：删点要删关联的边， 删边不删关联的点！ (二)、图的并运算 设G,G2是G的两个子图，G,与G,并是指由V(G1)UV(G2)为顶 点集，以E(G1)UE(G2)为边集组成的子图。记为：G1UG2
v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 G G-{ e1, e3, e6, e5 } v1 v2 v3 v4 e2 e4 注：删点要删关联的边，删边不删关联的点！ (二)、图的并运算 设G1,G2是G的两个子图，G1与G2并是指由 为顶 点集，以 为边集组成的子图。记为：
电子科越女学 elveraityaf Bectrole Sclece and Techaology af Chaa 1956 特别是，如果G,G,不相交（没有公共顶点）， 称它们的并为直接并， 可以记为： G1+G2 d d a e 3 f 3 G2 d 2 h a G1;G2
特别是，如果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 h 5 g i j G G 1 2 U