Arbre couvrant qui minimise une «métrique» dynamique

Question

Laissez-nous un graphique. Lorsque nous supprimons un bord, 2 «voitures» sont créées, une de chaque verti du bord. Lorsque ces 2 voitures se rencontrent, elles s'arrêtent. Le problème est de créer un arbre couvrant de sorte que la somme des nombres de voitures qui traversent chaque verti est minime.

La difficulté supplémentaire est que si un verti a des voitures qui en découlent, alors le coût est k ^ n et non n * k.

quelques idées. Nous pourrions trouver les cycles sans accord les plus courts comme début, mais la position de ces cycles sans accord, c'est-à-dire qu'ils se touchent, changent la métrique et donc quel est le cycle le plus court.

Ce n'est pas un problème minimum d'arbre couvrant. Je veux résoudre ce problème car chaque voiture représente une vardiable et l'arbre couvrant est le moyen le plus efficace de calculer un problème d'optimisation. Lorsque 2 voitures du même bord se rencontrent et s'arrêtent, j'ai une réduction d'une vardiable de l'optimisation.

Éditer:

Le processus est comme ça. Nous supprimons un certain nombre de bords pour faire du graphique un arbre couvrant. Chaque bord supprimé crée 2 voitures, une à chaque verti du bord retiré, qui doivent se rencontrer. Nous fixons un chemin pour chacune de ces voitures jumelles. Nous vérifions ensuite combien de voitures (à partir de tous les bords que nous avons supprimés) passent par chaque verti. Si le nombre de voitures qui passe d'un verti est n, le coût est k ^ n où k est une constante. Nous ajoutons ensuite tous les coûts et c'est le coût mondial qui doit être minimisé.

Veuillez me dire si quelque chose n'est pas clair.https://mathoverflow.net/questions/86301/spanning-tree-that-minizes-a-dynamic-metric