2
這裏我有一個有向圖G.我需要確定是否存在一組頂點不交集循環，以便每個頂點屬於一個循環。一組頂點不交疊循環，以便每個頂點屬於一個循環
我不確定這是否可以在多項式時間或如果它的NP完成？任何人都可以向我指出正確的方向嗎？
A
回答
4
將每個頂點分成一個「in」頂點和一個「out」頂點。然後一個頂點不相交的週期覆蓋對應於該圖上的完美匹配。你可以找到你的問題的答案一樣快，你可以找到完美的匹配（即多項式時間）
相關問題
- 1. 查找屬於簡單循環一部分的所有頂點
- 2. jquery點擊一個循環？
- 3. 使用for循環加載頂點
- 4. 在圖中找到一組頂點，使每個頂點可以到達其他k個頂點
- 5. 如何循環遍歷圖的頂點而不是爲每個頂點分別添加add.vertex？
- 6. 對於每個循環---> For循環
- 7. 對於一個圖，假設一個頂點有一個循環，爲什麼頂點的度數是2而不是1？
- 8. 對於每一個循環SQL
- 9. 對於每一個循環，閱讀行
- 10. 「對於每一個」循環：在Vb.net
- 11. WordPress多個循環 - 每個帖子頁面頂部顯示的第一個循環
- 12. 節點腳本（一個循環內循環）運行內存
- 13. 循環一個JSON腳本並應用於不同的DIVS每個循環
- 14. PHP循環，在除最後一個循環以外的每個循環之後添加一個逗號
- 15. 無法點擊每個利用對於每個循環
- 16. Python：繼續從一個點循環
- 17. 看起來像我的每個循環不止一次循環
- 18. 節點js同步每個循環
- 19. jQuery點擊每個循環內
- 20. 循環遍歷每個xml節點
- 21. 我該如何爲這個程序編寫一個循環，以便每次都返回頂部？
- 22. 生成元組以循環遍歷一個循環
- 23. JQuery - 從一個點循環遍歷每個類的案例
- 24. 在有向圖中找出一個循環中的所有頂點
- 25. 如何從外頂點列表中刪除循環頂點列表
- 26. 循環，從一個數組
- 27. JS循環，遞增每3個循環，而是由一個
- 28. 速度更快：將一個數組傳遞給一個類，併爲每個循環做一個循環，或者對每個循環做一個類
- 29. 對於循環語法錯誤 - 一次點擊貫穿整個循環
- 30. 嵌套的foreach循環，第一個循環不循環
你能舉個例子嗎？ – bubakazouba