有n个结点的有向连接图，最少有多少条边

对于一个有向图，最少有 0 条边，也就是说，所有节点之间都没有直接的连接。如果要求图是联通的（即任意两个节点之间都有路径相连），则最少需要 n-1 条边。这是因为，如果少于 n-1 条边，就会出现孤立的节点，无法与其他节点相连，而如果多于 n-1 条边，就会出现环路，无法构成有向树，也就无法保证联通性。

相关问题

多段图（关键路径算法）

### 多段图中的关键路径算法

在多段图中，关键路径是指从起点到终点具有最大权重和的一条或多条路径。这类问题通常用于项目管理等领域来识别哪些活动是按时完成项目的瓶颈所在。

对于多段图而言，其结构不同于一般的线性序列或树形结构，而是由多个阶段组成，每一段内的节点仅能连接至下一段的某些特定节点。为了计算这样的网络中的关键路径，可以采用动态规划的方法来进行处理[^1]。

#### 动态规划求解方法

通过定义状态转移方程，可以从最后一段向前逐步推导出各节点到达目标的最大时间开销：

设`f(i)`表示从第i个顶点出发到最后一个顶点所需最长时间，则有如下递推关系：

for i from n-2 downto 0 do
    f[i] = max{w(i,j)+f[j]} (j∈successors of node i)

其中`n`代表总的结点数目；`w(i, j)`是从结点`i`指向结点`j`边上的权值；而`max()`操作是在所有可能的目标结点之间取最大的那个值作为当前结点的最佳选择。

当完成了上述过程之后，就可以得到源点到汇点之间的最长路经长度即整个工程所需的最少工期。接着再回溯寻找具体的路径信息即可获得完整的临界路径列表。

#### 应用实例分析

假设存在一个多段无环加权有向图G=(V,E)，其中包含了五个不同的阶段S={s,V1,V2,V3,t}以及若干条带权边e(u,v)∈E。现在要找出该图内从起始位置`s`通往终止位置`t`的关键路径。

按照之前提到的方式构建相应的表格并填充各个子问题的结果，在此过程中不断更新最优解直到遍历完整张图表为止。最终不仅能够得知总耗时还知道具体经过了哪几个重要环节构成了所谓的“生命线”。