标记图形边缘

Question

给定一个图，问题是用三个数字标记其边，以使所有边的标签之和最小化。此外，对于每条标记为零的边，必须存在一条标记为非零的相邻边。最小边缘是多少？

Answer 1

不需要动态规划。一个简单的算法就可以完成这项工作。

请注意，连接到叶节点的边必须着色为 1。如果将这样的边着色为 0，则叶顶点上没有其他边可着色为 2（“对于每条着色为 0 的边，有必须存在用 2 着色的相邻边。" )

• 用 1 给每条边上色
• 循环A
  • 设置最大值=0
  • 设置 MAXEdge = 任意值
  • LOOP E 越过颜色 1 的边缘
    • 设置 S = 0
    • LOOP e 越过边到 E 两端的顶点
      • IF e 连接到叶子（度数为 1 的顶点）
        • 继续
      • 如果 e 没有着色 1
        • 继续
      • 设置S = S + 1
    • ENDLOOP e
    • 如果 S > 最大值
      • 设置最大值=S
      • 设置最大边缘 = E
  • 端环E
  • 如果最大值==0
    • 输出所有边缘颜色的总和
    • 停止
  • COLOR MAXEdge 颜色 2
  • LOOP e 越过边到 MAXEdge 两端的顶点
    • 如果 e 颜色 == 1
      • 用 0 给 e 上色
• 端环A