简答题

具有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条边。

答案解析

相似试题
  • 具有n个顶点的有向图最多有()条边。

    单选题查看答案

  • 一个具有n个顶点的有向图最多有()条边。

    单选题查看答案

  • 用深度优先遍历方法遍历一个有向无环图,并在深度优先遍历算法中按退栈次序打印出相应的顶点,则输出的顶点序列是()。

    单选题查看答案

  • 证明:只要适当地排列顶点的次序,就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0。

    简答题查看答案

  • 5个顶点的无向图最多有()条边。

    单选题查看答案

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

    填空题查看答案

  • 在一个具有n个顶点的无向完全图中,包含有()条边;在一个具有n个顶点的有向完全图中,包含有()条边。

    填空题查看答案

  • 在一个具有n个顶点的无向完全图中,包含有()条边,在一个具有n个顶点的有向完全图中,包含有()条边。

    填空题查看答案

  • 在一个具有n个顶点的有向完全图中,包含有()条边。

    填空题查看答案