Refugio (teoría de grafos)

En la teoría de grafos, un refugio es un cierto tipo de función en los conjuntos de vértices de un gráfico no dirigido . Si existe cobertura, el fugitivo puede usarla para ganar el juego de persecución y evasión en el gráfico usando esta función en cada paso del juego para determinar los conjuntos de vértices seguros a los que ir. Las cubiertas fueron introducidas por primera vez por Seymour y Thomas [1] como un medio para caracterizar el ancho de árbol de los gráficos [2] . Otras aplicaciones de este concepto son la prueba de la existencia de pequeños separadores en familias de grafos cerrados en menores [3] y la descripción de fronteras y clique minors de grafos infinitos [4] [5] .

Definición

Si G es un grafo no dirigido y X es un conjunto de vértices, entonces la arista X es un componente conectado no vacío de un subgrafo de G formado al eliminar X. Un refugio de orden k en un gráfico G es una función β que asigna cualquier conjunto X con menos de k vértices al tablero X β ( X ). Esta función también debe satisfacer restricciones adicionales, que son definidas de varias maneras por varios autores. El número k se denomina orden de cobertura [6] .

La definición original de Seymour y Thomas [2] de un refugio requiere la propiedad de que cualquiera de los dos lados β ( X ) y β ( Y ) deben tocarse entre sí, o deben tener un vértice común o debe haber un borde cuyos extremos pertenecen a estos dos lados. En la definición utilizada posteriormente por Alon, Seymour y Thomas [3] , ocultar requiere satisfacer la propiedad más débil de monotonicidad : si X ⊆ Y y ambos conjuntos X e Y tienen menos de k vértices, entonces β ( Y ) ⊆ β ( X ) . La propiedad de tangencia implica la propiedad de monotonicidad, pero lo contrario no se cumple necesariamente. Sin embargo, se deduce de los resultados de Seymour y Thomas [2] que en grafos finitos, si existe una cobertura con la propiedad de monotonicidad, entonces existe una cobertura con el mismo orden y la propiedad de tangencia.

Los refugios de definición de tangente están estrechamente relacionados con las zarzas , familias de subgrafos conectados de un gráfico dado que son tangentes entre sí. El orden de la mora es el número mínimo de vértices necesarios en el conjunto de vértices que tiene un representante en cada subgrafo de la familia. El conjunto de tableros β ( X ) para cubrir el orden k (con la definición de tangencia) forma una mora de orden al menos k , ya que cualquier conjunto Y con menos de k vértices no puede cubrir el subgrafo β ( Y ). Por el contrario, a partir de cualquier zarza de orden k , se puede construir un refugio del mismo orden definiendo β ( X ) (para cada X ) como una perla X que incluye todos los subgrafos de la zarza que no comparten puntos con   X. El requisito de que los subgrafos en una mora se toquen entre sí se puede usar para mostrar que tal tablero X existe, y que todos los tableros β ( X ) elegidos de esta manera se tocan entre sí. Así, un grafo tiene una zarza de orden k si y sólo si tiene un abrigo de orden k .

Ejemplo

Como ejemplo: sea G una red de nueve vértices. Defina un refugio de orden 4 en G asignando cada conjunto X con tres o menos vértices a un tablero X β ( X ) de la siguiente manera:

Es fácil comprobar directamente por análisis de casos que esta función β satisface las propiedades de monotonicidad del refugio. Si X ⊆ Y y X tiene menos de dos vértices, o si X consta de dos vértices que no son dos vecinos de un vértice de esquina de la red, entonces solo hay un tablero X y contiene cualquier tablero Y. En el caso restante, X consta de dos vecinos del vértice de la esquina y tiene dos lados X : uno consiste en el vértice de la esquina y el otro (elegido como β ( X )) consta de los seis vértices restantes. No importa qué vértice se agregue a X para formar Y , habrá un tablero Y con al menos cuatro vértices, que debe ser el único tablero más grande, ya que contiene más de la mitad de los vértices que no son de Y. Esta cuenta Y grande se elegirá como β ( Y ) y será un subconjunto de β ( X ). Por lo tanto, en cualquier caso, se cumple la propiedad de monotonicidad.

Persecución evasiva

Los escondites modelan ciertas clases de estrategias para un fugitivo en un juego de persecución en el que menos de k perseguidores intentan capturar a un solo fugitivo. Las posiciones tanto de los perseguidores como del fugitivo están limitadas por los vértices de un gráfico no dirigido dado, y ambos jugadores conocen las posiciones de los perseguidores y del fugitivo. En cada turno de juego, se puede añadir un nuevo perseguidor en un vértice arbitrario del gráfico (hasta llegar a un valor de k perseguidores) o se puede eliminar del gráfico uno de los perseguidores ya existentes. Sin embargo, antes de agregar un nuevo perseguidor, el fugitivo recibe información sobre dónde se agregará el perseguidor y puede moverse a lo largo de los bordes del gráfico hacia cualquier vértice desocupado. Durante el movimiento, el fugitivo no puede pasar por la parte superior ocupada por uno de los perseguidores.

Si existe k - cobertura (con la propiedad de monotonicidad), entonces el fugitivo puede evitar la captura indefinidamente y así ganar si siempre se mueve hacia el vértice β ( X ), donde X es el conjunto de vértices ocupados por los perseguidores al final de el movimiento. La propiedad de monotonicidad del refugio asegura que cuando se agrega un nuevo perseguidor a un vértice del gráfico, los vértices en β ( X ) siempre serán accesibles desde la posición actual del fugitivo [2] .

