Definimos un modelo general de grafos que evolucionan de forma estocástica, a saber, los grafos que evolucionan estocásticamente de manera uniforme en los bordes. En este modelo, cada borde posible de un grafo estático general subyacente evoluciona de forma independiente, estando vivo o muerto en cada paso discreto de tiempo de evolución siguiendo una regla estocástica (Markoviana). La regla estocástica es idéntica para cada borde posible y puede depender de las observaciones pasadas del estado del borde. Examinamos dos tipos de caminatas aleatorias para un único agente que tienen lugar en dicho grafo dinámico: (i) La Caminata Aleatoria con Retraso (RWD), donde en cada paso, el agente elige (de forma uniforme al azar) un borde posible incidente, es decir, un borde incidente en el grafo estático subyacente, y luego espera a que el borde esté vivo para atravesarlo. (ii) La Caminata Aleatoria más natural en lo que está Disponible (RWA), donde el agente solo mira los bordes incidentes vivos en cada paso de tiempo y atraviesa uno de ellos de forma uniforme al azar. Nuestro estudio se centra en acotar el tiempo de cobertura, es decir, el tiempo esperado hasta que cada nodo sea visitado al menos una vez por el agente. Para RWD, proporcionamos una primera cota superior para los casos correlacionando RWD con una caminata aleatoria simple en un grafo estático. Además, presentamos una teoría de redes eléctricas modificada que captura el caso. Para RWA, derivamos algunas primeras cotas para el caso, reduciendo RWA a una caminata equivalente a RWD con un retraso modificado. Además, también proporcionamos un marco que se muestra para calcular el valor exacto del tiempo de cobertura para una familia general de grafos que evolucionan estocásticamente en tiempo exponencial. Finalmente, realizamos experimentos sobre el tiempo de cobertura de RWA en grafos uniformemente en bordes y comparamos los hallazgos experimentales con nuestras cotas teóricas.