Grupo de teoría de la optimización; álgebra abstracta relevante?

Question

Supongamos que una chica, llamada Alicia se pierde de la casa. Donde todo su entorno geográfico, incluyendo a sí misma y a la posición de su casa puede ser modelado como particular vértices en un grafo $G$ tales que cada arista $G$ se corresponde con un camino que Alice puede caminar hacia abajo como ella intenta encontrar su camino a casa. Sin embargo, Alice se encuentra en el teléfono con su amigo Bob, que está tratando de dar sus instrucciones para volver a casa basado en lo que ella le dice de su entorno actual, sin embargo, Alice puede ver sólo los vértices adyacentes a ella y por lo Bob debe intentar su mejor basado en su descripción del lugar en donde ella es ayudarlo a navegar de vuelta a casa.

Ahora mi objetivo es optimizar el gráfico de $G$ sea tan duro como sea posible para Alice para llegar a casa. Después de repensar esto varias veces, yo no puedo ayudar pero creo que implica la teoría de grupo que parece extraño en este contexto particular, como no he usado álgebra abstracta en relación con los problemas de esta naturaleza antes. A pesar de que, en cualquier caso, mi tren de pensamiento fue:

Tratamos de diseñar un gráfico basado en las restricciones que se me había dado, que el conocimiento de los vecinos de cualquier vértice da como un poco de información estructural sobre el que los vértices posiciones con respecto a la gráfica como un todo, de esta manera desde que Alice sólo puede ver los objetos geográficos adyacentes a ella, un gráfico, para satisfacer esta propiedad sería el de asegurar Alice transmite poca información acerca de su posición como sea posible a Bob.

Sin embargo, si el gráfico tiene una gran automorphism grupo, o es "vértice transitiva", a continuación, desde cualquier vértice puede ser asignado a cualquier otro vértice a través de un bijective mapa. Esto haría que las posiciones (vértices) esencialmente indistinguibles a los objetos (vértices ) junto a Alice.

Así que estoy pensando en los más "transitiva" yo hago las gráficas automorphism grupo, el menos información Alice va a tener sobre su posición geográfica relativa a $G$, lo que significa menos información puede ser dada a Bob, lo que significa que Alice es probable que permanecer perdido más de ser incapaz de dar mucho de una descripción de su entorno basado en la estructura de vértices adyacentes.

Aunque no estoy totalmente seguro de que voy a la interpretación transitiva grupo de acciones correctamente y también el hecho de que la teoría del grupo está por venir en un problema de optimización parece un poco raro para mí, así que creo que podría estar buscando en el problema equivocado. Es mi vaga intuición corerct? O soy yo (probablemente) la interpretación de la relación entre los gráficos de automorfismos y vértices individuales relativa distinguir-con la capacidad de sus vecinos mal?

Answer 1

Conceptos como el vértice de la transitividad y la automorphism grupo de un gráfico parece abordar un problema un poco diferente. Supongamos que Alice, desde donde ella está de pie, se ve toda la estructura de $G$, pero no puede decirle a los vértices de distancia en términos absolutos: ella sólo puede describir los mismos en relación a su posición actual. (Supongo que todavía desea Alice deberá estar lo suficientemente cerca de un vértice antes de que ella se pueden identificar como su casa; de lo contrario, que sólo podía ir allí.)

En ese caso, los dos vértices son indistinguibles, según esta descripción, si no hay un gráfico de isomorfismo que tiene un vértice a otro. En particular, si el gráfico es de vértice transitiva, entonces no hay dos vértices son distinguibles, y Bob no puede dar a Alice algún consejo útil.

En su caso, Alice sólo tiene información local sobre el gráfico, y que no hay necesidad de ser un isomorfismo de toda la gráfica para hacer dos vértices indistinguibles. La versión más simple del problema es cuando Alice puede contar el número de aristas/carreteras fuera de su ubicación actual, pero no puede ver lo que los destinos aspecto. (Tal vez sería capaz de reconocer a uno de ellos como la casa, tal vez no; esto no cambia el problema.)

En este caso, los dos vértices son indistinguibles si tienen el mismo grado. Un gráfico regular es aquel en el que todos los vértices tienen el mismo grado, y así todos los vértices se parecen, y Bob no puede ayudar a Alice a encontrar el hogar.

Finalmente, podemos dar a Alice un poco más de potencia. Tal vez Alice puede ver en los vértices adyacentes y ser capaz de contar sus grados. O tal vez ella puede ver a a $k$ pasos de distancia, para algunos $k$.

Yo no soy consciente de que un término para los "casos difíciles" de este problema en general, pero de una manera que nos podría hacer que el problema es de difícil mirando regular gráficos con un mínimo grosor. La circunferencia de un gráfico es la duración del ciclo más corto. Si Alice se encuentra en un $r$-gráfico regular con la circunferencia $2k+1$, entonces ella siempre se ve la misma cosa cuando se está de pie en cualquier vértice: "hay $r$ los vértices vecinos; cada uno de ellos ha $r-1$ otros vecinos, y cada uno de los que ha $r-1$ otros vecinos, y así sucesivamente, y esas son todas diferentes."

Regular los gráficos con gran circunferencia no son difíciles de encontrar. De hecho, una elegida al azar, $r$- gráfico regular en $n$ vértices tendrá sólo un número constante de ciclos de longitudes $3, 4, \dots, 2k$ $n$ va al infinito: esto significa que sólo una pequeña fracción de los vértices en la gráfica se ven diferentes desde el aburrido uniforme de la descripción anterior. Con una probabilidad constante (dependiendo $k$), no habrá tales ciclos, y todos los vértices tienen el mismo aspecto a Alice.