En teoría de grafos , el entrelazamiento de un grafo dirigido es un número que mide la fuerza con la que se entrelazan los ciclos del grafo. Se define en términos de un juego matemático en el que n policías intentan capturar a un ladrón, que escapa por los bordes del grafo. De manera similar a otras medidas de grafos, como el rango de ciclo , algunos problemas algorítmicos, por ejemplo, el juego de paridad , se pueden resolver de manera eficiente en grafos de entrelazamiento acotado.
El juego de entrelazamiento [1] es jugado por n policías contra un ladrón en un grafo dirigido G . Inicialmente, todos los policías están fuera del grafo y el ladrón selecciona un vértice inicial arbitrario v de G . Más adelante, los jugadores se mueven por turno. En cada movimiento, los policías se quedan donde están o colocan a uno de ellos en el vértice actualmente ocupado por el ladrón. El ladrón debe moverse desde su vértice actual, a lo largo de un borde, a un sucesor que no esté ocupado por un policía. El ladrón debe moverse si ningún policía lo sigue. Si no hay un sucesor libre al que el ladrón pueda moverse, es atrapado y los policías ganan. El ladrón gana si no puede ser atrapado, es decir, si se puede hacer que el juego dure para siempre.
Un grafo G tiene un entrelazamiento n si n policías ganan en el juego de entrelazamiento en G pero n − 1 policías pierden el juego.
Los gráficos de entrelazamiento cero y uno se pueden caracterizar de la siguiente manera: [1]
El entrelazamiento también ha sido una noción clave para demostrar que la jerarquía de variables del cálculo modal mu es estricta. [2]
Puedes jugar al juego de enredos en línea en tPlay.