5
這可能是一個愚蠢的問題，但什麼是規範問題，要求圖的頂點的最小集合，以便從這些頂點，所有其他頂點可以通過「旅行」達到不超過一個邊緣？ 現實生活中的應用可能是：我需要知道哪些人才能與這個星球上的其他人相連一度？ 謝謝！允許以最大值到達所有其他頂點的最小頂點集合。一個邊
A
回答
3
我認爲這是Dominating Set Problem，與正常套蓋問題密切相關
相關問題
- 1. 如何在有向圖中找到最小的一組頂點，以便可以達到所有其他頂點
- 2. 圖 - 找到從所有其他頂點可到達的頂點
- 3. 在有向圖中找到可以從其中得到其他頂點的最小頂點數
- 4. 在圖中找到一組頂點，使每個頂點可以到達其他k個頂點
- 5. 最小化多邊形頂點
- 6. 有向圖中從一個頂點到另一個頂點的最短路徑
- 7. 最小VS最小頂點覆蓋
- 8. 如何從一個頂點獲得邊緣屬性的最大值的邊緣
- 9. OrientDB是否允許一個或多個頂點的多條邊？
- 10. 如何找到最大度數的圖中的所有頂點？
- 11. 如何記錄從源頂點到目標頂點的所有最短路徑
- 12. 刪除頂點和頂點本身的所有邊
- 13. 具有頂點權重和邊權重的最小Spanninjg樹
- 14. 最小切割頂點/節點 - 不是邊線
- 15. OrientDB查詢結果集與邊的空收集頂點，頂點
- 16. 矩形中的最大和最小頂點
- 17. 允許相對字體大小達到特定的最大值
- 18. 調整大小一個div依託其頂點的一個
- 19. C++：是一個圖ADT應該有一個頂點的列表和一個邊的列表，或只是指向其他頂點的頂點？
- 20. 如何使用graph.coreness找到頂點所屬的最大k-core
- 21. 使有向圖中的最小邊+節點值最大化
- 22. 如何爲Hazelcast Jet制定一個優雅的頂點以獲得最小值？
- 23. 查找最小頂點給定匹配最大值的二分圖覆蓋
- 24. 最大流量 - 通過頂點 - 如何？
- 25. 如何找到從某個頂點到達的所有邊的總和？
- 26. 將多邊形頂點數組「匹配」到另一個頂點的最佳方法？
- 27. 爲什麼一個頂點的着色與其他頂點不同？
- 28. 使用igraph查找連接到頂點的所有頂點？
- 29. 具有多個根頂點的圖中的最小生成樹
- 30. 從給定集合中查找具有最大點密度的最小圓點