Une question hypotétique. Dites que l'on me donne un arbre T et une liste de paires de nœuds (x, y) dans T. On me demande combien de paires je peux connecter simultanément (connecter x avec y) en utilisant chaque arête en T au plus une fois .Connexion de nœuds dans un arbre
Comment le ferait-on?
Il n'est pas NP-difficile pour les arbres. Vous pouvez faire ce qui suit, par exemple.
Racine l'arbre arbitrairement.
Pour chaque sommet v, calculez la solution optimale qui est confinée au sous-arbre de v.
De plus, pour chaque v, pour chaque chemin p qui inclut le bord parent de v, calculez la solution optimale qui est confinée à la sous-arborescence de v sauf pour le chemin p.
(2) et (3) peuvent être calculés en utilisant les solutions aux problèmes plus petits dans le sous-arbre de v. Il est probablement plus facile de regarder les étapes 1, 2 et 3, et de déterminer la récurrence vous-même, mais juste pour vous donner une idée, (2) peut être calculé en prenant le maximum de plusieurs solutions: une qui somme les solutions pour les enfants de v (c.-à-d. la somme des solutions produites à l'étape 2 pour chaque enfant), et une pour chaque chemin qui inclut v plus les solutions de l'étape 2 pour les autres enfants (cela comprend essentiellement ou deux solutions produites à l'étape 3 pour les enfants de v, plus la somme des solutions produites à l'étape 2 pour les autres enfants).
Il semble que vous décrivez le problème du voyageur de commerce? Où vous essayez de visiter autant de nœuds que possible sans utiliser deux fois le bord? C'est NP-difficile, et l'objet de nombreuses recherches. http://en.wikipedia.org/wiki/Travelling_salesman_problem – TZHX
@TZHX Non, je pense que par paires de nœuds, il signifie chemins. Il veut donc maximiser le nombre de chemins donnés qui sont disjoints. – marcog
@marcog, vous avez raison. C'est exactement ce que je veux! – Alexander