algorithm - 两个循环最多共享一个顶点的图标注

Question

早上好。我的朋友给了我一个有趣的图形问题，如下所示。

给定一个简单的图，其中两个循环最多共享一个顶点，如何用非负实数标记边，使得对于每个顶点，入射在其上的边的标签总和不超过给定常数（假设 K ) 并且图的所有边上的标签总和最大。提前感谢您的帮助。

Answer 1

呃，这是用大锤杀死一只苍蝇，但是就这样吧。

输入图的类别是禁止该次要的图的类别：

  *
 /|\
* | *
 \|/
  *

由于禁止次要是平面的，因此该类具有有界树宽，我们可以在线性时间内提取合适的树分解。一般分数匹配多面体是半整数的，所以存在一个最优解，边标签在{0, 1/2, 1}。我们可以对树分解使用动态规划来在线性时间内找到最优解。