TEORÍA DE TÉRMINOS DE GRAFOS

En la teoría de gráficos , un gráfico de policía ganador es un gráfico no dirigido en el que el perseguidor (policía) siempre puede ganar un juego de evasión de persecución en el que persigue a un ladrón, los jugadores se mueven alternativamente a lo largo del borde de un gráfico o se quedan quietos, hasta el policía aterriza en el vértice del ladrón. ^[1] Los gráficos finitos de policías también se denominan gráficos desmontables o gráficos construibles , porque se pueden desmantelar eliminando repetidamente un vértice dominado (uno cuyo vecindario cerrado es un subconjunto del vecindario de otro vértice) o construirse agregando repetidamente dicho vértice. Los gráficos de policías pueden reconocerse en tiempo polinómicomediante un algoritmo codicioso que construye un orden de desmantelamiento. Incluyen los gráficos cordales y los gráficos que contienen un vértice universal .

Definiciones [ editar ]

Persecución-evasión [ editar ]

Nowakowski y Winkler (1983) introdujeron gráficos de policías (y la clase complementaria de gráficos, gráficos de ladrones ) en el contexto del siguiente juego de persecución y evasión, cuya invención atribuyen a G. Gabor y A. Quilliot. Dos jugadores, un policía y un ladrón, se colocan en diferentes vértices iniciales de un gráfico dado. Ellos juegan por turnos; en el turno de cada jugador, el jugador puede moverse a un vértice adyacente o quedarse. El juego termina y el policía gana si el policía puede terminar su turno en el mismo vértice que el ladrón. El ladrón gana evadiendo indefinidamente al policía. Un gráfico de policía ganador es un gráfico con la propiedad de que, sin importar dónde comiencen los dos jugadores, el policía siempre puede forzar una victoria. ^[2]

Desmontaje [ editar ]

La vecindad cerrada N [ v ] de un vértice v en un gráfico dado es el conjunto de vértices que consta de v y todos los demás vértices adyacentes a v . Se dice que el vértice v está dominado por otro vértice w cuando N [ v ] ⊂ N [ w ] . Es decir, v y w son adyacentes, y cualquier otro vecino de v también es vecino de w . ^[3] Nowakowski y Winkler (1983)Llame a un vértice que está dominado por otro vértice un vértice irreducible . ^[2]

Un orden de desmantelamiento o el orden de eliminación de la dominación de un gráfico dado es un orden de los vértices de tal manera que, si los vértices se eliminan uno por uno en este orden, cada vértice (excepto el último) está dominado. Un gráfico es desmontable si y solo si tiene un orden de desmontaje. ^[2] [3]

Propiedades de cierre [ editar ]

	una	si	C	re	mi	F	sol	h
8									8
7 7									7 7
6 6									6 6
5 5									5 5
4 4									4 4
3									3
2									2
1									1
	una	si	C	re	mi	F	sol	h

El rey blanco (policía) puede vencer al rey negro (ladrón) en un tablero de ajedrez, por lo que el gráfico del rey es un gráfico de victoria policial.

La familia de gráficos de policías ganadores se cierra con productos sólidos de gráficos . El policía puede ganar en un producto fuerte de gráficos de policías ganadores jugando para ganar uno de los factores del producto, y después de hacerlo jugando en los factores restantes de la misma manera mientras continúa en el mismo vértice que el ladrón en El factor ya ganado. ^[2] Por ejemplo, el gráfico del rey , un fuerte producto de dos gráficos de ruta , es cop-win. ^[4]

No es cierto que cada subgrafo inducido de un gráfico de policías gane es cop-win. Sin embargo, ciertas subgrafías inducidas especiales siguen siendo policiales. Nowakowski y Winkler (1983) definen una retracción de un gráfico G en una de sus subgrafías inducidas H para ser un mapeo desde los vértices de G a los vértices de H que mapea cada vértice de H hacia sí mismo, y que mapea cada dos vértices adyacentes de G ya sea para el mismo vértice que entre sí o a un par de vértices adyacentes en H . Luego, como argumentan, la familia de gráficos de policías se cierra bajo retracción. Para, un policía puede ganar en Hmediante la simulación de un juego en el G . Siempre que la estrategia ganadora en G llamaría a la policía de que se quedara, o para seguir una ventaja cuyos extremos se correlacionan con el mismo vértice de H , las estancias de policía puesto en H . Y en todos los demás casos, la CP sigue el borde en H que es la imagen bajo la retracción de un borde que gana en G . ^[2]

Equivalencia de cop-win y desmantelamiento [ editar ]

