圖形標籤，其中兩個週期最多共享一個頂點

Question

早上好。我的朋友給了我一個有趣的圖形問題，如下所示。

給定一個簡單的圖，其中兩個週期至多共享一個頂點，如何用非負實數標記邊，使得對於每個頂點，入射到其上的邊的標籤總和不超過給定的常數（可以說K）和圖的所有邊上的標籤總和是最大的。感謝您的幫助提前。

Answer 1

呃，這是用大錘殺一隻蒼蠅，但是這裏就是這樣。

類輸入圖的是類禁止這個小圖的：

* 
/|\ 
* | * 
\|/ 
    * 

由於禁止未成年人是平面的，類已經有界樹寬，並且我們可以提取線性時間合適的樹分解。一般的分數匹配多面體是半積分的，因此存在邊緣標籤在{0,1/2,1}中的最優解。我們可以在樹分解中使用動態編程來在線性時間內找到最優解。