Le problème du recouvrement d un graphe par des sommets

Abstract

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 : quatre heuristiques seront présentées plus loin. Toutes ces méthodes ont été programmées en language Matlab et une étude comparative a été faite pour pouvoir apprécier de l e¢ cacité de ces méthodes.