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 de manière ad hoc en adaptant 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 ?

Oui ca existe. La structure que tu cherches est un maximum weight matching. L'algo est complique et est base sur une extension de l'algo de matching dans les graph bipartie. https://en.wikipedia.org/wiki/Maximum_weight_matching

Il y a une implementation dans networkX: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.matching.max_weight_matching.html

Génial, c'est exactement ça ! Merci beaucoup !

Et du coup j'aurais appris la définition d'un matching en théorie des graphes