Selección aleatoria de árboles generadores en gráficas

Abstract

Resumen: Existen diversos procedimientos para seleccionar aleatoriamente árboles generadores en gráficas conexas no dirigidas, con tiempos esperados de ejecución Entre los órdenes 0(n log n) y O(n3)en los peores casos, donde n es el número de vértices en la gráfica. En este trabajo realizamos la localización efectiva y eficiente de árboles generadores mediante paseos aleatorios sobre dichas gráficas, con la finalidad de obtener un equilibrio entre el diámetro del árbol, la valencia de los vértices internos y el número de hojas de los árboles obtenidos. Para esto, proponemos el uso de diversas matrices de transición en cadenas de Markov, considerando diferentes distribuciones de probabilidad para las vecindades de vértices involucradas en el paseo aleatorio.