Algorithme pour calculer la longueur moyenne d'un chemin simple

Question

Compte tenu d'un graphique connecté et de deux nœuds S et T, il peut y avoir de nombreux chemins simples différents (sans cycles) de s à t.Y a-t-il un algorithme efficace pour trouver la longueur moyenne de ces chemins?

Answer 1

Je suppose que vous savez déjà qu'un algorithme polynomial pour compter le nombre de chemins simples entre deux nœuds impliquerait P= NP, ce résultat est due à Valiant (la complexité des problèmes de dénombrement et de fiabilité, 1979).

Imaginez maintenant, vous attendez à découvrir une contradiction, que vous pouvez calculer $ \ texte {avg} (g, u, v) $ en temps polynomial.

let $ g + l $ Soyez le graphique résultant de l'ajout d'un moyen simple de longueur $ l $ entre $ u $ et $ v $ in $ g $ . Ce nouveau chemin est composé de $ l-1 $ nouveaux nœuds et il n'interfère pas avec aucun chemin précédent de $ U $ à $ v $ , fourni $ l \ geq 2 $

.

.

alors, $ \ text {avg} (g + 3, u, v) - \ text {avg} (g + 2, u, u, v> = 1 $ / (\ # \ Text {Text {Chemins} (g, U, V) +1) $ , à partir de laquelle vous pouvez obtenir $ \ # \ text {chemins} (g, u, v) $ en temps polynomial. Mais nous savons que cela ne peut pas être fait dans le temps polynomial, une contradiction.