Dans ce mémoire, on s intéresse au problème du recouvrement de l ensemble des arêtes d un graphe par des sommets. Le problème étant di¢ cile à résoudre, donc on va se concentrer sur les méthodes approchées de résolutions ...