具有n个顶点的有向无环图最多有多少条边？
具有n个顶点的有向无环图最多有n×（n—1）/2条边。 这是一个拓扑排序相关的问题。—个有向无环图至少可以排出一个拓扑序列，不妨设这n个顶点排成的拓扑序列为v1，v2，v3，„，vn，那么在这个序列中，每个顶点vi只可能与排在它后面的顶点之间存在着以vi为弧尾的弧，最多有n-i条，因此在整个图中最多有（n-1）+（n-2）+„+2+1=n×（n-1）/2条边。
举一反三
内容
- 0
具有n个顶点的有向图最多有（ ）条边。
- 1
一个具有n个顶点无向连通图最少有____条边,最多有____条边。
- 2
()有n个顶点的无向图至多有n(n-1)条边。
- 3
具有n个顶点的无向图最多有n(n—1)条边，最少有n-l条边。
- 4
有n个顶点的简单无向图最多有n(n-1)条边。