algorithm
algorithme lié à un temps polynomial pour la couverture de vertex minimum
Recherche…
Introduction
Il s’agit d’un algorithme polynomial permettant d’obtenir la couverture de sommet minimum du graphe non dirigé connecté. La complexité temporelle de cet algorithme est O (n2)
Paramètres
| Variable | Sens |
|---|---|
| g | Graphique connecté non dirigé d'entrée |
| X | Ensemble de sommets |
| C | Ensemble final des sommets |
Remarques
La première chose à faire dans cet algorithme consiste à classer tous les sommets du graphe par ordre décroissant en fonction de leur degré.
Après cela, vous les répétez et ajoutez-les à l'ensemble des sommets finaux qui n'ont aucun sommet adjacent dans cet ensemble.
Au stade final, itère sur les sommets finaux et supprime tous les sommets dont l'un des sommets est situé dans cet ensemble.
Pseudo-code d'algorithme
Algorithme PMinVertexCover (graphique G)
Entrée connectée G
Ensemble de couverture de sommet minimum de sortie 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 est la couverture minimale du sommet du graphe G
on peut utiliser un tri par godet pour trier les sommets selon son degré car la valeur maximale des degrés est (n-1) où n est le nombre de sommets alors la complexité temporelle du tri sera O (n)