Deje que sea un gráfico aleatorio en bordes. Con una probabilidad muy alta, tiene muchos ciclos. Nuestro objetivo es producir cualquiera de estos ciclos lo más rápido posible.
Suponiendo que tenemos acceso a en forma de lista de adyacencia, podemos tener éxito con probabilidad constante en el tiempo siguiente manera: seleccione cualquier nodo y comience a generar rutas aleatorias a partir de ; una vez que encontremos dos rutas distintas que comparten un punto final, habremos terminado. Hay puntos finales posibles, y para la paradoja del cumpleaños tendremos éxito con probabilidad constante después de descubrir de ellos.
¿Podemos hacerlo mejor? En particular, ¿es posible un algoritmo de tiempo constante que tenga éxito con probabilidad constante?
Respuestas:
No, no puedes superar las consultas de . Explicaré cómo formalizar el bosquejo de prueba de exfret de esto, de una manera que funcione para algoritmos adaptativos. Todo esto se anticipa en la respuesta de exfret; Solo estoy completando algunos de los detalles.Θ(n−−√)
Considere cualquier algoritmo (posiblemente adaptativo) que emita una secuencia de consultas, donde cada consulta es "buscar el borde la lista de adyacencia del vértice " o "probar si los vértices están conectados por un borde". Podemos suponer que no se repite ninguna consulta, ya que cualquier algoritmo que repita una consulta puede transformarse en uno que nunca repita ninguna consulta. Del mismo modo, podemos suponer que el algoritmo nunca realiza una consulta de conectividad en ningún par de vértices que ya se sabe que están conectados por un borde (es decir, probar cuando fue devuelto previamente por una consulta de recuperación en , o era previamente devuelto por una consulta de búsqueda eni v v,w v,w w v v w , o previamente probamos la conectividad de ).w,v
Supongamos que denota el evento de que, durante las primeras consultas, más de una consulta de búsqueda no devuelve ningún vértice , y ninguna consulta de búsqueda devuelve un vértice que fue consultado previamente, y que ninguna consulta de prueba de conectividad devuelve "conectado ". Demostraremos que si . De ello se deduce que ningún algoritmo que realice consultas puede tener una probabilidad constante de encontrar un ciclo 4.Ek k w Pr[Eq]=1−o(1) q=o(n−−√) o(n−−√)
¿Cómo probamos esto? Calculemos . Hay dos casos: o bien el ª consulta es una consulta traiga, o se trata de una consulta de prueba de conectividad:Pr[Ek|Ek−1] k
Si el ª consulta es una zona de alcance consulta en el vértice , hay vértices mencionados entre los primeros consultas, y si los ª consulta devuelve uno de los que entonces tendremos , de lo contrario tendremos . Ahora la respuesta a la ésimo consulta es uniformemente distribuida sobre un conjunto de vértices, donde contiene todos los vértices que no han sido devueltos por fetch consultas previas sobre , por lo que la respuesta a la ésimo consulta se distribuye uniformemente en un conjunto de tamaño al menosk v 2(k−1) k−1 k ¬Ek Ek k S S v k n−k+1 . La probabilidad de golpear al menos uno de estos es , por lo que en este caso, .≤2(k−1)/(n−k+1) Pr[Ek|Ek−1]≥1−2(k−1)/(n−k+1)
Si la ésima consulta es una consulta de prueba de conectividad, entonces .k Pr[Ek|Ek−1]≥1−1/n−−√
En cualquier caso, si tenemosq=o(n−−√)
Ahora,
Si , entoncesk≤q≤n−−√
entonces
El lado derecho es aproximadamente . Cuando , esto es .exp{−2q2/(n−q)} q=o(n−−√) 1−o(1)
En conclusión: cuando . De ello se deduce que necesita para tener una probabilidad constante de encontrar cualquier ciclo (y mucho menos un ciclo de 4).Pr[Eq]=1−o(1) q=o(n−−√) Ω(n−−√)
fuente
Supongamos que solo podemos consultar el borde de la lista de adyacencia de un vértice dado (que supongo que no está ordenado) o si dos vértices dados son adyacentes. En este caso, debería tomar consultas incluso para encontrar un ciclo. Esto se debe a que existe una probabilidad de que todas nuestras consultas del primer tipo devuelvan vértices diferentes y que todas nuestras consultas del segundo tipo devuelvan que los dos vértices no están conectados.i n−−√ 1−o(1)
Corríjame si estoy equivocado en algún lugar o si no entiendo el problema.
fuente