algorithm
Algoritmo delimitado por tiempo polinómico para la cobertura mínima de vértices
Buscar..
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 Pseudo Código
Algoritmo PMinVertexCover (gráfico G)
Entrada conectada grafo G
Conjunto de cubierta de vértice mínimo de salida C
Set C <- new Set<Vertex>()
Set X <- new Set<Vertex>()
X <- G.getAllVerticiesArrangedDescendinglyByDegree()
for v in X do
List<Vertex> adjacentVertices1 <- G.getAdjacent(v)
if !C contains any of adjacentVertices1 then
C.add(v)
for vertex in C do
List<vertex> adjacentVertices2 <- G.adjacentVertecies(vertex)
if C contains any of adjacentVertices2 then
C.remove(vertex)
return C
C es la cubierta de vértice mínima del gráfico G
podemos usar la clasificación de cubos para clasificar los vértices según su grado porque el valor máximo de grados es (n-1) donde n es el número de vértices, entonces la complejidad del tiempo de clasificación será O (n)
