第8章图的基本概念 【例81.5】在图8.1.2中,G1,G2,G3均是G的真 子图,其中G1是G的由E1={e1,e2,e3,e4}导出的导出 子图G[E1];G2、G均是G的生成子图;G3是G的由 V3={a,d,e}导出的导出子图GLV3],同时也是由 E3={e4,e3}导出的导出子图G[E3]
第8章 图的基本概念 【例8.1.5】 在图8.1.2中，G1，G2，G3均是G的真 子图，其中G1是G的由E1={e1，e2，e3，e4}导出的导出 子图G［E1］；G2、G均是G的生成子图；G3是G的由 V3={a，d，e}导出的导出子图G［V3］，同时也是由 E3={e4，e5}导出的导出子图G［E3］
第8章图的基本概念 Pc b C b d 图8.1.2
第8章 图的基本概念 图 8.1.2 e3 e2 e1 e 4 e 5 e e 7 6 a b d e G e 3 e 2 e 1 e4 a b d G1 c c e3 e 4 e 6 a b d e G2 c e4 e5 a d e G3
第8章图的基本概念 3.补图 定义81.3G为n阶简单图,由G的所有顶点和能使 G成为完全图的添加边所构成的图称为G的相对于完全 图的补图,简称G的补图,记作G 【例8.1.6】图81.3中G是G相对于Kn的补图。 对于补图,显然有以下结论
第8章 图的基本概念 3.补图 定义8.1.3 G为n阶简单图，由G的所有顶点和能使 G成为完全图的添加边所构成的图称为G的相对于完全 图的补图，简称G的补图，记作 。 【例8.1.6】 图8.1.3中 是G相对于Kn的补图。 对于补图,显然有以下结论： G G
第8章图的基本概念 K 图8.1.3
第8章 图的基本概念 图 8.1.3 G G K5
第8章图的基本概念 (1)G与G互为补图,即G=G (2)E(G)UEG)=E(完全图)且E(G)∩E(G) (3)完全图与n阶零图互为补图 (4)G与G均是完全图的生成子图
第8章 图的基本概念 （1）G与 互为补图，即 =G。 （2）E（G）∪E（ ）=E（完全图）且E（G）∩E（ ） = 。 （3）完全图与n阶零图互为补图。 （4）G与 均是完全图的生成子图。 G G G G G