● 稀疏图 （sparse graph):有向图e<nlogn 。 稠密图(dense graph).:有向图e>nlogn 子图(subgraph) -G=(V,E),G'=(V,E')如V≤V且E≤E',则称G是G的子图 ·度(degree)、出度(OutDegree)、入度Indegree): <u,v>称u邻接到v,或v邻接自u。邻接到某顶点的弧的数目称该顶点的入度 Dy);邻接自某顶点的弧的数目称该顶点的出度OD(u);某顶点的入度、 出度之和为该顶点的度TD(v)】 路径和回路： 一有向路径无向路径，路径长度、回路或环 连通图和连通分量： 连通图（无向），强连通图（有向），连通分量 。 生成树、生成森林： 一连通图的生成树是极小连通子图。 有向图的生成森林由若干有向树组成，含有图中全部顶点和部分足以构成 若干颗不相交有向树的狐。 ypb@ustc.edu.cn 4 中国科学技术大学ypb@ustc.edu.cn 4 中国科学技术大学 • 稀疏图（sparse graph）：有向图e<nlogn • 稠密图（dense graph）：有向图e>nlogn • 子图（subgraph）: – G=(V,E),G’=(V’,E’),如V’≦V且 E≦E’,则称G’是G的子图 • 度(degree)、出度(OutDegree)、入度(Indegree): – <u,v>称u邻接到v，或v邻接自u。邻接到某顶点的弧的数目称该顶点的入度 ID(v)；邻接自某顶点的弧的数目称该顶点的出度OD(u)；某顶点的入度、 出度之和为该顶点的度TD(v) • 路径和回路： – 有向路径/无向路径，路径长度、回路或环 • 连通图和连通分量： – 连通图(无向)，强连通图（有向），连通分量 • 生成树、生成森林： – 连通图的生成树是极小连通子图。 – 有向图的生成森林由若干有向树组成，含有图中全部顶点和部分足以构成 若干颗不相交有向树的狐