3
A
回答
4
最大二分配匹配是一個二分圖中的一組邊,沒有兩個邊相鄰。最大獨立集是圖中的一組節點(頂點),沒有兩個頂點相鄰。
因此,您可以通過將二分圖中的每條邊轉換爲一個節點,然後在所有在原始圖中共享公共端點的新創建節點之間添加一條邊來將二分匹配問題轉換爲獨立集。那麼新圖中的最大獨立集合對應於原始問題中的最大二分配匹配。
相關問題
- 1. 將Outlook VBA轉換爲獨立腳本
- 2. 將獨立存儲集合轉換爲SQL
- 3. 將獨立的Javascript轉換爲小部件
- 4. 如何將HTML(CSS)轉換爲PDF使用JavaScript bowser獨立
- 5. 如何將perl + cpp轉換爲獨立應用程序
- 6. 將數據集轉換爲二進制
- 7. 將此雙重匹配轉換爲LINQ
- 8. 將字符轉換爲字符串的因子匹配部分
- 9. 如何將ZZ轉換爲二進制?
- 10. 如何將二進制轉換爲qpixmap
- 11. 如何將UCHAR轉換爲二進制
- 12. 最大獨立集合的二分圖
- 13. 將副本集轉換爲獨立服務器後遇到MongoDB警告
- 14. 如何將Vlookup轉換爲索引/匹配?
- 15. PHP:如何將正則表達式轉換爲示例匹配?
- 16. 如何將if-then-else轉換爲模式匹配?
- 17. 如何將T轉換爲類以匹配「where T:class」約束?
- 18. 如何用匹配的轉換替換重新匹配?
- 19. 二部圖中的最大加權獨立集合
- 20. 將獨立Java應用程序轉換爲可部署的Web應用程序
- 21. 如何將JavaPairRDD轉換爲數據集?
- 22. 如何將數組轉換爲集合
- 23. 如何將集合轉換爲列表?
- 24. 如何將IEnumerable轉換爲Subsonic集合?
- 25. 獨立的匹配值由連字符
- 26. 位置獨立字符串匹配
- 27. 將XBAP轉換爲獨立的WPF應用程序
- 28. 將Java嵌入式數據庫轉換爲獨立數據庫
- 29. ADA:將斜槓輸入轉換爲3個獨立整數
- 30. 將腳本轉換爲獨立處理多個表格