存在加權循環的複雜性

Question

假設加權圖G，頂點和邊被加權，並且給定常數k，那麼下面的決策問題A的複雜度是多少？

1-A：劑量G總容量爲K的容器循環嗎？
2-如果G是平面圖，A的複雜度是多少？

任何想法或指向論文或書籍也歡迎！

Answer 1

它是NP完全的，因爲您可以從平面Hamiltonian cycle減少單位重量和k = n。