Por ejemplo, el fugitivo gana este juego contra tres perseguidores en una cuadrícula de 3 × 3 utilizando la estrategia descrita, apoyándose en la cobertura de orden 4 descrita en el ejemplo. Sin embargo, en el mismo juego, cuatro perseguidores siempre pueden atrapar a un fugitivo colocando a los perseguidores en tres vértices, lo que corta la red en dos caminos con tres vértices cada uno. Luego colocamos al perseguidor en el centro del camino que contiene al fugitivo, y finalmente eliminamos al perseguidor que no está adyacente a la esquina y lo colocamos sobre el fugitivo. Por tanto, una red de 3 × 3 no tiene orden de cobertura 5.

Las coberturas con la propiedad táctil permiten que el fugitivo gane contra perseguidores más fuertes que pueden saltar simultáneamente de una posición a otra [2] .

Relación con ancho de árbol, separadores y menores

Las cubiertas se pueden usar para describir el ancho de árbol de un gráfico: un gráfico tiene una cubierta de orden k si y solo si tiene un ancho de árbol de al menos k − 1 . La descomposición en árbol se puede utilizar para describir la estrategia ganadora para los perseguidores en el mismo juego de persecución-evitación, de modo que el gráfico tenga una cobertura de orden k si y solo si el fugitivo gana en un juego correcto contra menos de k perseguidores. En partidas ganadas por un fugitivo, siempre hay una estrategia óptima en forma de cobertura, y en partidas ganadas por perseguidores, siempre hay una estrategia óptima en forma de descomposición del árbol [2] . Por ejemplo, dado que una red de 3 × 3 tiene una cobertura de orden 4 pero no una cobertura de orden 5, debe tener un ancho de árbol exactamente igual a 3. El mismo teorema minimax se puede generalizar a gráficos infinitos con un ancho de árbol finito si, en el caso definición de ancho de árbol, se requiere que el árbol subyacente no tenga extremos [2] .

Los escondites también están estrechamente relacionados con la existencia de separadores , un tamaño pequeño de conjuntos de vértices X en un gráfico de n vértices, de modo que cualquier borde X tiene como máximo 2n /3 vértices. Si el grafo G no tiene un separador con k vértices, entonces cualquier conjunto X con como máximo k vértices tiene una arista X (única) con más de 2n /3 vértices. En este caso, G tiene un refugio de orden k + 1 , en el que β ( X ) se define como un único tablero X grande. Es decir, cualquier gráfico tiene un pequeño separador o una cubierta de alto orden [3] .

Si el grafo G tiene una cobertura de orden k , para k ≥ h 3/2 n 1/2 para algún entero h , entonces G debe tener también el grafo completo K h como menor . En otras palabras, el número de Hadwiger de un gráfico de n -vértices con orden de cobertura k tiene un valor de al menos k 2/3 n −1/3 . Como consecuencia, los gráficos libres de K h menores tienen un ancho de árbol menor que h 3/2 n 1/2 y separadores de tamaño menor que h 3/2 n 1/2 . De manera más general, el límite O(√ n ) de ancho de árbol y el tamaño del separador son válidos para cualquier familia de grafos no triviales que se puedan caracterizar por grafos prohibidos , ya que para cualquier familia de este tipo existe una constante h tal que la familia no incluye K h [3] .

En grafos infinitos

Si un grafo G contiene un rayo, un camino simple semi-infinito que tiene un vértice inicial pero no un vértice final, entonces tiene una cobertura de orden ℵ 0 , es decir, una función β que mapea cada conjunto finito X de vértices a un Tablero X que cumple con las condiciones de cobertura. Es decir, definimos β ( X ) como un tablero X único, que consta de un número ilimitado de vértices de rayos. Por lo tanto, en el caso de los gráficos infinitos, la conexión entre el ancho del árbol y los refugios se rompe: un solo rayo, a pesar de ser un árbol en sí mismo, tiene refugios de todos los órdenes finitos y, aún más fuerte, un refugio de orden ℵ 0 . Dos rayos de un grafo infinito se consideran equivalentes si no existe un conjunto finito de vértices que separe un número infinito de vértices de un rayo de un número infinito de vértices de otro rayo. Esta relación de equivalencia y sus relaciones de equivalencia se denominan los extremos del grafo.

Los puntos finales de cualquier gráfico tienen una correspondencia uno a uno con lugares escondidos de orden ℵ 0 . Cualquier rayo define una cubierta, y dos rayos equivalentes cualesquiera definen la misma cubierta [4] . Por el contrario, cualquier cobertura está determinada por los rayos de tal manera que puede mostrarse mediante el siguiente análisis de opciones:

Por lo tanto, cualquier clase de equivalencia de rayos define una cobertura única, y cualquier cobertura está definida por una clase de equivalencia de rayos.

Para cualquier número cardinal , un grafo infinito G tiene una cobertura de orden κ si y solo si tiene una clique menor de orden κ. Es decir, para números cardinales incontables, el mayor orden de ocultación en G es el número de Hadwiger del gráfico G [4] .

Notas

  1. ↑ Seymour, Thomas, 1993 .
  2. ↑ 1 2 3 4 5 6 7 Seymour y Thomas, 1993 , pág. 22–33.
  3. ↑ 1 2 3 4 Alon, Seymour, Thomas, 1990 , pág. 801–808.
  4. ↑ 1 2 3 Robertson, Seymour, Thomas, 1991 , pág. 303–319.
  5. ↑ 1 2 Diestel, Kühn, 2003 , pág. 197–206.
  6. ↑ Johnson, Robertson, Seymour, Thomas, 2001 , pág. 138–155.

Literatura