Partitionnement de graphes par des arbres sous contraintes de degré

Nous présentons une contrainte de partitionnement de graphe par des arbres sous contraintes de degré. Étant donné un graphe orienté G, la contrainte spécifie que toute solution est formée par N arbres, tels que le nombre de fils d'un sommet quelconque de G appartienne à un ensemble donné de valeurs. Il existe pour la contrainte d'arbre pure, introduite dans [2], une caractérisation complète polynomialement évaluable. Cependant, la prise en compte du nombre de fils de chaque sommet rend le problème d'existence d'une solution NP-complet. Nous montrons donc comment intégrer une relaxation polynomiale de la contrainte de degré, prenant en compte les différents aspects de la contrainte d'arbre pure. Enfin, nous présentons une première série de résultats partiels pratiques sur les problèmes (NP-complets) d'existence d'un chemin Hamiltonien et d'un arbre binaire couvrant dans le cas de graphes orientés quelconques