电子摊越女学 elveraityaf Bectrole Sclece and Techaology af Chaa 第一章图的基本概念 本次课内容 一、子图的相关概念 二、几种典型的图运算 三、路与连通性
第一章 图的基本概念 本次课内容 一、子图的相关概念 二、几种典型的图运算 三、路与连通性
电子科越女学 elveraity af Beetronle Sclence and Techaelogy af Cha /956 一、子图的相关概念 1、子图的概念 简单地说，图G的任意一非空部分（包括本身）都称为是图G的 的一个子图。定义如下： 定义1如果V(H)三V(G),E(H)sE(G), 且H中边的重数不超过G中对应边的条数，则称H为 G的子图，记为H三G 当 H三G,H≠G时，称H是G的真子图，记为 H
一、子图的相关概念 1、子图的概念 简单地说，图 G的任意一非空部分 (包括本身 )都称为是图 G 的 的一个子图。定义如下： 定义1 如果 ， 且H中边的重数不超过G中对应边的条数，则称H为 G的子图，记为 。 当 时，称H是G的真子图，记为
电子特越女学 veraitya Bectrole Sclece and TechaologyafChaa 1956 N3 N G V2 0 v3 V1 G1 69 G2
v 4 v 3 v 2 v1 v 4 v1 v 3 v 2 G 2 v1 G1 v1 v 4 G 3 G
电子摊越女学 elveraity af Beetronle Sclence and Techaelogy af Cha 1956 2、点与边的导出子图 ()图G的顶点导出子图 定义2如果V'三V(G),则以V为顶点集， 以两个端点均在V刀中的边集组成的图，称为 图G的点导出子图。记为：G[V门 例1如图所示，取P'={1,3,5},求G[]. 2 5 3 3 图G GIV']
2、点与边的导出子图 (1) 图 G的顶点导出子图 定义2 如果 ，则以 为顶点集， 以两个端点均在 中的边集组成的图，称为 图G的点导出子图。记为： . 例1 如图所示，取 ，求 . 1 2 3 4 5 图 G G V[ ] 1 3 5
ST 电子摊越女学 elveraity af Beetronle Sclence and Techaelogy af Cha 1956 (2)图G的边导出子图 定义3如果E'三E(G),则以E'为边集， 以E”中边的所有端点为顶点集组成的图，称为 图G的边导出子图。记为：G[ET. 例2如图所示，求G[ET。其中E'={13,24,35} 2 5 5 3 图G 3 G[E']
(2) 图G的边导出子图 定义3 如果 ，则以 为边集， 以 中边的所有端点为顶点集组成的图，称为 图G的边导出子图。记为： . 例2 如图所示，求 。其中 . 1 2 3 4 5 图G G E[ ] 1 2 3 4 5