具有n个顶点的有向无环图最多有多少条边？ -题库考试答案搜索网

具有n个顶点的有向无环图最多有多少条边？

问答题

2022-01-02 06:50

查看答案

正确答案

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

试题解析

标签：数据结构计算机科学技术

感兴趣题目

●n个顶点的有向完全图中含有向边的数目最多为 (23) 。

n个顶点的强连通有向图G，最多有（）条边，最少有（）边。强连通图即是任何两个顶点之间有路径相通，当所有结点在一个环上时，必定是强连通图。

29条边的有向连通图，至少有（）个顶点，至多有（）个顶点，有29条边的有向非连通图，至少有（）个顶点。

具有7个顶点的有向图至少应有多少条边才可能成为一个强连通图（）。

在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。

在一个具有n个顶点的无向图中，要连接全部顶点至少需要（）条边。

在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（）条边。

具有n个顶点的连通图至少有多少条边？

要连通具有n个顶点的有向图，至少需要（）条边。

在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为（）。

对于具有n个顶点和e条边的有向图，在其对应的邻接链表中一共包含（）个表结点。