algorithm
Algoritmo delimitado por tiempo polinómico para la cobertura mínima de vértices

.NET Framework C Language C# Language C++ Java Language JavaScript MATLAB Language PHP Python Language Ruby Language
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)



Modified text is an extract of the original Stack Overflow Documentation
Licenciado bajo CC BY-SA 3.0
No afiliado a Stack Overflow