Apartado 1

Definimos una red como un conjunto de elementos más un conjunto de arcos que unen pares de elementos diferentes; consideraremos que los elementos son números naturales de 1 a una cierta cota N. Por ejemplo, una red puede constar de los naturales {1, 2, 3, 4} y del conjunto de arcos {(1, 2), (2, 4), (3, 4)}. Una red puede representarse gráficamente:

Destacamos que los arcos están dirigidos, es decir, los arcos (1, 2) y (2, 1) son diferentes.
Diremos que una secuencia C de naturales está ordenada respecto una red R si se cumplen las tres condiciones siguientes:

• C no contiene elementos repetidos.
• Los elementos de C y de R coinciden.
• Si existe un arco (a, b) en R, entonces a aparece antes que b en C.

Así, las secuencias 1 2 3 4, 1 3 2 4 y 3 1 2 4 están ordenadas respecto la red del ejemplo anterior, pero no sucede lo mismo con las secuencias 1 2 3 2 4, 1 2 3 ni 1 2 4 3, pues violan alguna de las tres condiciones establecidas.
Se pide un programa capaz de determinar si una secuencia está ordenada respecto una red. Dicho programa debe procesar un fichero de entrada, de nombre "RED1.DAT", que contendrá la configuración de la red y diversas secuencias. El formato exacto es el siguiente:

Línea 1: un carácter numérico (dígito) que representa el valor de N (comprendido entre 1 y 9).

Líneas siguientes: cada línea contendrá una o más parejas de valores naturales, representando cada una de ellas un arco entre dos elementos de la red. Cada natural se representa mediante un dígito; dos naturales consecutivos están siempre separados por un único espacio en blanco.

Una línea que contiene únicamente una aparición del carácter '0'.

Líneas siguientes: cada línea representa una secuencia a examinar y contendrá diversos valores naturales, separados por un único espacio en blanco, y representados cada uno de ellos por un dígito.

La salida debe almacenarse en el fichero "RED1.RES" y debe contener tantas líneas como secuencias a examinar. Cada línea contendrá o bien la palabra 'SI' o bien la palabra 'NO' (en mayúsculas) dependiendo de si la secuencia correspondiente está ordenada respecto la red o no.

A continuación, se codifica la red del ejemplo anterior y algunas secuencias respecto ella, así como el resultado esperado:

Para simplificar el problema, podéis suponer en este apartado y en todos los que siguen, que no habrá errores de formato en la entrada.

Apartado 2

Decimos que dos redes A y B son similares si se cumplen las condiciones siguientes:

• Tienen los mismos elementos.
• B tiene los mismos arcos que A, utilizando una renumeración de los elementos de A.

Por ejemplo, la red A con elementos {1, 2, 3, 4} y arcos {(3, 1), (4, 2), (1, 2)} es similar a la red del apartado anterior (llamémosla B) si renumeramos los elementos de A de la forma siguiente: 1, como 2; 2, como 4; 3, como 1; y 4, como 3. La similitud queda patente dibujando ambas redes una junto a otra:

Se pide construir un programa que, dadas dos redes, determine si son similares o no. Puede suponerse que, en caso de ser similares, habrá una sola renumeración de los elementos de la primera de las redes que permita obtener la condición de similitud. El programa debe procesar el fichero de entrada, de nombre "RED2.DAT", que contendrá la configuración de ambas redes. El formato exacto es el siguiente:

Línea 1: un carácter numérico (dígito) que representa el valor de N para la red A.

Líneas siguientes: cada línea contendrá una o más parejas de valores naturales, representando cada una de ellas un arco entre dos elementos de la red A. Cada natural se representa mediante un dígito; dos naturales consecutivos están siempre separados por un único espacio en blanco.

Una línea que contiene únicamente una aparición del carácter '0'.

Línea siguiente: un carácter numérico (dígito) que representa el valor de N para la red B.

Líneas siguientes: cada línea contendrá una o más parejas de valores naturales, representando cada una de ellas un arco entre dos elementos de la red B. Cada natural se representa mediante un dígito; dos naturales consecutivos están siempre separados por un único espacio en blanco.

La salida debe almacenarse en el fichero "RED2.RES" y debe contener una única línea. Dicha línea contendrá la palabra 'NO' (en mayúsculas) si las redes no son similares, mientras que si lo son deberá contener la renumeración (única) que asegura dicha condición. La renumeración se escribirá como una secuencia de valores naturales, separados por un único espacio en blanco, y representados cada uno de ellos mediante un dígito; el valor que aparece en posición k en la línea representa la renumeración del elemento k de A. Así, para el ejemplo anterior, el fichero "RED2.RES" debe contener los valores 2 4 1 3, en este orden:

Apartado 3

Decimos que la secuencia C es un camino dentro de una red R si C es una secuencia de elementos de R tales que existe un arco entre todo par de elementos consecutivos. Así, las secuencias 3 4 y 1 2 4 son caminos dentro la red ejemplo del primer apartado, pero no lo son ni 1 2 3 ni 4 2 1.

Decimos que la red A es la extensión de la red B si se cumplen las condiciones siguientes:

• Ambas redes tienen los mismos elementos.
• Si existe un camino de m a n en B, entonces existe un arco de m a n en A.

Es decir, la extensión de una red consiste en hacer explícitos todos los caminos que existen en dicha red, añadiendo arcos adicionales. La figura siguiente muestra un ejemplo de extensión de una red que requiere añadir cuatro nuevos arcos:

Se pide un programa que, dada una red, construya su extensión. Dicho programa debe procesar un fichero de entrada, de nombre "RED3.DAT", que contendrá la configuración de la red en el mismo formato que los apartados anteriores:

Línea 1: un carácter numérico (dígito) que representa el valor de N para la red.

Líneas siguientes: cada línea contendrá una o más parejas de valores naturales, representando cada una de ellas un arco entre dos elementos de la red. Cada natural se representa mediante un dígito; dos naturales consecutivos están siempre separados por un único espacio en blanco.

La salida debe almacenarse en el fichero "RED3.RES" y debe contener todos los arcos de la red construida. Cada arco se almacenará en una única línea, de la manera habitual:

En toda línea: una pareja de valores naturales, separados por un único espacio en blanco, y representados cada uno de ellos por un dígito. Cada pareja representa un arco entre dos elementos de la red.

Las líneas de la salida deben aparecer ordenadas: primero, los arcos que salen del elemento 1 ordenadamente según el elemento al que van a parar; a continuación, los que salen del elemento 2 ordenadamente según el elemento al que van a parar; etc. A continuación, se muestra el contenido de los ficheros para la red del ejemplo anterior:

Apartado 4

Decimos que la red A es una simplificación de la red B si se cumplen las condiciones siguientes:

• Ambas redes tienen los mismos elementos.
• El conjunto de arcos de A está incluido en el conjunto de arcos de B.
• La extensión de A y B es la misma.

Decimos además que A es una simplificación mínima de B si no existe ninguna simplificación de B con menos arcos que A. Es decir, una simplificación mínima de una red consiste en quitar todos los arcos que se pueda pero conservando los caminos que hay dentro de la red: si hay un camino entre dos elementos dentro de B, este camino debe existir también dentro de A. En la figura siguiente mostramos una red (izquierda) y su simplificación mínima (derecha):

Se pide un programa que, dada una red, construya una simplificación mínima (puede haber más de una). Dicho programa debe procesar un fichero de entrada de nombre "RED4.DAT" y generar otro de salida de nombre "RED4.DAT", siendo la descripción de ambos idéntica a la de "RED3.DAT" y "RED3.RES", respectivamente. Así, el ejemplo anterior puede representarse con los ficheros: