连接断开连接的图的组件的最低成本？
Minimum cost to connect components of a disconnected graph?
我们最初通过邻接矩阵给出了一个完全连接的图。然后，删除一些边，使图形断开连接，现在我们有了这个断开连接的图形的多个组件。连接所有组件所需的最低成本是多少？
设G = (V, E_1 ∪ E_2)为原始（加权、全连接）图，G' = (V, E_1)为删除集合E_2中的边得到的图。
考虑通过收缩 G' 的连通分量（即每个连通分量成为单个顶点）获得的图 G''，其中 G'' 的两个顶点是邻居当且仅当 G' 中相应的连通分量由 E_2 中的边连接。本质上，这意味着 G'' 的边是集合 E_2 中的边（从原始图中删除的边）。
观察到添加从 E_2 到 G' 的边的一个子集可以恢复 G' 的（完整）连通性当且仅当这些边连接来自 [=13= 的所有顶点时].最便宜的方法是在 G'' 上选择最小成本生成树（相对于边的权重）。根据您的评论，我假设您知道最小生成树是什么以及如何计算它。
一句话总结：
可以通过计算图上的最小（成本）生成树来找到恢复连通性所需的成本最小的一组边，该树是通过将每个连接的组件收缩成单个顶点而获得的，并且包含作为其边集, 从原始图中删除的边。
我们最初通过邻接矩阵给出了一个完全连接的图。然后，删除一些边，使图形断开连接，现在我们有了这个断开连接的图形的多个组件。连接所有组件所需的最低成本是多少？
设G = (V, E_1 ∪ E_2)为原始（加权、全连接）图，G' = (V, E_1)为删除集合E_2中的边得到的图。
考虑通过收缩 G' 的连通分量（即每个连通分量成为单个顶点）获得的图 G''，其中 G'' 的两个顶点是邻居当且仅当 G' 中相应的连通分量由 E_2 中的边连接。本质上，这意味着 G'' 的边是集合 E_2 中的边（从原始图中删除的边）。
观察到添加从 E_2 到 G' 的边的一个子集可以恢复 G' 的（完整）连通性当且仅当这些边连接来自 [=13= 的所有顶点时].最便宜的方法是在 G'' 上选择最小成本生成树（相对于边的权重）。根据您的评论，我假设您知道最小生成树是什么以及如何计算它。
一句话总结： 可以通过计算图上的最小（成本）生成树来找到恢复连通性所需的成本最小的一组边，该树是通过将每个连接的组件收缩成单个顶点而获得的，并且包含作为其边集, 从原始图中删除的边。