logo标签列表

在有向加权图中寻找平均权重最高的树

graph
4
我正在寻找以下问题的算法：给定一个有向加权图 G，找到一个在 G 中的树 T，使得 T 的平均权重最大化。
有趣的问题。您能否提供有关图形假设和树约束的更多信息？是否有任何阻止我们仅使用最大权重的边和两个相应节点的树？ - Khaur
“T”的“平均”重量是什么意思？如果您说平均值为（在“T”中边缘权重的总和/“T”中边缘数），那么可以立即说选择具有最高权重的边缘。所以请您澄清一下。 - Reza
1个回答
0

  1. 给定一个图G

  2. 按升序排序边（最小权重优先）

  3. 剪切顶部边（最小权重的边）

  4. 剪切孤立的顶点

  5. 现在是一棵树吗？

    • 是：转到步骤6

    • 否：转到步骤3

  6. 返回G

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接