我有一个无向的非循环简单图，有 N 个节点和 N-1 边（所有节点都相互连接） .
N
N-1
删除边缘 E_i 将图形分成两个分别具有 M_i 和 N-M_i 节点的子图 .
E_i
M_i
N-M_i
我正在寻找一种搜索边缘 E_i 的算法，以找到最平等的节点分区：我想找到 min(max(M_i, N-M_i)) .
min(max(M_i, N-M_i))
什么是无向非循环连通图？那是对的，tree .
将树根植于任意顶点并计算每个顶点子树的大小 .
设m（i）是第i个顶点子树的大小 .
假设你有固定边（u，v），深度（u）<depth（v） . 然后，简单地计算max（m（v），N-m（v）） .
所有这些值中的最小值就是您的答案 .
我假设图表由边缘列表表示;从这里我们可以创建相应的节点列表及其相关的边缘 .
理由：
将每个节点视为自己的集群，权重为1 .
连续"merge"每个叶子节点进入其父节点，增加父节点的权重 .
在每次迭代中，构建可用的最轻的集群 .
继续，直到只剩下两个集群;连接它们的边缘是要移除的边缘 .
初始化：
将所有叶节点（顺序1）放入列表中 .
通过增加重量对列表进行排序 .
获取列表顶部的叶节点;将其合并到其父级（添加权重） .
如果结果节点现在是叶子，请将叶子插入列表中的适当位置 .
重复步骤3和4，直到只剩下两个节点;这些形成了所需的分区 .
2 回答
什么是无向非循环连通图？那是对的，tree .
将树根植于任意顶点并计算每个顶点子树的大小 .
设m（i）是第i个顶点子树的大小 .
假设你有固定边（u，v），深度（u）<depth（v） . 然后，简单地计算max（m（v），N-m（v）） .
所有这些值中的最小值就是您的答案 .
我假设图表由边缘列表表示;从这里我们可以创建相应的节点列表及其相关的边缘 .
理由：
将每个节点视为自己的集群，权重为1 .
连续"merge"每个叶子节点进入其父节点，增加父节点的权重 .
在每次迭代中，构建可用的最轻的集群 .
继续，直到只剩下两个集群;连接它们的边缘是要移除的边缘 .
初始化：
将所有叶节点（顺序1）放入列表中 .
通过增加重量对列表进行排序 .
获取列表顶部的叶节点;将其合并到其父级（添加权重） .
如果结果节点现在是叶子，请将叶子插入列表中的适当位置 .
重复步骤3和4，直到只剩下两个节点;这些形成了所需的分区 .