Cada gráfico desmontable es cop-win. Una estrategia ganadora para el policía es encontrar un vértice dominado v , y seguir (por inducción) una estrategia óptima en el gráfico formado al eliminar v , pretendiendo que el ladrón está en el vértice que domina v cada vez que está realmente en v . Esto dará como resultado una victoria real del juego, o en una posición donde el ladrón está en v y el policía está en el vértice dominante, desde el cual el policía puede ganar en un movimiento más. ^[2] Esta estrategia se puede utilizar como base para una prueba mediante la inducción del hecho de que, en un gráfico de n -vertex, el policía puede forzar una victoria en la mayoría de n - 4 movimientos.^[5] [6]

Por el contrario, cada gráfico de policía gana tiene un vértice dominado. Porque, si el ladrón juega de manera óptima para que el juego dure el mayor tiempo posible y la última posición del juego antes de que el policía gane tiene al policía en el vértice c y al ladrón en r , entonces r debe estar dominado por c , de lo contrario, el ladrón podría prolongar el juego por al menos un movimiento. La función que mapea r sobre c y deja todos los demás vértices en su lugar es una retracción, por lo que el gráfico formado al eliminar el vértice dominado debe seguir siendo un triunfo policial. Por inducción, se deduce que cada gráfico de policía-ganador es desmontable. ^[2]El mismo argumento muestra que, en un gráfico sin vértices dominados, el ladrón nunca puede perder: siempre hay un movimiento a un vértice que no es adyacente al policía. En un gráfico arbitrario que no es un triunfo policial, el ladrón puede ganar eliminando todos los vértices dominados y jugando dentro del subgrafo restante, que no debe estar vacío, de lo contrario el gráfico sería desmantelable.

Algoritmos de reconocimiento y la familia de todas las órdenes de desmantelamiento [ editar ]

Si un vértice en un gráfico de victorias de policía está dominado, entonces (a medida que se eliminan otros vértices dominados) permanece dominado hasta que se elimine o se convierta en el vértice final de un orden de desmantelamiento. Por lo tanto, la colección de órdenes de desmantelamiento válidas tiene la estructura de un antimatroide , y se puede encontrar una orden de desmantelamiento mediante un simple algoritmo codicioso que encuentra y elimina repetidamente cualquier vértice dominado. El proceso tiene éxito si y solo si el gráfico es cop-win, así que además de proporcionar un algoritmo para encontrar órdenes de desmantelamiento, este método proporciona un algoritmo para probar si un gráfico dado es cop-win. Una forma de encontrar cada vértice sucesivo para eliminar es realizar los siguientes pasos:

• Encuentra todos los triángulos en el gráfico y cuenta el número de triángulos en los que participa cada borde.
• Encuentre repetidamente un vértice v que sea el punto final de un borde que participa en un número de triángulos igual al grado de v menos uno, elimine v y disminuya los triángulos por borde de cada borde restante que formó un triángulo con v .

En un gráfico con n vértices, m aristas y degeneración d , este proceso puede llevarse a cabo en el tiempo O ( dm ) . ^[7]

Un algoritmo alternativo y más complicado de Spinrad (2004) implica mantener un número llamado déficit para cada par de vértices adyacentes ( x , y ) , que cuenta el número de vecinos de x que no son vecinos de y . Construye y mantiene el conjunto de déficit real (vecinos de x que no son vecinos de y ) solo cuando el déficit es pequeño. Para acelerar sus cálculos, utiliza árboles de decisión que clasifican los vértices de acuerdo con sus adyacencias con pequeños bloques de log ₂  nvértices Realiza los siguientes pasos:

• Agrupe los vértices en bloques, construya un árbol de decisión para cada bloque y clasifique todos los vértices por sus conjuntos de vecinos dentro de cada bloque.
• Use esta clasificación para calcular los déficits para todos los pares de vértices adyacentes, en el tiempo O ( n / log n ) por par.
• Repita los siguientes pasos n / log n veces, hasta que se hayan eliminado todos los vértices:
  • Construya el conjunto de déficit para todos los pares adyacentes que tienen déficit como máximo log  n y que aún no han construido este conjunto, utilizando el conjunto inicial de árboles de decisión, en el tiempo O ( n / log n ) por par.
  • Repita los siguientes pasos log n veces:
    • Encuentre un par ( x , y ) con un conjunto de déficit construido pero vacío.
    • Eliminar vértice x
    • Elimine x de todos los conjuntos de déficit construidos a los que pertenece.
  • Construya un árbol de decisión para el registro n vértices eliminados y clasifique todos los vértices por sus vecinos en este conjunto.
  • Use el árbol de decisión para actualizar los déficits para todos los bordes en tiempo constante por borde.

El tiempo para este procedimiento es O ( n ² + mn / log  n ) . ^[8]

Familias relacionadas de gráficos [ editar ]

