设某强连通有向图中有 n 个顶点,则该强连通图中 至少有()条边。
在有向图中,如果存在一条从顶点u到顶点v的路径以及一条从顶点v到顶点u的路径,则称这两个顶点是强连通的。一个有向图被称为强连通图,如果图中的每一对顶点都是强连通的。
对于一个包含n个顶点的强连通有向图:
最少边的数量:我们可以找到一种构造方法使得边的数量最小。这种方法就是创建一个环形结构,所有的顶点都连接在一起形成一个循环。这样,每个顶点都有出度和入度至少为1,满足了强连通的条件。因此,在这种情况下,最少需要 n 条边来构成一个包含n个顶点的强连通有向图。
最多边的数量:我们可以通过构造一个完全有向图来使边的数量最多。在完全有向图中,每对不同的顶点之间都有一条方向任意的边。因此,在这种情况下,最多需要 n*(n-1) 条边来构成一个包含n个顶点的强连通有向图。