第一章图的基本概念 本次课主要内容 子图、图运算、路与连通性 (一)、子图的相关概念 (二)、图运算 (三)、路与连通性
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