Considere un gráfico cúbico aleatorio conectado de n = | V | vértices, extraídos de G ( n , 3 -reg ) (como se define aquí , es decir, 3 n es par y cualesquiera dos gráficos tienen la misma probabilidad).
Por supuesto que hay posibles Búsquedas de amplitud primero, uno para cada nodo de inicio s ∈ V . Una búsqueda en anchura B G comenzando en el nodo s ∈ V asigna un nivel de d ( s , v ) a cada nodo v ∈ V , en donde d ( s , v ) es la distancia entre s y v en G .
Dada una búsqueda específica de Breadth First Search , deje que sea el número de aristas que se han asignado al nivel , y let . En otras palabras, es el número de bordes del nivel que contiene más bordes que cualquier otro nivel. Por último, dejar que sea el máximo para cualquiera de los de amplitud primero Búsquedas de .
Llamemos la amplitud de .
Pregunta
¿Cómo crece el valor esperado de cuando tiende al infinito? Recordemos que es aleatorio cúbico . Más precisamente, lo que realmente me gustaría saber es si el valor esperado de pertenece a .
Como es par, se considera el límite para que no me importen impares .
fuente
Respuestas:
La amplitud para gráficos expansores. Un gráfico aleatorio de 3 regulares es asintóticamente casi seguramente un gráfico expansor (ver Wikipedia) , por lo que la expectativa de la amplitud será , ya que la probabilidad de que no sea un gráfico expansor va a cuando va a .α(n)=Θ(n) Θ(n) 0 n ∞
Para un gráfico de expansión con el parámetro , para cualquier conjunto de vértices con , no son vecinos del conjunto. Ahora, deje que el número de vértices en el nivel sea , con . Entonces tenemos de la propiedad de expansión que mientras no sea demasiado grande (es decir, no hemos incluido la mitad de los vértices todavía) Ahora, busque el nivel que contiene el vértice . Es decir, entonces yβ s s≤n/2 βs j ℓj ℓ0=1 j
Si bien esta prueba analiza la cantidad de vértices en un nivel en lugar de la cantidad de aristas (sobre las cuales el OP preguntó), siempre hay al menos tantas aristas agregadas en el paso como vértices en el nivel , ya que se debe alcanzar cada vértice por alguna ventaja.i i
fuente
La respuesta de Peter Shor es realmente buena, pero hay otra forma de responder esto: probar que el ancho del árbol está limitado por dos veces la amplitud (la versión de vértice). Como sabemos que los expansores 3-regulares tienen un ancho de árbol lineal, hemos terminado.
Vea la construcción de la descomposición de un árbol dado un árbol BFS, es la diapositiva 15 de esta presentación: http://www.liafa.jussieu.fr/~pierref/ALADDIN/MEETING2/soto.pdf
Es fácil ver que el tamaño de cada bolsa está limitado por dos veces el nivel más ancho.
fuente