questa è probabilmente una domanda stupida, ma qual è il problema canonico che richiede il set minimo di vertici da un grafico, in modo che da questi vertici tutti gli altri vertici possano essere raggiunti "viaggiando" non più di uno bordo? L'applicazione della vita reale sarebbe: Quali persone ho bisogno di sapere, di essere connesso a tutti gli altri sul pianeta con un solo grado? Grazie!Set minimo di vertici che consente di raggiungere tutti gli altri vertici in max. un lato
5
A
risposta
3
Penso che sia lo Dominating Set Problem, strettamente correlato al normale problema di copertura set
Problemi correlati
- 1. È possibile accedere a tutti i vertici in un poligono in uno shader di vertici?
- 2. Algoritmo per trovare l'albero di spanning minimo dei vertici scelti
- 3. Programmazione lineare: trovare tutti i vertici ottimali
- 4. Trova il taglio minimo in un grafico tale che i vertici dati siano disconnessi
- 5. R igraph - specifica lo spazio minimo tra i vertici
- 6. Calcolo dei vertici di un rettangolo ruotato
- 7. OrientDB: trova tutti i vertici che non hanno un vertice diretto di una data classe
- 8. R igraph rinomina i vertici
- 9. Spanning tree che riduce al minimo il numero di vertici connessi a più spigoli?
- 10. Modificare i vertici in un oggetto THREE.BufferGeometry
- 11. Utilizzo di più buffer di vertici in DX10/DX11
- 12. Trova tutti i percorsi tra due vertici (nodi)
- 13. vertici correttamente a colori in R IGRAPH
- 14. Gruppo vertici in cluster utilizzando NetworkX
- 15. Riduci a icona Poligono Vertici
- 16. Colorare heightmap facce anziché vertici
- 17. Verifica se un elenco di vertici contiene un oggetto
- 18. aggiunta di vertici personalizzati a un grafico di incremento
- 19. Come accedere ad altri vertici in un programma vertex shader in opengl es 2?
- 20. tre js vertici non aggiornati
- 21. condizionale rimozione di vertici in base agli attributi di r
- 22. Come assegnare immagini diverse a diversi vertici in un igraph?
- 23. OpenGL garantisce che le primitive in un buffer di vertici vengano disegnate in ordine?
- 24. Script Blender: Indici dei vertici selezionati
- 25. OpenGL: attributo singolo vertice per più vertici?
- 26. openGL di base, buffer di vertici e pyglet
- 27. Trova il centroide di un poligono con i vertici ponderati
- 28. Gestione dei file .obj: Perché è possibile avere più vertici (vt) rispetto ai vertici (v)?
- 29. Python igraph: cancella i vertici da un grafico
- 30. Aggiunta dinamica di vertici a una riga in Three.js