algorithm - 如何拆分图以最小化最长路径的长度

Question

给定一个图和一个数字 n，是否有一种算法可以通过删除 n 条边来拆分图，以最小化最长路径/直径的长度？

例如，如果我有以下图表:

A - B - C - D 
      \ E - F

并且 n = 2，您可能希望在以下之间切割图形:

• 乙和丙
• B和E

所以没有路径会超过 2。如果图是树/非循环无向图，这也有区别吗？

EDIT1:通过树/无环无向图更改重组图

Answer 1

对于非循环图的特定情况(我假设这就是您所说的“非重组”的意思)，您可以执行以下操作:

1. 运行 Topological Sorting对节点进行排序的算法。

2. 运行动态规划来解决您的问题。递归将是最小化(美国英语!)从节点 0 到节点 i 的最长分支，使用 j 切割。