Tarea 3 de Almacenamiento y Recuperación de la
Información
Trimestre 2008 Primavera
Entrega: 28 de julio de
2008 a las 22:00.
Sea G = (V, E) una gráfica. Se dice que G es bipartita si se puede dividir V en
dos subconjuntos A y B tales que no existe ninguna arista entre dos
vértices de A ni ninguna arista entre dos vértices de B
(dicho de otra forma, todas las aristas de G están entre un
vértice en A y un vértice en B). Se puede demostrar que G
es bipartita si y sólo si no
contiene un ciclo de longitud impar.
Escribe un programa bipartitaNN
que decida si una gráfica es bipartita o no, donde NN son los dos
dígitos de la
clave que le fue proporcionada por el profesor. Página de prueba.
La entrada al programa estará en el archivo bipartita.ent y consiste de un
renglón con un entero N (la cantidad de vértices de G)
seguido de N renglones con N enteros 0 o 1 cada uno (la matriz de
adyacencia de G). Puedes suponer que los vértices de G
están numerados del 1 al N y que 2 <= N <= 100.
La salida del programa deberá estar en el archivo bipartita.sal y consiste de un
renglón con un entero R (1 si G es bipartita y 0 si no lo es).
En el caso de que R sea bipartita
el segundo renglón deberá contener la cantidad P de
vértices en A y el tercer renglón deberá contener
una lista con los P vértices en A (ordenados de menor a mayor).
En el caso de que R no sea bipartita
el segundo renglón deberá contener la longitud L de un
ciclo impar C de G y el tercer renglón deberá contener
una lista con los L vértices de C (en el orden en el que
aparezcan en el ciclo).
Observe que en el primer ejemplo también se pudo responder con P
= 2 y A = {3, 4} y que en el segundo ejemplo también se pudo
responder con L = 5 y C = (1, 4, 2, 3, 5). En general, para cada
gráfica G la respuesta R siempre es la misma, pero el resto de
la respuesta puede tener varias opciones. Para esta tarea basta que
dé cualquier respuesta correcta.
Pista:Si G es bipartita entonces cualquier
algoritmo de búsqueda debe pasar de un vértice en A a uno
en B o viceversa. ¿Qué puedes decir si el algoritmo pasa
de un vértice en A a otro que ya estaba en A?