Cada gráfico cordal finito es un gráfico desmantelable, y cada orden de eliminación de un gráfico cordal (un orden de los vértices en el que los vecinos posteriores de cada vértice forman una camarilla ) es un orden de desmantelamiento válido. Sin embargo, existen infinitas gráficas de cordal que no son cop-win. ^[9]

Cada gráfico que tiene un vértice universal es desmontable, ya que cada vértice está dominado por el vértice universal, y cualquier orden de vértice que coloque el vértice universal al final es un orden de desmantelamiento válido. Por el contrario, casi todos los gráficos desmontables tienen un vértice universal, en el sentido de que, entre todos los gráficos desmontables n- vértice, la fracción de estos gráficos que tienen un vértice universal va a uno en el límite como n va al infinito. ^[10]

El gráfico de la rueda de cinco vértices es cop-win pero no hereditariamente cop-win.

Los gráficos de ganancia hereditaria de cop son los gráficos en los que cada subgrafía isométrica es win de cop. Esto no es cierto para todos los gráficos de policías ganadores; por ejemplo, el gráfico de rueda de cinco vértices es cop-win pero contiene un ciclo isométrico de 4 ciclos, que no es cop-win, por lo que este gráfico de rueda no es hereditariamente cop-win. Los gráficos de ganancia hereditaria de la policía son los mismos que los gráficos puenteados, gráficos en los que cada ciclo de longitud cuatro o más tiene un atajo, un par de vértices más cercanos en el gráfico que en el ciclo. ^[11] Un gráfico de ganancia de policía es ganancia de ganancia hereditaria si y solo si no tiene ni el ciclo 4 ni el ciclo 5 como ciclos inducidos. Para un gráfico de ganancia policial hereditaria, la reversión de cualquier recorrido transversales un orden de desmantelamiento válido, del cual se deduce que cualquier vértice puede elegirse como el último vértice de un orden de desmantelamiento. ^[12]

Se puede usar un juego similar con un mayor número de policías para definir el número de policías de un gráfico, el menor número de policías necesarios para ganar el juego. Los gráficos de policías ganadores son exactamente los gráficos del número de policías igual a uno.

  (Redirigido desde el gráfico sin puente )

Saltar a navegaciónSaltar a búsqueda

Un gráfico con 16 vértices y 6 puentes (resaltados en rojo)

Un gráfico conectado no dirigido sin bordes de puente

En la teoría de grafos , un puente , istmo , borde de corte o arco de corte es un borde de un gráfico cuya eliminación aumenta su número de componentes conectados . ^{[1] De manera} equivalente, un borde es un puente si y solo si no está contenido en ningún ciclo . Se dice que un gráfico no tiene puentes o está libre de istmo si no contiene puentes.

Otro significado de "puente" aparece en el término puente de un subgrafo . Si H es un subgrafo de G , un puente de H en G es un subgrafo máxima de G que no está contenido en H y no está separado por H .

Árboles y bosques [ editar ]

Un gráfico con $${\ displaystyle n} los nodos pueden contener como máximo $${\ displaystyle n-1}puentes, ya que agregar bordes adicionales debe crear un ciclo. Los gráficos con exactamente$${\ displaystyle n-1}los puentes son exactamente los árboles , y los gráficos en los que cada borde es un puente son exactamente los bosques .

En cada gráfico no dirigido, hay una relación de equivalencia en los vértices según la cual dos vértices se relacionan entre sí siempre que haya dos caminos de borde disyuntivo que los conectan. (Cada vértice está relacionado con sí mismo a través de dos caminos de longitud cero, que son idénticos pero no obstante disyunto de borde.) Las clases de equivalencia de esta relación se denominan componentes conectados a 2 bordes , y los puentes del gráfico son exactamente los bordes cuyos Los puntos finales pertenecen a diferentes componentes. El árbol de bloques de puente del gráfico tiene un vértice para cada componente no trivial y un borde para cada puente. ^[2]

Relación con la conectividad de vértices [ editar ]

Los puentes están estrechamente relacionados con el concepto de vértices de articulación , vértices que pertenecen a cada ruta entre algún par de otros vértices. Los dos puntos finales de un puente son vértices de articulación a menos que tengan un grado de 1, aunque también puede ser posible que un borde sin puente tenga dos vértices de articulación como puntos finales. Análogamente a los gráficos sin puente que están conectados a 2 bordes, los gráficos sin vértices de articulación están conectados a 2 vértices .

En un gráfico cúbico , cada vértice de corte es un punto final de al menos un puente.

Gráficos sin puente [ editar ]

Un gráfico sin puente es un gráfico que no tiene ningún puente. Las condiciones equivalentes son que cada componente conectado del gráfico tiene una descomposición del oído abierto , ^[3] que cada componente conectado está conectado a 2 bordes , o (según el teorema de Robbins ) que cada componente conectado tiene una fuerte orientación . ^[3]

