Looking for algorithm Answers? Try Ask4KnowledgeBase
Looking for algorithm Keywords? Try Ask4Keywords
algorithmAlgoritmo delimitado por tiempo polinómico para la cobertura mínima de vértices
Introducción
Este es un algoritmo polinomial para obtener la cobertura mínima de vértice de un gráfico no dirigido conectado. La complejidad temporal de este algoritmo es O (n2).
Parámetros
| Variable | Sentido |
|---|---|
| sol | Entrada conectada grafica no dirigida |
| X | Conjunto de vértices |
| do | Conjunto final de vértices |
Observaciones
Lo primero que debe hacer en este algoritmo para obtener todos los vértices de la gráfica ordenados en orden descendente según su grado.
Después de eso, hay que iterar en ellos y agregar cada uno al conjunto de vértices finales que no tienen ningún vértice adyacente en este conjunto.
En la etapa final, itere en el conjunto de vértices finales y elimine todos los vértices que tengan uno de sus vértices adyacentes en este conjunto.
Algoritmo delimitado por tiempo polinómico para la cobertura mínima de vértices Ejemplos relacionados
This modified text is an extract of the original Stack Overflow Documentation created by following contributors and released under CC BY-SA 3.0
This website is not affiliated with Stack Overflow
Email: tutorialpedia@outlook.com