简答题

具有n个顶点的强连通图至少有多少条边?这样的图应该是什么形状?

正确答案

具有n个顶点的强连通图至少有n条边,这样的图是一个由n个顶点构成的环。
强连通图是相对于有向图而言的。由于强连通图要求图中任何两个顶点之间能够相互连通,因此每个顶点至少要有一条以该顶点为弧头的弧和一条以该顶点为弧尾的弧,每个顶点的入度和出度至少各为1,即顶点的度至少为2,这样根据图的顶点数、边数以及各项点的度三者之间的关系计算可得:边数=2×n/2=n。

答案解析

相似试题
  • 具有n个顶点的连通图至少有多少条边?

    简答题查看答案

  • n个顶点的强连通图至少有()条边,其形状是()。

    填空题查看答案

  • G是一个非连通无向图,共有28条边,则该图至少有()个顶点。

    单选题查看答案

  • n个顶点的连通图至少有()边。

    填空题查看答案

  • 设G为具有N个顶点的无向连通图,则G至少有()条边。

    填空题查看答案

  • 设某强连通图中有n个顶点,则该强连通图中至少有()条边。

    单选题查看答案

  • n个顶点的强连通图的边数至少有()。

    单选题查看答案

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

    填空题查看答案

  • n个顶点的强连通图的邻接矩阵中至少有()个非零元素。

    单选题查看答案