顶点的度( degree) 子图( subgraph) 与该顶点相关联的边的数目 图G=(v,E),G=(V,E)中,若v≤V, 入度( in degree) E≤E,并且E中的边所关联的顶点都在v 出度( out degree) 中,则称图G是图G的子图 路径(path) 回路( cycle,也称为环) 从顶点v到顶点v的路径 ■无向图中,如果两个结点之间有平行边, 顶点序列vV,V2 容易让人误看作“环”) v,v使得(v,v1) 路径长度大于等于3 v)〔着 对有向图,则使得<v ■有向图两条边可以构成环,例如<V,V1> va>,<va;Ⅵa> 和<V,V>构成环 Va,v>)都在E中 简单路径( simple path) 路径长度( ength) 点叔新有,躺成舒鬼 权新有,轴彩光 有根图 ■简单回路( simple cycle) 个有向图中,若存在一个顶点 ■无环图( acyclic graph) v。,从此顶点有路径可以到达图 有向无环图( directed acyclic 中其它所有顶点,则称此有向图 graph,简写为DAG 为有根的图,V称作图的根 ■树、森林 值惠单 曰 权新有轴2 北京大学信息学院 ©版权所有，转载或翻印必究 Page 7 顶点的度（degree） „ 与该顶点相关联的边的数目 „ 入度(in degree) „ 出度(out degree) 北京大学信息学院 ©版权所有，转载或翻印必究 Page 8 子图（subgraph） „ 图G=(V，E)，G’=(V’，E’)中，若V’≤V， E’≤E，并且E’中的边所关联的顶点都在V’ 中，则称图G’是图G的子图 北京大学信息学院 ©版权所有，转载或翻印必究 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 北京大学信息学院 ©版权所有，转载或翻印必究 Page 10 回路（cycle，也称为环） „ 无向图中，如果两个结点之间有平行边， 容易让人误看作“环”） „ 路径长度大于等于3 „ 有向图两条边可以构成环，例如<V0，V1> 和<V1，V0> 构成环 V0 ╳ √ √ V1 √ 北京大学信息学院 ©版权所有，转载或翻印必究 Page 11 „ 简单回路（simple cycle） „ 无环图（acyclic graph） „ 有向无环图（directed acyclic graph，简写为DAG） 北京大学信息学院 ©版权所有，转载或翻印必究 Page 12 有根图 „ 一个有向图中，若存在一个顶点 V0，从此顶点有路径可以到达图 中其它所有顶点，则称此有向图 为有根的图，V0称作图的根 „ 树、森林