Newsletter
Liste des sujets

Problème algorithmique / théorie des graphes

Jean_Python
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 ? :noel:

Message édité le 27 avril 2021 à 21:55:22 par Jean_Python
Sous forums
  • Religion