Dado un dirigidos $n\times n$ plaza de la gráfica, como se muestra en la figura con $n^2$ nodos. Encontrar un conjunto de rutas de $\mathcal P$ $s$ $t$con la cardinalidad mínima (he.e, número mínimo de las rutas en las $\mathcal P$) de tal forma que cualquier par de vértices alcanzables está contenida en al menos una ruta de acceso en $\mathcal P$. Dos vértices es alcanzable si existe una trayectoria entre ellos. Por ejemplo, si el nodo $v$ está por debajo y a la derecha del nodo $u$, $u$ $v$ es accesible (véase la figura).
Me han resuelto este problema por pequeño $n$ por ensayo y error, pero no tengo idea de generalizar. Puede alguien darme algunos consejos? o dime si este problema es NP-duro? Muchas gracias
Respuesta
¿Demasiados anuncios?
Misha
Puntos
1723
El número mínimo de rutas necesarias en un $n$ $n$ cuadrícula (que es, una cuadrícula con $n^2$ vértices) es $\left\lceil \frac{n(n+1)}{3}\right\rceil$: secuencia de A007980 en la OEIS.
Para demostrar que al menos este muchos caminos son necesarios, vamos a $k = \lfloor \frac{2n-1}{3}\rfloor$, definir $u_0, u_1, \dots, u_k$$u_i = (i,k-i)$, y definir $v_0, v_1, \dots, v_k$ $(n-1-i,n-1-(k-i))$ (como se coordina con $(0,0)$ la esquina superior izquierda de la cuadrícula). No todos los pares de puntos de $(u_i, v_j)$ puede tener un camino que va a través de ambos, pero no resultan ser exactamente $\left\lceil \frac{n(n+1)}{3}\right\rceil$ que hacer (para comprobar esto, se hará el cálculo para cada caso de $n \bmod 3$ por separado). Cualquier ruta de acceso sólo puede ir a través de un punto de $u_i$ y un punto de $v_j$, por lo que debe haber, al menos, $\left\lceil \frac{n(n+1)}{3}\right\rceil$ rutas para dar cuenta de todos estos pares.
Para demostrar que $\left\lceil \frac{n(n+1)}{3}\right\rceil$ pares suficiente, se dará una recursivo de construcción que llena un $n \times n$ cuadrícula con $2(n-1)$ rutas más que un $(n-3) \times (n-3)$ cuadrícula. (La secuencia de $\left\lceil \frac{n(n+1)}{3}\right\rceil$ resulta para satisfacer esta recurrencia.)
Empezar por tomar el siguiente $2(n-1)$ rutas en la $n \times n$ grid:
- caminos que van de la $k$ pasos a la derecha, $n-1$ pasos hacia abajo, y $n-1-k$ más pasos a la derecha para $k=1,\dots,n-1$, y
- caminos que van de la $k$ pasos hacia abajo, $n-1$ pasos a la derecha, y $n-1-k$ pasos más abajo para $k=1, \dots, n-1$.
Estos son suficientes para cubrir todos los pares de vértices que están en la misma fila o columna, así como de todos los pares de vértices que incluyen un vértice a lo largo de uno de los bordes de la cuadrícula.
Para lidiar con los pares de vértices que no están a lo largo de un borde de la cuadrícula, tomar la construcción de la $(n-3) \times (n-3)$ cuadrícula, y modificar cada ruta de acceso de la siguiente manera:
- Insertar un paso atrás y un paso a la derecha en el comienzo.
- Insertar un paso atrás y un paso a la derecha en el centro.
- Insertar un paso atrás y un paso a la derecha al final.
Deje $u_1$ $u_2$ dos vértices de la cuadrícula con coordenadas $(x_1,y_1)$$(x_2,y_2)$, de tal manera que $1 < x_1 < x_2 < n-1$$1 < y_1 < y_2 < n-1$. Para mostrar que hay una modificación de la ruta que cubre $u_1$ $u_2$ simultáneamente, definir $$ u_i' = \begin{cases} (x_i-1, y_i-1), & \text{if } x_i + y_i < n-1, \\ (x_i-1, y_i-2) \text{ or } (x_i-2,y_i-1), & \text{if } x_i + y_i = n-1, \\ (x_i-2, y_i-2), & \text{if } x_i + y_i > n-1. \end{casos} $$ Aquí es una visualización de este no-muy-bijective la correspondencia entre los puntos en el interior de la $n \times n$ cuadrícula, y puntos en el $(n-3) \times (n-3)$ cuadrícula. Cada región roja (incluyendo mayormente a un punto, algunos incluso más) corresponde a un punto en el más pequeño de la cuadrícula. Puntos en la superposición de dos rojo regiones podrían ir de cualquier manera, no importa.
La ruta de acceso en la $(n-3) \times (n-3)$ cuadrícula que cubre $u_1'$ $u_2'$ simultáneamente se convierte en un camino en el $n \times n$ cuadrícula que cubre $u_1$ $u_2$ simultáneamente cuando se modifican. Esto completa la prueba de que las obras de construcción.
