Longitud promedio de las rutas st (simples) en un gráfico dirigido

Dado el hecho de que enumeración de la ruta - es un problema # P-completo, ¿podría haber métodos eficientes que calculen (o al menos aproximen) la longitud promedio de ruta - sin enumerarlos? ~~¿Qué pasa si se permite a los caminos volver a visitar los vértices?~~ $s$ $t$ $s$ $t$

Los resultados relevantes en gráficos especiales también podrían ser útiles.

algorithms complexity-theory graphs approximation enumeration liuyu
fuente

Si se permite que los caminos vuelvan a visitar los vértices, entonces un camino

no simple implica que no hay una longitud promedio, ya que la longitud tenderá al infinito.

s - t

$s-t$

Shaull

@Shaull, tienes razón. Estaba pensando en el tiempo de golpe de una caminata aleatoria de

. Pero la longitud promedio tiende al infinito sin más restricciones.

s

$s$

t

$t$

liuyu

esto parece estar muy avanzado, recomendamos migrar a cstheory

vzn

Si entiendo bien, esta pregunta podría ser de su interés para un gráfico especial.

Juho

parece que esto podría estar relacionado con el flujo máximo de red? También tenga en cuenta que para gráficos de mundo pequeño y varios otros gráficos con cierta simetría, tenderá hacia la longitud promedio de la ruta . un algoritmo bastante natural podría ser muestrear aleatoriamente las rutas

cortas y observar la desviación estándar de los resultados.

s

$s$

t

$t$

vzn

Respuestas: