稀疏图( sparse graph):有向图 e<nlogn ·稠密图( dense graph):有向图e> nlogn 子图( subgraph): G=(VE)G2=(V,E),如V≤V且EE,则称G是G的子图 度( degree)、出度( OutDegree)、入度( Indegree) <uⅴ>称u邻接到v,或v邻接自u。邻接到某顶点的弧的数目称该顶 点的入度ID(v);邻接自某顶点的弧的数目称该顶点的出度ODu) 某顶点的入度、出度之和为该顶点的度TD(v) 路径和回路: 有向路径/无向路径,路径长度、回路或环 ·连通图和连通分量: 连通图(无向),强连通图(有向),连通分量 ·生成树和生成森林(所有顶点/连通图/无回路) pb(@ustc.edu.cn 中国科学技术大学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) • 路径和回路： – 有向路径/无向路径，路径长度、回路或环 • 连通图和连通分量： – 连通图(无向)，强连通图（有向），连通分量 • 生成树和生成森林(所有顶点/连通图/无回路)