← 全部问题具有 n 个顶点的强连通有向图的最大边数是多少？
具有 n 个顶点的强连通有向图的最大边数是
n(n−1)。这对应于一个完全有向图，其中每一对不同顶点都有双向的边。
理解与推导
- 识别顶点数 n。
- 应用最大边数公式：n(n−1)。
- 理解这是无向完全图边数 n(n−1)/2 的两倍。
例子
对于一个有 5 个顶点的有向图（n=5），最大边数是 5(5−1)=20。讲师解释说，每一对顶点可以有两个方向相反的边。
容易误解的地方
- 认为最大边数是 n(n−1)/2，这适用于无向图。
- 假设强连通图不能有最大边数。
相关问题
要判断一个有向图是否是强连通的，必须验证每一对顶点是否相互可达。如果发现哪怕一对顶点中一个无法到达另一个，该图就不是强连通的。
适用条件：图是有向图。；需要检查所有顶点对的相互可达性。
认识概念↗ 具有 n 个顶点的无向连通图至少有 n-1 条边。当图形成树结构时，达到这个最小值。
适用条件：图是无向图。；图是连通的。；图有 n 个顶点。
认识概念↗ 具有 n 个顶点的无向简单图的最大边数是 n(n−1)/2。当图是完全图时，达到这个最大值。
适用条件：图是无向图。；图是简单图（没有自环或同一对顶点之间的多重边）。；图有 n 个顶点。
连通图是指任意两个顶点之间都存在路径的无向图。如果有一对顶点之间没有路径相连，则该图称为非连通图。
适用条件：图是无向图。；判断标准是任意两个顶点之间是否存在路径。
认识概念↗ 具有 n 个顶点的强连通有向图至少有 n 条边。当图形成一个单一的有向环时，达到这个最小值。
适用条件：图是有向图。；图是强连通的。；图有 n 个顶点。
答案依据视频资料生成并经过独立核验。若有疑问，请核对原视频或联系原作者。