■简单回路( simple cycle) 无环图( acyclic graph) 有向无环图( directed acyclic graph,简写为DAG) 北京大学信息学院 @版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 11 简单回路（simple cycle） 无环图（acyclic graph） 有向无环图（directed acyclic graph，简写为DAG）
有根图 一个有向图中,若存在一个顶点 Vo,从此顶点有路径可以到达图 中其它所有顶点,则称此有向图 为有根的图,V称作图的根 ■树、森林 北京大学信息学院 @版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 12 有根图 一个有向图中，若存在一个顶点 V0，从此顶点有路径可以到达图 中其它所有顶点，则称此有向图 为有根的图，V0称作图的根 树、森林
连通图 对无向图G=(V,E)而言,如 果从V1到V2有一条路径(从V2 到V1也一定有一条路径),则称 V1和V2是连通的 (connected) 强连通 北京大学信息学院 @版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 13 连通图 对无向图G=（V，E）而言，如 果从V1到V2有一条路径（从V2 到V1也一定有一条路径），则称 V1和V2是连通的 （connected） 强连通
连通分支或者连通分量 无向图的最大连通子图 强连通分支(强连通分量) 0 v5 北京大学信息学院 @版权所有,转载或翻印必究
北京大学信息学院 ©版权所有，转载或翻印必究 Page 14 连通分支或者连通分量 无向图的最大连通子图 强连通分支（强连通分量） v0 v5
网络 带权的连通图 3(4 15 北京大学信息学院 @版权所有,转载或翻印必究 Page 15
北京大学信息学院 ©版权所有，转载或翻印必究 Page 15 网络 带权的连通图