• 2022-06-06
    具有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)条边。