61图的基本概念(续) 标号图( labeled graph) 带权图( weighted graph) 15 北京大学信息学院 版权所有,转载或翻印必究 Page 6
北京大学信息学院 ©版权所有，转载或翻印必究 Page 6 6.1 图的基本概念（续） ◼ 标号图（labeled graph） ◼ 带权图（weighted graph）
61图的基本概念(续) 顶点的度( degree) 与该顶点相关联的边的数目 入度( n degree 出度( out degree) ■子图( subgraph) 图G=(V,E,G’=(V,E)中,若V≤V, E’≤E,并且E中的边所关联的顶点都在v 中,则称图G是图G的子图 北京大学信息学院 版权所有,转载或翻印必究 Page 7
北京大学信息学院 ©版权所有，转载或翻印必究 Page 7 6.1 图的基本概念（续） ◼ 顶点的度（degree） ◼ 与该顶点相关联的边的数目。 ◼ 入度(in degree) ◼ 出度(out degree) ◼ 子图（subgraph） ◼ 图G=(V，E)，G’=(V’ ，E’)中，若V’≤V， E’≤E，并且E’中的边所关联的顶点都在V’ 中，则称图G’是图G的子图
61图的基本概念(续) a路径(path) 在图G=(v,E)中,如果存在顶点序列v vn,Va,…,Vn,V,使得(v,V1) Vn,V)(若对有向图 则使得<vp,V1>,<Vn,v2>,…,<Vn V>)都在E中,则称从顶点v到顶点v存 在一条路径 简单路径( simple path) 路径长度( length) 北京大学信息学院 版权所有,转载或翻印必究 Page 8
北京大学信息学院 ©版权所有，转载或翻印必究 Page 8 6.1 图的基本概念（续） ◼ 路径（path） ◼ 在图G=(V，E)中，如果存在顶点序列Vp， Vi1，Vi2，…，Vin，Vq，使得（Vp，Vi1）， (Vi1，Vi2) ，…，(Vin，Vq)（若对有向图， 则使得<Vp，Vi1>，<Vi1，Vi2> ，…，<Vin， Vq>）都在E中，则称从顶点Vp到顶点Vq存 在一条路径。 ◼ 简单路径（simple path） ◼ 路径长度（length）
61图的基本概念(续) 回路( cycle,也称为环) 简单回路( simple cycle) 无环图( acyclic graph) 有向无环图( directed acyclic graph,简写为DAG 北京大学信息学院 版权所有,转载或翻印必究 Page 9
北京大学信息学院 ©版权所有，转载或翻印必究 Page 9 6.1 图的基本概念（续） ◼ 回路（cycle，也称为环） ◼ 简单回路（simple cycle） ◼ 无环图（acyclic graph） ◼ 有向无环图（directed acyclic graph，简写为DAG）
61图的基本概念(续) 有根的图 个有向图中,若存在一个顶点v,从此顶点 有路径可以到达图中其它所有顶点,则称此有 向图为有根的图,V称作图的根。 连通的( connected) 对无向图G=(V,E)而言,如果从V1到V2有 条路径(从V2到V1也一定有一条路径) 称V1和V2是连通的( connected) 强连通 北京大学信息学院 版权所有,转载或翻印必究 Page 10
北京大学信息学院 ©版权所有，转载或翻印必究 Page 10 6.1 图的基本概念（续） ◼ 有根的图 ◼ 一个有向图中，若存在一个顶点V0，从此顶点 有路径可以到达图中其它所有顶点，则称此有 向图为有根的图，V0称作图的根。 ◼ 连通的（connected） ◼ 对无向图G=（V，E）而言，如果从V1到V2有 一条路径（从V2到V1也一定有一条路径），则 称V1和V2是连通的（connected） 。 ◼ 强连通