标号图( abeled graph) 带权图( weighted graph) 3 15 4 V 6 北京大学信息学院 版权所有,转载或翻印必究 Page 6
北京大学信息学院 ©版权所有，转载或翻印必究 Page 6 标号图（labeled graph） 带权图（weighted graph）
顶点的度( degree) 与该顶点相关联的边的数目 入度( in degree) 出度( out degree) 北京大学信息学院 散权所伺,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 7 顶点的度（degree） 与该顶点相关联的边的数目 入度(in degree) 出度(out degree)
子图( subgraph) n图G=(V,E,G'=(V,E)中,若V≤V, E≤E,并且E中的边所关联的顶点都在V 中,则称图G是图G的子图 V 北京大学信息学院 版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 8 子图（subgraph） 图G=(V，E)，G’=(V’，E’)中，若V’≤V， E’≤E，并且E’中的边所关联的顶点都在V’ 中，则称图G’是图G的子图
路径(path) p 从顶点vp到顶点vq的路径 顶点序列V,vn,Va,… 使得(vn,V1) vn,V),…,(m,V)(若 对有向图,则使得<V, <v1;V12> <vn,v>)都在E中 ■简单路径( simple path) q 路径长度( length) 北京大学信息学院 版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 9 路径（path） 从顶点Vp到顶点Vq的路径 顶点序列Vp，Vi1，Vi2，…， Vin，Vq，使得（Vp，Vi1）， (Vi1，Vi2) ，…，(Vin，Vq)（若 对有向图，则使得<Vp， Vi1>，<Vi1，Vi2> ，…， <Vin，Vq>）都在E中 简单路径（simple path） 路径长度（length） Vp Vq
回路( cycle,也称为环) 无向图中,如果两个结点之间有平行边, 容易让人误看作“环”) 路径长度大于等于3 n有向图两条边可以构成环,例如<V,V1> 和<Ⅴ1,V>构成环 0 北京大学信息学院 @版权所有,转载或翻印必究 Page 10
北京大学信息学院 ©版权所有，转载或翻印必究 Page 10 回路（cycle，也称为环） 无向图中，如果两个结点之间有平行边， 容易让人误看作“环”） 路径长度大于等于3 有向图两条边可以构成环，例如<V0，V1> 和<V1，V0> 构成环 V0 ╳ √ √ V1√