En ce moment :Genshin Impact, Valhalla, Breath of the wild, Animal Crossing, GTA 5, Red dead 2
PCPS5Xbox SeriesSwitch 2
Liste des sujets
Problème algorithmique / théorie des graphes
Jean_Python
Niveau 10
27 avril 2021 à 21:52:53
J'ai un graphe G( V, E, w) non orienté et pondéré, avec w: E-> |R+
et je cherche H un sous-graphe de G tel que: - les nœuds de H sont de degré 0 ou 1 - la somme des poids w des arêtes de H est maximale
Pas de contrainte sur son unicité, du moment que j'ai un sous-graphe qui correspond je suis content.
Je vois bien comment faire ça avec des méthodes classiques (backtracking ou autre), mais est-ce qu'il n’existerait pas déjà un algo sur étagère pour faire ça directement ?
Message édité le 27 avril 2021 à 21:55:22 par Jean_Python