En la formulación discreta del problema pos-evasión, el medio ambiente se modela como un gráfico.
Hay variantes innumerables posibles de persecución-evasión, aunque tienden a compartir muchos elementos. Un ejemplo típico básico, es el siguiente (policías y ladrones)[4] juegos: Perseguidores y evasores ocupan los nodos de un grafo. Las dos partes tienen alternativas o decisiones posible, que consisten en que cada miembro se quede donde está o se mueve a lo largo de un borde a un nodo adyacente. Si un perseguidor ocupa el mismo nodo que un evasor el evasor es capturado y se le retira del gráfico. La pregunta que se plantea es por lo general el número de perseguidores que son necesarios para asegurar la eventual captura de todos los evasores.[5]
A menudo, las reglas de movimiento cambian la velocidad de los evasores. Esta velocidad es el número máximo de aristas en las que un evasor puede moverse a lo largo de en un solo turno. En el ejemplo anterior, los evasores tienen una velocidad de uno. En el otro extremo es el concepto infinito de velocidad, que permite que un evasor para moverse a cualquier nodo en el gráfico siempre y cuando haya un camino entre sus posiciones originales y finales que no contenga nodos ocupados por un perseguidor. Del mismo modo algunas variantes arman a los perseguidores con "helicópteros", que les permiten moverse a cualquier vértice en su turno sin recorrer un punto previo.
Otras variantes ignoran la restricción de que los perseguidores y evasores siempre deben ocupar un nodo y permitir la posibilidad de que se encuentren a algún lugar a lo largo de un borde. Estas variantes se refieren a menudo a problemas tan amplios, mientras que las variantes anteriores entrarían en la categoría de búsqueda de problemas.
Existen varias variantes que son equivalentes a los parámetros de gráfico importantes. En concreto, la búsqueda del número de perseguidores necesarios para capturar un solo evasor con velocidad infinita en un grafo G (cuando perseguidores y evasor no tienen manera de moverse giro a giro, sino que se mueven al mismo tiempo) es equivalente a encontrar el punto de la gráfica.
