§6.1.1图的概念 10.生成树 无回路的连通的无向图的生成图,称为该无 向图的生成树 定理6-1生成树中边的个数为结点个数 减1 a a b 16
16 §6.1.1 图的概念 10．生成树 无回路的连通的无向图的生成图，称为该无 向图的生成树。 【定理 6-1】生成树中边的个数为结点个数 减1. a b c d a b c d a b c d
s6.12图的基本操作 ①检索: 按结点(编号或内容)检索结点(位置) 按边的两顶点检索边 ②插入: 插入结点 插入边 ③删除 删除结点及与其关联的边 删除边 17
17 §6.1.2 图的基本操作 ①检索： ·按结点（编号或内容）检索结点（位置） ·按边的两顶点检索边 ②插入： ·插入结点 ·插入边 ③删除： ·删除结点及与其关联的边 ·删除边
86.1.2图的基本操作 ④求邻接点、关联边 ⑤求度(入度与出度) ⑥求路径 ⑦求子图 ⑧求生成图 ⑨求生成树 ⑩求连通分量 18
18 §6.1.2 图的基本操作 ④求邻接点、关联边 ⑤求度（入度与出度） ⑥求路径 ⑦求子图 ⑧求生成图 ⑨求生成树 ⑩求连通分量
86.1.2图的基本操作 )求拓扑序列(有向图) 2图的遍历 3求关键路径 4求最短路径 5求最小生成树
19 §6.1.2 图的基本操作 ⑾求拓扑序列（有向图） ⑿图的遍历 ⒀求关键路径 ⒁求最短路径 ⒂求最小生成树 …………
§62图的抽象对象模型 考虑仅从逻辑关系出发时,图结点和整个图对 象应具有的性质 由于图结点的关系不象其他结构中结点那样有 限制,所以它的抽象结构比较复杂 20
20 §6.2 图的抽象对象模型 • 考虑仅从逻辑关系出发时，图结点和整个图对 象应具有的性质 • 由于图结点的关系不象其他结构中结点那样有 限制，所以它的抽象结构比较复杂