Fin (teoría de grafos)
En las matemáticas de gráficas infinitas , el final de una gráfica representa, intuitivamente, una dirección en la que la gráfica se extiende hasta el infinito. Extremos pueden formalizarse matemáticamente como clases de equivalencia de infinitos caminos , como refugios que describe las estrategias para la búsqueda de evasión de juegos en el gráfico, o (en el caso de los gráficos localmente finitos) como extremos topológicos de espacios topológicos asociados con la gráfica.
Los extremos de los gráficos se pueden utilizar (a través de los gráficos de Cayley ) para definir los extremos de los grupos generados de forma finita . Los grupos infinitos generados de forma finita tienen uno, dos o infinitos extremos, y el teorema de Stallings sobre los extremos de los grupos proporciona una descomposición para los grupos con más de un extremo.
Los extremos de los gráficos fueron definidos por Rudolf Halin ( 1964 ) en términos de clases de equivalencia de caminos infinitos. [1] Arayo en un grafo infinito es uncamino simplesemi-infinito; es decir, es una secuencia infinita de vérticesv0,v1,v2, ... en la que cada vértice aparece como máximo una vez en la secuencia y cada dos vértices consecutivos en la secuencia son los dos extremos de una arista en el grafico. Según la definición de Halin, dos rayosr0yr1son equivalentes si hay otro rayor2(no necesariamente diferente de ninguno de los dos primeros rayos) que contiene infinitos vértices en cada uno der0yr1. Ésta es una relación de equivalencia : cada rayo es equivalente a sí mismo, la definición es simétrica con respecto al orden de los dos rayos y se puede demostrar que es transitiva . Por lo tanto, divide el conjunto de todos los rayos en clases de equivalencia , y Halin definió un final como una de estas clases de equivalencia.
También se ha utilizado una definición alternativa de la misma relación de equivalencia: [2] dos rayos r 0 y r 1 son equivalentes si no hay un conjunto finito X de vértices que separe infinitos vértices de r 0 de infinitos vértices de r 1 . Esto es equivalente a la definición de Halin: si el rayo r 2 de la definición de Halin existe, entonces cualquier separador debe contener un número infinito de puntos de r 2 y por lo tanto no puede ser finito, y viceversa si r 2no existe entonces un camino que alterne tantas veces como sea posible entre r 0 y r 1 debe formar el separador finito deseado.
Extremos también tienen una caracterización más concreto en términos de refugios , las funciones que describen las estrategias de evasión para la búsqueda de evasión de juegos en un gráfico G . [3] En el juego en cuestión, un ladrón está tratando de evadir un conjunto de policías al pasar de vértice a vértice a lo largo de los bordes de G . La policía tiene helicópteros y, por lo tanto, no necesita seguir los bordes; sin embargo, el ladrón puede ver que se acerca la policía y puede elegir dónde moverse antes de que aterricen los helicópteros. Un refugio es una función β que asigna cada conjunto X de ubicaciones policiales a uno de los componentes conectados del subgrafo formado al eliminar X; un ladrón puede evadir a la policía moviéndose en cada ronda del juego a un vértice dentro de este componente. Los refugios deben satisfacer una propiedad de coherencia (correspondiente al requisito de que el ladrón no puede moverse a través de los vértices en los que la policía ya ha aterrizado): si X es un subconjunto de Y , y tanto X como Y son conjuntos de ubicaciones válidos para el conjunto de policías dado. , entonces β ( X ) debe ser un superconjunto de β ( Y ). Un refugio tiene orden k si la colección de ubicaciones policiales para las que proporciona una estrategia de escape incluye todos los subconjuntos de menos de k vértices en el gráfico; en particular, tiene orden ℵ 0si los mapas de cada subconjunto finito X de los vértices de un componente de G \ X . Cada rayo en G corresponde a un refugio de orden ℵ 0 , es decir, la función β que mapea cada conjunto finito X a la componente única de G \ X que contiene infinitos vértices del rayo. A la inversa, todo paraíso de orden ℵ 0 puede definirse de esta manera mediante un rayo. [4] Dos rayos son equivalentes si y solo si definen el mismo refugio, por lo que los extremos de un gráfico están en correspondencia uno a uno con sus paraísos de orden ℵ 0 .
.svg)
