图的术语 第七章图 示例6如下是一个网 3 10 2 生成树:一个连通图G的子图如果是一棵包含G的所有 顶点的极小连通子图,则该子图称为G的生成树。所谓 极小是指边数最少。由于n个顶点的连通图至少有n-1条 边,而所有包含n-1边及n个顶点的连通图都是无回路的 树,所以生成树是无回路的树。若在生成树中去掉任何 条边,都会使之变为非连通图。若在生成树上任意添 加一条边,就必定出现回路。 第16页
第七章 图 第16页 示例6 如下是一个网 生成树：一个连通图G的子图如果是一棵包含G的所有 顶点的极小连通子图，则该子图称为G的生成树。所谓 极小是指边数最少。由于n个顶点的连通图至少有n-1条 边，而所有包含n-1边及n个顶点的连通图都是无回路的 树，所以生成树是无回路的树。若在生成树中去掉任何 一条边，都会使之变为非连通图。若在生成树上任意添 加一条边，就必定出现回路。 V1 V3 V2 V4 V5 11 10 3 2 8 6 5 4 ⚫ 图的术语
图的术语 第七章图 ( A B 示例7设有如下无向图G N86昌 910 3 则 图73无向图及其连通分量 图)无向图G是一个非连 B (2)无向图G有三个连通 分量,分别为 (3)图75是无向图G中大 连通分量的一棵生成树 注,一棵有n个顶点的生成图75 G 树有且仅有n-1条边,但是有n1 条边的图不一定是生成树。 第17页
第七章 图 第17页 示例7 设有如下无向图G 1 2 A 13 3 4 5 B L M C D E 12 6 7 8 F G H 9 10 11 I J K 则 图7.3 无向图及其连通分量 (1) 无向图G是一个非连 通图 (2) 无向图G有三个连通 分量，分别为 A B L M C F J D E I K G H (3) 图7.5是无向图G中大 连通分量的一棵生成树 A B L M C F J 注. 一棵有n个顶点的生成 图 7.5 树有且仅有n-1条边，但是有n-1 条边的图不一定是生成树。 ⚫ 图的术语
图的术语 第七章图 有向树:如果一个有向图恰有一个顶点的入度为0,其 余顶点的入度均为1,则是一棵有向树。 生成森林:一个有向图的生成森林由若干棵有向树组 成,含有图中全部顶点,但只有足以构成若干棵不相交的 有向树的弧。 示例8如下表示一个有向图及其生成森林 (A B C A F D F BC E 图76一个有向图及其生成森林 第18页
第七章 图 第18页 有向树：如果一个有向图恰有一个顶点的入度为0，其 余顶点的入度均为1，则是一棵有向树。 生成森林：一个有向图的生成森林由若干棵有向树组 成，含有图中全部顶点，但只有足以构成若干棵不相交的 有向树的弧。 示例8 如下表示一个有向图及其生成森林 A F E B D C F A B E D C 图7.6 一个有向图及其生成森林 ⚫ 图的术语
图的基本操作 第七章图 (1) Loc Vertex(G,y)顶点定位函数 确定顶点v在图G中的位置。若图中无此顶点,则返回函 数值0。 (2) Get Vertex(G,i)取顶点函数 求图G中第个顶点。若大于图G中的顶点数,则返回函 数值NULL (3) FirstAID(G,v)求第一个邻接点函数 求图G中顶点v的第1个邻接点。若v没有邻接点或图G中无 顶点v,则返回函数值0。 (4) NextADJr(G,V,w)求下一邻接点函数 已知w为图G中顶点v的某个邻接点,求顶点w的下一个邻 接点。若w是v的最后一个邻接点,则返回函数值0 5) Ins vertex(G,u)插入顶点操作 和图G中增添一个顶点u为图G的第n+1个顶点,其中n为插 入之前图G中所含顶点的个数 9贝
第七章 图 第19页 (1) LocVertex(G,v) 顶点定位函数 确定顶点v在图G中的位置。若图中无此顶点，则返回函 数值0。 (2) Get Vertex(G,i) 取顶点函数 求图G中第i个顶点。若i大于图G中的顶点数，则返回函 数值NULL。 (3) FirstADJ(G,v) 求第一个邻接点函数 求图G中顶点v的第1个邻接点。若v没有邻接点或图G中无 顶点v，则返回函数值0。 (4) NextADJ(G,v,w) 求下一邻接点函数 已知w为图G中顶点v的某个邻接点，求顶点w的下一个邻 接点。若w是v的最后一个邻接点，则返回函数值0。 (5) InsVertex (G,u)插入顶点操作 和图G中增添一个顶点u为图G的第n+1个顶点，其中n为插 入之前图G中所含顶点的个数。 ⚫ 图的基本操作
图的基本操作 第七章图 (6) InsAR(G,V,w)插入弧的操作 在图G中增添一条从顶点ⅴ到顶点w的弧 (⑦) Delvertex(G,y)删除顶点操作 在图G中删除顶点v以及所有与顶点ⅴ相关联的弧 (8) DelAro(G,v,w)删除弧的操作 在图G中删去一条从顶点v到顶点w的弧 以上有关图的若干基本操作,前四种不涉及图的 修改,后四种涉及图的修改。在后面讨论图的存储结 构及图的操作中,主要考虑图的前四种基本操作 第20页
第七章 图 第20页 (6) InsARC(G,v,w) 插入弧的操作 在图G中增添一条从顶点v到顶点w的弧。 (7) DelVertex(G,v) 删除顶点操作 在图G中删除顶点v以及所有与顶点v相关联的弧。 (8) DelARC(G,v,w) 删除弧的操作 在图G中删去一条从顶点v到顶点w的弧。 以上有关图的若干基本操作，前四种不涉及图的 修改，后四种涉及图的修改。在后面讨论图的存储结 构及图的操作中，主要考虑图的前四种基本操作。 ⚫ 图的基本操作