Un problema abierto importante que involucra puentes es la conjetura del ciclo de doble cubierta , debido a Seymour y Szekeres (1978 y 1979, independientemente), que establece que cada gráfico sin puente admite un conjunto de ciclos simples que contienen cada borde exactamente dos veces. ^[4]

El algoritmo de búsqueda de puentes de Tarjan [ editar ]

Robert Tarjan describió el primer algoritmo de tiempo lineal para encontrar los puentes en un gráfico en 1974. ^[5] Realiza los siguientes pasos:

• Encuentra un bosque de$${\ displaystyle G}
• Crea un bosque enraizado $${\ displaystyle F} del árbol de expansión
• Atravesar el bosque $${\ displaystyle F}en preordenar y numerar los nodos. Los nodos principales en el bosque ahora tienen números más bajos que los nodos secundarios.
• Para cada nodo $${\ displaystyle v} en preordenar (denotando cada nodo usando su número de preorden), haga:
  • Calcule la cantidad de descendientes del bosque $${\ displaystyle ND (v)} para este nodo, agregando uno a la suma de los descendientes de sus hijos.
  • Calcular $${\ displaystyle L (v)}, la etiqueta de pedido más bajo accesible desde $${\ displaystyle v} por una ruta para la cual todos menos el último borde permanecen dentro del subárbol enraizado $${\ displaystyle v}. Este es el mínimo del conjunto que consiste en la etiqueta de pedido previo de$${\ displaystyle v}, de los valores de $${\ displaystyle L (w)} en los nodos hijos de $${\ displaystyle v} y de las etiquetas de preorden de nodos accesibles desde $${\ displaystyle v} por bordes que no pertenecen a $${\ displaystyle F}.
  • Del mismo modo, calcular $${\ displaystyle H (v)}, la etiqueta de preorden más alta alcanzable por una ruta para la cual todos menos el último borde permanecen dentro del subárbol enraizado en $${\ displaystyle v}. Este es el máximo del conjunto que consiste en la etiqueta de preorden de$${\ displaystyle v}, de los valores de $${\ displaystyle H (w)} en los nodos hijos de $${\ displaystyle v} y de las etiquetas de preorden de nodos accesibles desde $${\ displaystyle v} por bordes que no pertenecen a $${\ displaystyle F}.
  • Para cada nodo $${\ displaystyle w} con nodo padre $${\ displaystyle v}, Si $${\ displaystyle L (w) = w} y {\ displaystyle H (w)  entonces el borde de $${\ displaystyle v} a $${\ displaystyle w} Es un puente.

Búsqueda de puentes con descomposiciones en cadena [ editar ]

Un algoritmo de búsqueda de puente muy simple ^[6] utiliza descomposiciones en cadena . Las descomposiciones en cadena no solo permiten calcular todos los puentes de un gráfico, sino que también permiten leer cada vértice de corte de G (y el árbol de corte de bloque de G ), lo que proporciona un marco general para probar 2 vértices y 2 vértices -conectividad (que se extiende a las pruebas de conectividad de 3 bordes y 3 vértices en tiempo lineal).

Las descomposiciones en cadena son descomposiciones especiales del oído que dependen de un árbol DFS T de G y se pueden calcular de manera muy simple: deje que cada vértice se marque como no visitado. Para cada vértice v en números DFS ascendentes 1 ... n , atraviese cada respaldo (es decir, cada borde que no esté en el árbol DFS) que incide en v y siga el camino de los bordes de los árboles hasta la raíz de T , deteniéndose en El primer vértice marcado como visitado. Durante tal recorrido, cada vértice atravesado se marca como visitado. Por lo tanto, un recorrido se detiene a más tardar en v y forma una ruta o ciclo dirigido, comenzando con v; llamamos a este camino o ciclo una cadena. La i ésima cadena encontrada por este procedimiento se denomina C _i . C = C ₁ , C ₂ , ... es entonces una degradación de las cadenas de G .

Los siguientes caracterizaciones luego permitir a leer de varias propiedades de G de C de manera eficiente, incluyendo todos los puentes de G . ^[6] Sea C una descomposición en cadena de un gráfico simple conectado G = (V, E) .

1. G está conectado-2-borde si y sólo si las cadenas en C partición E .
2. Un borde e en G es un puente si y sólo si e no está contenida en cualquier cadena en C .
3. Si G está conectado a 2 bordes, C es una descomposición del oído .
4. G está conectada a 2-vértice si y sólo si G tiene grado mínimo 2 y C ₁ es el único ciclo en C .
5. Un vértice v en un gráfico G conectado a 2 bordes es un vértice cortado si y solo si v es el primer vértice de un ciclo en C - C ₁ .
6. Si G está conectado a 2 vértices, C es una descomposición del oído abierto .