Prac 2012

Algoritmos y Estructuras de Datos III
Segundo Cuatrimestre de 2012
http://www.dc.uba.ar/people/materias/aed3
Normas basicas de higiene y
seguridad
DEPTO. DE COMPUTACION - FCEyN - UBA
Por resolucion 802/98 del Consejo Directivo de la Facultad cada Departamento debe elaborar un
conjunto de Normas Basicas de Seguridad para ser incluidas en las Guas de Trabajos Practicos de todas
las materias. A continuacion transcribimos las normas aprobadas por el Departamento de Computacion
Las normas basicas de higiene y seguridad son un conjunto de medidas destinadas a proteger la salud
de todos, prevenir accidentes y promover el cuidado del material de los laboratorios. Son un conjunto
de practicas de sentido comun: el elemento clave es la actitud responsable y la concientizacion de todos:
personal y alumnado.
RESPETELAS Y HAGALAS RESPETAR
1. Se debera conocer la ubicacion de los elementos de seguridad en el lugar de trabajo, tales como:
matafuegos, salidas de emergencia, accionamiento de alarmas, etc.
2. Observar de que clase A, B o C es cada matafuego ubicado en el Departamento de Compu-
tacion, y verificar que material combustible papel, madera, pintura, material electrico se puede
apagar con el. Por ejemplo, nunca usar un matafuegos clase A para apagar fuego provocado por
un cortocircuito.
3. Salidas: Ante una emergencia: se podra solicitar a un docente JTP o profesor, u otra persona
autorizada que obtenga la llave de la puerta de planta baja. La persona autorizada que abra la
puerta se hara responsable del cierre de la puerta y de la devolucion de la llave.
4. Las unicas ventanas sin reja son las de los cuartos 11 y 12, dan a un balcon.
5. No se deben bloquear las rutas de escape o pasillos con equipos, mesas, maquinas u otros elementos
que entorpezcan la correcta circulacion.
6. No se permitira comer, beber, ni fumar en los laboratorios. Recordar que el polvo y la tiza danan
las PC.
7. No se permitira enchufar ni desenchufar perifericos a las CPU de los laboratorios sin la supervision
del docente o administradores de la red. No se modificara la instalacion de ningun equipo.
8. No se permitiran instalaciones electricas precarias o provisorias. Se dara aviso inmediato a la
Secretara Tecnica en caso de filtraciones o goteras que puedan afectar las instalaciones o equipos
y puedan provocar incendios por cortocircuitos (interno 355).
9. Es imprescindible mantener el orden y la limpieza. Cada persona es responsable directa del lugar
donde esta trabajando y de todos los lugares comunes.
10. Los laboratorios contaran con un botiqun de primeros auxilios con los elementos indispensables
para atender casos de emergencia.
1
Procedimientos ante emergencias
a. Emergencias medicas
Si ocurre una emergencia tal como: cortes o abrasiones, quemaduras o ingestion accidental de algun
producto qumico, toxico o peligroso, se debera proceder:
a) A los accidentados se les proveeran los primeros auxilios.

b) Simultaneamente se tomara contacto con el Servicio Medico (Interno 482), o al Servicio Medico
de Deportes (4576-3451 / 3459)
c) Avise al Jefe de Laboratorio o autoridad del Departamento, quienes solicitaran asistencia de la
Secretara Tecnica (interno 380) para que enven personal del Departamento de Mantenimiento,
Seguridad y Control o Servicios Generales segun correspondan.
d ) El Jefe de Departamento notificara el accidente al Servicio de Higiene y Seguridad para su
evaluacion e informe, donde se determinaran las causas y se elaboraran las propuestas para
modificar dichas causas y evitar futuras repeticiones.
e) Centros para requerir ayuda medica:
S.A.M.E. Telefono 107
Hospital Pirovano
Av. Monroe 3555 Tel. 4542-5552 / 9279
INTOXICACIONES
Hospital de Ninos. Dr. R. Gutierrez
Sanchez de Bustamante 1399. Capital Federal. Tel: 4962-6666.
Hospital de Ninos. Dr. P. de Elizalde
Av. Montes de Oca 40 Tel. 4307-7491. Toxicologa: 4300-2115
QUEMADURAS
Hospital de Quemados
P. Goyena 369 Tel. 4923-4082 / 3022
OFTALMOLOGIA
Hospital Santa Luca
San Juan 2021 Tel. 4941-7077
Hospital Dr. P. Lagleyze
Av. Juan B. Justo 4151 Tel. 4581-0645 / 2792
b. Incendio
Mantenga la calma. Lo mas importante es ponerse a salvo y dar aviso a los demas.
Si hay alarma, accionela. Si no grite para alertar al resto.
Se dara aviso inmediatamente al Departamento de Seguridad y Control (Interno 311) informando
el lugar y las caractersticas del siniestro.
Si el fuego es pequeno y sabe utilizar un extintor, uselo. Si el fuego es de consideracion, no se
arriesgue y manteniendo la calma ponga en marcha el plan de evacuacion.
Si debe evacuar el sector apague los equipos electricos y cierre las llaves de gas y ventanas.
Evacue la zona por la ruta asignada.
No corra, camine rapido, cerrando a su paso la mayor cantidad de puertas. No utilice ascensores.
Descienda siempre que sea posible.
No lleve consigo objetos, pueden entorpecer su salida.
Si pudo salir, por ninguna causa vuelva a entrar. Deje que los equipos especializados se encarguen.
Telefonos utiles:
BOMBEROS: Telefono 100
2
DIVISION CENTRAL DE ALARMA: 4381-2222 / 4383-2222 / 4304-2222.
CUARTEL V DE BOMBEROS DE BELGRANO: Obligado 2254 Capital Tel. 4783-2222
BOMBEROS DE VICENTE LOPEZ: Av. Maipu 1669 Vicente Lopez. Tel. 4795-2222
BOMBEROS DE SAN ISIDRO: Santa Fe 650 Martnez. Tel. 747-2222
c. Corriente electrica
Es imprescindible la concientizacion del riesgo que engendra la corriente electrica. Ya que si bien no es
la mayor fuente de accidentes, se trata generalmente de accidentes graves, en muchos casos mortales.
Los incendios provocados por causas electricas son muy frecuentes. Ellos ocurren por: sobrecalenta-
miento de cables o equipos bajo tension debido a sobrecarga de los conductores; sobrecalentamiento
debido a fallas en termostatos o fallas en equipos de corte de temperatura; fugas debidas a fallas
de aislacion; autoignicion debida a sobrecalentamiento de materiales inflamables ubicados demasiado
cerca o dentro de equipos bajo tension, cuando en operacion normal pueden llegar a estar calientes;
ignicion de materiales inflamables por chispas o arco.
Shock Electrico
Un shock electrico puede causar desde un sensacion de cosquilleo hasta un desagradable estmulo
doloroso resultado de una perdida total del control muscular y llegar a la muerte.
Control de los riesgos electricos

Los factores principales a considerar son:
el diseno seguro de las instalaciones
el diseno y construccion de los equipos de acuerdo a normas adecuadas
la autorizacion de uso despues que se ha comprobado que es seguro
el mantenimiento correcto y reparaciones
las modificaciones que se efectuen se realicen segun normas
Las precauciones generales contra el shock electrico son:
la seleccion del equipo apropiado y el ambiente adecuado
las buenas practicas de instalacion
el mantenimiento programado y regular
el uso de acuerdo a las instrucciones del fabricante
La proteccion contra el shock electrico se consigue usando:
equipos de maniobra con baja tension
la doble aislacion o la construccion aislada
las conexiones a tierra y la proteccion por equipos de desconexion automatica
la separacion electrica entre las fuentes y la tierra
Frecuentemente se usan adaptadores de enchufes. Tenga siempre en cuenta que cuando se usan estos
aditamentos puede desconectarse la tierra del equipo que esta usando.
3
Informacion sobre la materia
Programa
1 Algoritmos. Definicion de algoritmo. Modelos de computacion: modelo RAM, Maquina de Turing.
Complejidad, definicion, complejidad en el peor caso, en el caso promedio. Algoritmos de tiempo poli-
nomial y no polinomial. Lmite inferior. Ejemplo: analisis de algoritmos de ordenamiento. Algoritmos
recursivos. Analisis de la complejidad de algoritmos recursivos.
Tecnicas de diseno de algoritmos: dividir y conquistar, backtracking, algoritmos golosos, programacion
dinamica.
2 Grafos. Definiciones basicas: adyacencia, grado de un nodo, isomorfismos, caminos, conexion, etc.
Grafos bipartitos. Arboles: caracterizacion, arboles orientados, arbol generador. Enumeracion. Grafos
eulerianos y hamiltonianos. Planaridad. Coloreo. Numero cromatico. Matching, conjunto independien-
te, recubrimiento. Recubrimiento de aristas y vertices.
3 Algoritmos en grafos y aplicaciones. Representacion de un grafo en la computadora: matrices
de incidencia y adyacencia, listas. Algoritmos de busqueda en grafos: BFS, DFS, A . Mnimo arbol
generador, algoritmos de Prim y Kruskal. Arboles ordenados: codigos unvocamente descifrables. Algo-
ritmos para deteccion de circuitos. Algoritmos para encontrar el camino mnimo en un grafo: Dijkstra,
Ford, Dantzig. Planificacion de procesos: PERT/CPM. Algoritmos heursticos: ejemplos. Nociones de
evaluacion de heursticas y de tecnicas metaheursticas. Algoritmos aproximados. Heursticas para el
problema del viajante de comercio. Algoritmos para detectar planaridad. Algoritmos para coloreo de
grafos. Algoritmos para encontrar el flujo maximo en una red: Ford y Fulkerson. Matching: algoritmos
para correspondencias maximas en grafos bipartitos. Otras aplicaciones.
4 Problemas NP-completos. Problemas tratables e intratables. Problemas de decision. P y NP. Ma-
quinas de Turing no determinsticas. Problemas NP-completos. Relacion entre P y NP. Problemas de
grafos NP-completos: coloreo de grafos, grafos hamiltonianos, recubrimiento mnimo de las aristas,
corte maximo, etc.
4
Docentes
e-mail: [email protected]
Teoricas
Marina Groshaus [email protected]
Irene Loiseau [email protected]
Practicas
Alejandro Strejilevich de Loma [email protected]
Daro Alejandro Guzik [email protected]
Michel Jonathan Mizrahi [email protected]
Federico Lebron [email protected]
Laboratorio
Emilio Oca [email protected]
Pablo Haramburu [email protected]
Hernan Modrow [email protected]
Xavier Warnes [email protected]
Alumnos
e-mail: [email protected]
5
Regimen de aprobacion
1. Se tomaran dos examenes parciales, el primero el 13/10/2012 y el segundo el 05/12/2012.
2. Se podra recuperar una vez cada parcial. El recuperatorio del primer parcial se tomara el 12/12/2012
y el del segundo el 19/12/2012.
3. Se realizaran 3 trabajos practicos cuyas primeras fechas de entrega seran el 07/09/2012, el 05/10/2012
y el 16/11/2012. Para mas detalles sobre la entrega y las fechas de recuperatorio de los TP leer mas
abajo las instrucciones para el laboratorio.
4. Para aprobar los practicos y poder dar final como alumno regular, se requiere haber aprobado los dos
parciales con nota 5 (cinco) o mas en cada uno, y los trabajos practicos con 5 (cinco) o mas en cada
uno. La aprobacion de los trabajos practicos se firmara unicamente en las fechas de toma o entrega
de examenes del segundo cuatrimestre de 2012. No se firmaran los practicos despues de comenzado el
siguiente cuatrimestre.
5. Para aprobar la materia por promocion (es decir, sin rendir examen final) se requiere:
a. Haber aprobado los dos parciales con nota 5 (cinco) o mas en cada uno y tener 7 (siete) o mas de
promedio.
b. Haber aprobado los trabajos practicos con nota 5 (cinco) o mas en cada uno y tener 7 (siete) o
mas de promedio.
c. Tener los finales de las correlativas aprobados antes de la ultima fecha de finales del cuatrimestre.
Las promociones se firmaran unicamente en las fechas de final correspondientes al segundo cuatrimestre
de 2012.
6. Tanto para firmar los practicos como para la promocion la nota puede ser la obtenida en el recupera-
torio.
7. Toda informacion referente a la materia sera publicada en la cartelera de Algoritmos y Estructura de
Datos III y/o en la pagina web y/o sera enviada a la lista de alumnos de la materia por e-mail.
6
Pautas generales para el Laboratorio
Se realizaran 3 trabajos practicos, en grupos de 3 o 4 personas. La informacion relativa a cada
trabajo practico estara disponible el la pagina web de la materia y en los enunciados de cada TP
se podran estipular condiciones particulares que invaliden algunas de las aqu descriptas.
Instrucciones generales para los trabajos

Normalmente los programas leeran los datos desde archivos de entrada, y escribiran los resultados
a archivos de salida.
Las funciones pedidas deben estar claramente separadas del codigo que se utiliza para probarlas.
Los lenguajes de programacion permitidos a utilizar se estableceran en las clases de laboratorio.
Debe intentarse minimizar la complejidad de los algoritmos.
No es necesario programar interfases graficas.
Fecha de entrega
Los trabajos deben presentarse en las fechas que figuran arriba. Cada trabajo puede recuperarse
una vez. Las fechas son tentativas y los cambios seran informados a los alumnos con antelacion
suficiente.
Para los trabajos entregados en la primera fecha de entrega, el recuperatorio es una semana despues
de la correccion por parte de los docentes.
Para los trabajos no entregados en primera fecha, el recuperatorio es en la fecha de recuperatorio
prevista en el enunciado.
La entrega de cada trabajo practico (o su recuperatorio) debe realizarse en el da y horario previsto
para ello, y en mano de alguno de los docentes del laboratorio, todo ello sin excepcion.
Que hay que entregar

Por cada trabajo practico debe entregarse en una carpeta un informe y un diskette o CD.
El informe debe contener el numero de grupo, datos de los integrantes del grupo (incluyendo e-mail),
un ndice inicial y el enunciado del trabajo practico.
En general, cada ejercicio se presentara en una seccion separada incluyendo: introduccion, detalles
de implementacion, pseudocodigo, respuestas a las preguntas planteadas, analisis de la complejidad
de los algoritmos principales, comentarios, conclusiones, referencias (mas o menos en ese orden).
El informe debe ser autocontenido (entenderse por s mismo).
Los programas deben estar correctamente indentados y comentados para facilitar su lectura.
Las hojas no deben caerse de la carpeta y debe ser posible leer el informe con comodidad.
El diskette o CD no debe caerse de la carpeta.
Cada ejercicio debe presentarse en un directorio distinto incluyendo:
archivos con los fuentes, archivo del proyecto (si lo hubiera), archivo ejecutable
archivos de entrada de datos (si los hubiera), archivos de salida de datos (si los hubiera)
El diskette o CD tambien debe contener el informe, en algun formato standard.
7
Bibliografa
En cada practico se mencionan las referencias que mejor se ajustan a la forma en que sera dado
el tema correspondiente. La catedra tiene ejemplares de todos los libros mencionados en esta bi-
bliografa, que pueden ser solicitadas por los alumnos a los profesores. Hasta donde llega nuestro
conocimiento, los libros marcados con (a) estan en la biblioteca central (Pabellon II), los marcados
con (b) en la Hemeroteca del Departamento de Matematica (segundo piso del Pabellon I) y los
marcados con (c) en la Infoteca del Departamento de Computacion.
Bibliografa basica:
[1] R. Ahuja, T. Magnanti, J. Orlin, Network flows, Prentice Hall, 1993. (a,c)
[2] G. Brassard, P. Bratley, Fundamental of Algorithmics, Prentice Hall, 1996. (c)
[3] M. Garey, D. Jonhson, Computers and Intractability: A Guide to the Theory of NP-
Completeness, W. Freeman and Co., 1979. (a,c)
[4] J. Gross, J. Yellen, Graph theory and its applications, CRC, 1999. (c)
[5] F. Harary, Graph theory, Addison-Wesley, 1969 (hay una reedicion de 1996). (a)
Bibliografa de consulta:
[6] A. Aho, J. Hopcroft, J. Ullman, The design and analysis of computer algorithms, Addison-
Wesley, 1974 (hay edicion en castellano). (a,c)
[7] A. Aho, J. Hopcroft, J. Ullman, Data structures and algorithms, Addison-Wesley, 1983 (hay
edicion en castellano). (a,c)
[8] A. Aho, J. Hopcroft, J. Ullman, Foundations of Computer Science, Computer Science Press,
1995.
[9] M. Albertson, J. Hutchinson, Discrete Mathematics with Algorithms, Wiley, 1988. (a,c)
[10] G. Baum, Complejidad, Kapelusz (I EBAI), 1986. (c)
[11] C. Berge, The theory of graphs and applications, Wiley, 1958. (a)
[12] C. Berge, Graphs, North-Holland, 1985. (b)
[13] N. Bigs, E. Lloyd, R. Wilson, Graph theory: 1736-1936, Oxford University Press, 1976.
[14] J. Bondy, U. Murty, Graph theory with applications, Macmillan Press, 1976.
[15] R. Campello, N. Maculan, Algoritmos e heursticas, Editorial da Universidade Federal Flumi-
nense, 1994. (a,c)
8
[16] N. Deo, Graph theory with applications to engineering and computer science, Prentice-Hall, 1974.
[17] S. Even, Graph algorithms, Computer Science Press, 1979.
[18] L. Ford, D. Fulkerson, Flows in Networks, Princeton University Press, 1962. (b)
[19] M. Gondran, M. Minoux, Graphs and Algorithms, John Wiley and Sons, 1984.
[20] E. Horowitz, S. Sahni, Fundamentals of Computer Algorithms, Computer Science Press, 1978.
[21] D. Knuth, The art of computer programming, Addison-Wesley, 1973. (a,c)
[22] Mc Hugh James, Algorithmic Graph Theory, Prentice-Hall International, 1990.
[23] C. Papadimitriou, Computational Complexity, Addison-Wesley, 1995.
[24] V. Rayward-Smith, I. Osman, C. Reeves, G. Smith, Modern heuristic search methods, Wiley,
1996.
[25] C. Reeves, Modern heuristic techniques for combinatorial problems, Blackwell, 1993.
[26] R. Sedgewick, Algorithms in C++, Addison-Wesley, 1998. (a,c)
[27] I. Sominsky, Metodo de Induccion Matematica, Lecciones populares de matematica, Editorial MIR,
Moscu, 1985.
[28] M. Syslo, N. Deo, J. Kowaljk, Discrete Optimization Algorithms, Prentice Hall, 1983.
[29] M. Swamy, D. Thulasiraman, Graphs, networks and algorithms, John Wiley and Sons, 1981.
[30] J. Szwarcfiter, Grafos e algoritmos computacionais, Editora Campus, Rio de Janeiro, 1987.
[31] R. Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathema-
tics, 1993. (a)
[32] A. Tucker, Applied Combinatorics, John Wiley and Sons, 1984. (c)
9
Practica 1
Referencias para este practico: [9], [8], [27]
1.1. Probar por induccion:

a. 1 + 2 + . . . + n = n(n + 1)/2, n 1
b. 1 + 3 + 5 + . . . + (2n + 1) = (n + 1)2 , n 0
c. 12 + 22 + . . . + n2 = n(n + 1)(2n + 1)/6, n 1
d. 1 + 22 32 + . . . + (1)n n2 = (1)n n(n + 1)/2, n 1
e. (1 + 2 + 3 + . . . + n)2 = 13 + 23 + . . . + n3 , n 1
f. 1 1! + 2 2! + . . . + n n! = (n + 1)! 1, n 1
1.2. Encontrar una formula para la siguiente suma y demostrarla por induccion: 1 + 2 + 22 + 23 + 24 +
. . . + 2n .
1.3. La poblacion de una colonia de hormigas se duplica todos los anos. Si se establece una colonia
inicial de 10 hormigas, cuantas hormigas habra despues de n anos?
1.4. Probar por induccion que para n 5 se verifica que 2n > n2 .
1.5. La poblacion de gatos en un deposito tiene la propiedad de que el numero de gatos en un ano es
igual a la suma de la cantidad de gatos de los dos anos anteriores. Si en el primer ano haba un
solo gato, y en el segundo dos (suponiendo ello posible!), probar que el numero de gatos en el ano
n es:
!n+1 !n+1
r
1 1+ 5 1 5

5 2 2
1.6. Cual es el error en la siguiente demostracion?

Se quiere probar que los elementos x1 , x2 , x3 , . . . , xn , de un conjunto son iguales entre s.
i. Paso inicial (n = 1): El conjunto tiene un solo elemento x1 que es igual a si mismo.
ii. Paso inductivo: Supongamos que x1 = x2 = x3 = . . . = xn1 . Como tambien vale la hipotesis
inductiva para un conjunto de dos elementos, tenemos que xn1 = xn y por tanto resulta que
x1 = x2 = x3 = . . . = xn1 = xn .
1.7. Cual es el error en la siguiente demostracion?
Se quiere probar que a 6= 0 vale que an = 1.
i. Paso inicial (n = 0): an = 1 a.
ii. Paso inductivo: Supongamos que an1 = 1. Entonces an = (an1 an1 )/an2 = (11)/1 = 1.
10
Practica 2
Referencias para este practico: [2], [8], [26], [9]
2.1. Que cantidad de bits se necesitan para almacenar (en binario) un entero m?
2.2. a. Suponiendo que en una computadora dada, una operacion basica de un algoritmo tarda 1 mi-
crosegundo en ejecutarse y que la complejidad del mismo es aproximadamente 10n (o sea un
problema de tamano n se resuelve en aproximadamente 10n microsegundos, donde n es el ta-
mano del problema), estimar el tiempo que la maquina tardara en resolver problemas donde n
sea 20, 50, 100, 500 y 1000.
b. Idem a. para algoritmos de complejidades 1000n, log2 n, 2n/3 , nlog2 n y 2n .
c. Cual es el problema de mayor tamano que puede resolverse en el tiempo que antes se resolva
un problema de tamano n = 1000 en cada uno de los casos anteriores, si se dispone de una
maquina 10000 veces mas veloz?
2.3. a. Decidir si son verdaderas o falsas las siguientes afirmaciones y justificar:
i. n es O(n)
ii. 3n2 + 7n + 4 es O(n2 )
iii. ni es O(nj ) si i < j
iv. n log2 (n) es O(n2 )
b. Mostrar que n! no es O(rn ), cualquiera sea el entero positivo r. Concluir que una complejidad
de O(n!) es peorque exponencial de cualquier base.
2.4. Decir cual es la complejidad de los siguientes algortimos:
a. Dadas dos variables x, y:
PASO 1: poner aux = x
PASO 2: poner x = y
PASO 3: poner y = aux
b. Dado un vector v, su dimension d y un elemento e:

PASO 1: poner i = 1
PASO 2: mientras i < d y e 6= v[i] hacer
PASO 3: i=i+1
PASO 4: si e = v[i] imprimir i
PASO 5: sino imprimir No se encontro
c. Dado un numero natural n:
funcion Factorial(n)
si n = 0 devolver 1
sino devolver (n Factorial(n 1))
fin funcion
d. Dado un vector v, y su dimension d:
11
PASO 1: para i desde 1 hasta d hacer
PASO 2: poner min = i
PASO 3: para j desde i hasta d hacer
PASO 4: si v[j] < v[min] poner min = j
PASO 5: poner aux = v[i]
PASO 6: poner v[i] = v[min]
PASO 7: poner v[min] = aux
2.5. a. Mostrar que el siguiente algoritmo que lista todas las permutaciones de n elementos funciona
correctamente y determinar su complejidad:
PASO 1: poner j = 1, construir la permutacion {1} y poner S = {{1}}
PASO 2: poner j = j + 1
PASO 3: para cada permutacion de j 1 elementos {a1 , a2 , . . . , aj1 } en S, hacer:
PASO 4: poner P = {a1 , a2 , . . . , aj1 , j}.
PASO 5: si j < n poner S = S {P }. Si j = n imprimir P .
PASO 6: para i = j 1 hasta 1 hacer
PASO 7: intercambiar las posiciones i e i + 1 de P
PASO 8: si j < n poner S = S {P }.
PASO 9: si j = n imprimir P .
PASO 10: si j < n ir a 2. Si j = n parar.
b. Cuanto tardara su computadora en correr este algoritmo para n = 11, n = 15, n = 20, n = 24?
2.6. a. Escribir en forma de algoritmo el metodo clasico para pasar un numero de su representacion
binaria a su representacion decimal. Cual es la complejidad de este algoritmo?
b. Analizar si los siguientes pasos corresponden o no a un algoritmo (supuestamente para determi-
nar la representacion binaria de un entero dado m).
PASO 1: escribir una secuencia cualquiera de 0s y 1s.
PASO 2: pasar el numero anterior a decimal en la forma clasica
(algoritmo del punto a.)
PASO 3: si el numero obtenido en 2 es m parar, sino volver al paso 1.
c. Idem b. para:
PASO 1: poner k = 1.
PASO 2: listar todas las posibles combinaciones de k digitos binarios
en orden creciente;
transformar cada una de ellas a decimal por el metodo clasico
(algoritmo del punto a.);
si alguna de ellas es igual a m parar.
PASO 3: poner k = k + 1 e ir al paso 2.
d. Escribir el algoritmo clasico para pasar de la representacion decimal a binaria de un numero

dado. Determinar su complejidad y compararla con la del algoritmo del punto c.
2.7. a. Escribir un procedimiento que dado un numero entero, devuelva su factorizacion en numeros
primos.
b. Escribir un algoritmo para reducir una fraccion dada x/y a sus terminos mas chicos.
c. Determinar la complejidad de los algoritmos de los puntos a. y b.
2.8. a. Escribir el algoritmo de Euclides para calcular el maximo comun divisor entre 2 numeros b y c en
forma recursiva y no recursiva. Mostrar que su complejidad es O(mn{b, c}). Puede construir
un ejemplo (un peor caso) donde esta complejidad efectivamente se alcance? Puede hacerlo
para b y c tan grandes como se desee?
12
b. Analizar el siguiente algoritmo para determinar el maximo comun divisor entre dos numeros b
y c, y mostrar que su complejidad tambien es O(mn{b, c}).
PASO 1: poner g = mn{b, c}
PASO 2: mientras g > 1 hacer
PASO 3: si b/g y c/g son enteros, informar mcd = g y parar.
PASO 4: poner g = g 1
PASO 5: informar mcd = 1 y parar
c. Las complejidades calculadas para los algoritmos de las partes a. y b. son iguales. Cual de los
dos algoritmos elegira? Justificar y comentar.
d. Probar que se puede mejorar la complejidad calculada en a. demostrando que el algoritmo de
Euclides es en realidad O(log2 (mn{b, c})).
2.9. a. Escribir algoritmos para realizar suma, resta y multiplicacion de matrices. Determinar la com-
plejidad y expresarla en funcion de la dimension de las matrices.
b. Escribir un algoritmo que dada una matriz A y un numero n calcule An (o sea A A . . . A,
n veces). Determinar la complejidad del mismo.
c. Escribir y determinar la complejidad del algoritmo de Gauss (triangulacion) para resolver un
sistema de n ecuaciones lineales con n incognitas.
d. Idem c. para el metodo de los determinantes (Regla de Cramer).
e. Determinar para los algoritmos de los puntos a., b., c. y d. cual es la importancia del peor caso.
2.10. Cual es la complejidad en el caso promedio del algoritmo de busqueda secuencial?
2.11. Cual es el lmite inferior para la complejidad de un algoritmo que determine el maximo de n
numeros?
2.12. a. Escribir un algoritmo para ordenar n elementos por el metodo de burbujeo y probar que su
complejidad es O(n2 ).
b. Escribir algoritmos para ordenar n elementos por seleccion e insercion y calcular su complejidad.
c. Cual de los algoritmos presentados en a. y b. es mejor?
2.13. Presentamos a continuacion otro algoritmo de ordenamiento llamado Quicksort. Sea S la secuencia
que se va a ordenar.
procedimiento Quicksort(S)
si long(S) 1 entonces devolver S
sino
Partir(S,j)
poner S1 {S[i] : i < j}
poner S2 {S[i] : i > j}
devolver Quicksort(S1 ) S[j] Quicksort(S2 )
fin procedimiento
13
procedimiento Partir(S,limite)
poner i 1
poner k long(S)
mientras i < k hacer
mientras i k L S[i] S[1] hacer
poner i i + 1
mientras i < k L S[k] > S[1] hacer
poner k k 1
si i < k entonces
Intercambiar(S, i, k)
fin mientras
Intercambiar(S, 1, i 1)
poner limite i 1
fin procedimiento
Partir ordena S de tal forma que para todo i < limite , S[i] es menor o igual que S[limite], y para
todo i > limite, S[i] es mayor que S[limite]. S[limite] es el primer elemento de la secuencia inicial,
al que llamaremos pivote.
a. Ordenar la secuencia 20, 52, 45, 35, 15, 80, 76, 25 usando Quicksort.
b. Cual es el peor caso para el algoritmo Quicksort? Cual es la complejidad del mismo?
c. Cual es la complejidad en el caso promedio?
d. Si en Partir se toma como pivote el elemento medio de la secuencia, responder b. y c.
e. Si el pivote es la media entre el primer elemento, el ultimo y el elemento medio, responder a. y
b.
(Modificando: S2 = {S[i]/i j} y retornando
Quicksort(S1 ) Quicksort(S2 ), pues la media puede no ser un elemento de la secuencia)
f. Por que se trata que el pivote se acerque a la mediana?
2.14. * El algoritmo Meansort es una modificacion de Quicksort. Para dividir la secuencia original (pri-
mera llamada), se utiliza como pivote el primer elemento o el elemento medio de la secuencia.
Durante la particion se calcula la media de cada subsecuencia, que seran usadas como pivote de la
particion siguiente.
a. Ordenar la secuencia de 2.13a usando Meansort.

b. Cual es el peor caso para Meansort? Cual es la complejidad de Meansort?
c. Cual es la complejidad en el caso promedio?
2.15. * B-sort es otra modificacion de Quicksort. En este caso modifica Quicksort de la siguiente manera:
se toma como pivote el elemento medio de la secuencia. Durante la particion, si S[k] > S[k + 1] se
intercmbian, asegurando que S[k] es el menor elemento de la subsecuencia derecha. Si S[i] < S[i1]
se intercambian, siendo por lo tanto S[i] el mayor elemento de la subsecuencia izquierda.
a. Ordenar la secuencia de 2.13a usando B-sort.

b. Que sucede si durante la particion no se intercambian S[k] con S[k + 1]? Y que con S[i] y
S[i 1]?
c. Cuantas comparaciones seran necesarias si la secuencia tiene tres elementos?
d. Cual es la complejidad del peor caso de este algortimo?
e. Cual es la complejidad en el caso promedio?
2.16. Un heap o parva es un arbol binario o casi binario (puede haber un nodo que tenga una sola hoja
como sucesora) organizado de tal manera que si a cada nodo le corresponde un numero, entonces
el valor de un nodo es mayor o igual que el de sus hijos. Por lo tanto, la raz del arbol es el nodo de
mayor valor. Esta estructura se usa para dar otro algoritmo de ordenamiento llamado Heapsort.
14
a. Disenar un algoritmo para convertir un arbol binario a un heap. Cual es la complejidad? Aplicar
ese algoritmo para el arbol siguiente:
5
10 13
20 8 15 7
16 7 12
b. Dado un heap probar que al podar la raz alcanza con O(log2 (n)) operaciones para rearmar uno
nuevo.
c. A partir de esto se construye un algoritmo, Heapsort, para ordenar un vector de n numeros.
Escribirlo detalladamente. (Sugerencia: los ndices van de 0 a n 1, donde dado i, su hijo
izquierdo es 2i + 1 y su hijo derecho es 2i + 2)
2.17. a. Escribir un algoritmo para ordenar una secuencia por el metodo Mergesort.
b. Determinar la complejidad del algoritmo enunciado.
c. En que casos es conveniente usar este metodo?
15
Practica 3
3.1. Escribir una funcion recursiva y una no recursiva para calcular los numeros de Fibonacci, definidos
del siguiente modo:
F0 = 0
F1 = 1
Fn = Fn1 + Fn2 , n 2
Determinar la complejidad de ambas. Cual resulta mejor?

3.2. El conocido problema de las torres de Hanoi fue planteado por primera vez por el matematico
frances Eduard Lucas del siguiente modo:
En el inicio de los tiempos Dios creo las torres de Brahma con 64 discos de oro puro
dispuestos en agujas de diamante. Cuando la hora llego ordeno a un grupo de padres
de un Monasterio en Tibet que dieran inicio al movimiento de los discos segun reglas
determinadas y aviso que concluido el trabajo las torres se desmoronaran dando inicio
al final de los tiempos.
Las reglas eran las siguientes:
Solo se puede mover un disco a la vez.
Un disco de mayor tamano no puede descansar sobre uno mas pequeno que el mismo.
Solo puedes desplazar el disco que se encuentre arriba en cada aguja.
a. Escribir un algoritmo recursivo para resolver este problema.

b. Demostrar que el algoritmo presentado en a. es correcto.
c. Analizar la complejidad del algoritmo.
d. Relacionar el resultado de c. con la formulacion que el matematico Lucas hizo del problema (el
final de los tiempos).
3.3. a. * Escribir un algoritmo recursivo para determinar, dado un conjunto de puntos en el plano cual
es el par de puntos que esta mas proximo entre si, de acuerdo a las siguientes ideas:
Ordenar los puntos de acuerdo a su coordenada x. Si todos los puntos tienen la misma
coordenada x, ordenar los puntos de acuerdo a su coordenada y, y para el resto del algoritmo
pensar las coordenadas intercambiadas.
Trazar una recta vertical que divida al conjunto en dos partes R1 y R2 de manera tal que
la cantidad de puntos en cada parte sea lo mas cercano posible a la mitad del total.
Calcular las distancias mnimas en cada parte, d1 y d2 .
Para calcular la distancia mnima en la union de los dos conjuntos, calcular primero d =
mn{d1 , d2 }.
Eliminar los puntos que esten a distancia mayor a d de la recta vertical que separa a R1 y
R2 .
Ordenar los puntos en cada Ri de acuerdo al valor de la coordenada y.
Calcular la distancia de cada uno de los puntos a sus vecinos (son a lo sumo 5). Si cualquiera
de estas distancias es menor que d, actualizar el valor de d.
16
b. Aplicar el algoritmo anterior al siguiente conjunto de puntos
{(1, 3,5), (1,3, 4,5), (2, 1), (2, 0,5), (0, 3), (0, 2,1),
(1,1, , 5), (2,5, 3,4), (1, 10), (0,5, 7), (0,7, 9),
(3, 4,5), (3, 1,2), (2, 0), (4,5, 0,9), (3,4, 6,7)}
c. Determinar la complejidad del algoritmo.
3.4. Hay que organizar un torneo que involucre a n competidores. Cada competidor debe jugar exacta-
mente una vez contra cada uno de sus oponentes. Ademas cada competidor debe jugar un partido
por da con la sola posible excepcion de un da en el cual no juegue.
a. Si n es potencia de 2 dar un algoritmo que use la tecnica de dividir y conquistar para armar el
fixture para que el torneo termine en n 1 das.
b. Si n > 1 no es potencia de 2 dar un algoritmo para armar el fixture para que el torneo termine
en n 1 das, si n es par o en n, si n es impar.
3.5. Sean P1 , P2 , . . . , Pn programas que se quieren almacenar en una cinta. El programa Pi requiere
si Kb de memoria. La cinta tiene capacidad para almacenar todos los programas. Se conoce la
frecuencia i con que se usa el programa Pi . La densidad de la cinta y la velocidad del drive
son constantes. Despues que un programa se carga desde la cinta la misma se rebobina hasta el
principio. Si los programas se almacenan en orden i1 , i2 , . . . , in el tiempo promedio de carga de un
programa es
X X
T =c ij sik
j kj
donde la constante c depende de la densidad de grabado y la velocidad del dispositivo. Queremos

construir un algoritmo goloso para determinar el orden en que se almacenan los programas que
minimice T .
Analizar las siguientes estrategias de almacenamiento:
i. en orden no decreciente de los si

ii. en orden no creciente de los i
iii. en orden no creciente de i /si
Como se podra demostrar que la ultima estrategia es la mejor? (Sugerencia: analizar en cada caso
que ocurre cuando dos elementos contiguos desordenados se ordenan.)
3.6. a. Se quiere dar el vuelto a un cliente usando el mnimo numero de monedas posibles. Hay monedas
de 1,5,10 y 25 centavos.(Hay al menos una de cada tipo) Analizar el siguiente algoritmo goloso
para resolver el problema:
Elegir en cada paso la moneda de mayor valor entre las disponibles.
Probar que si hay una solucion el algoritmo goloso siempre encuentra una solucion para estos
valores de las monedas.
b. Mostrar ejemplos que muestren que si tambien hay monedas de 12 centavos, o si no hay al menos
una moneda de cada tipo, puede ocurrir que el algoritmo no encuentre una solucion aunque la
haya.
3.7. a. Escribir un algoritmo para calcular los coeficientes binomiales usando el triangulo de Pascal, que
use la tecnica de programacion dinamica. Explicar porque se cumple en este caso el principio de
optimalidad.
b. Determinar la complejidad temporal y espacial del algoritmo de a.
c. Revisar el ejercicio 3.1 y ver que la misma idea de a. se aplica al calculo de los numeros de
Fibonacci.
3.8. Sea M Nmn una matriz de numeros naturales. Se desea obtener un camino que empiece en la
casilla superior izquierda ([1, 1]), termine en la casilla inferior derecha ([m, n]), y tal que minimice
la suma de los valores de las casillas por las que pasa. En cada casilla [i, j] hay dos movimientos
posibles: ir hacia abajo (a la casilla [i + 1, j]), o ir hacia la derecha (a la casilla [i, j + 1]).
17
a. Disenar un algoritmo eficiente basado en programacion dinamica que resuelva este problema.
b. Determinar la complejidad del algoritmo propuesto (temporal y espacial).
c. Exhibir el comportamiento del algoritmo sobre la matriz que aparece a continuacion.

2 8 3 4
5 3 4 5

1 2 2 1
3 4 6 5
3.9. Sea v = (v1 , v2 , . . . vn ) un vector de numeros naturales, y sea w N. Se desea intercalar entre
los elementos de v las operaciones + (suma), (multiplicacion) y (potenciacion) de tal manera
que al evaluar la expresion obtenida el resultado sea w. Para evaluar la expresion se opera de
izquierda a derecha ignorando la precedencia de los operadores. Por ejemplo, si v = (3, 1, 5, 2, 1), y
las operaciones elegidas son +, , y (en ese orden), la expresion obtenida es 3 + 1 5 2 1,
que se evalua como (((3 + 1) 5) 2) 1 = 400.
a. Disenar un algoritmo basado en programacion dinamica que dados v y w, encuentre una secuen-
cia de operaciones como la deseada, en caso de que tal secuencia exista.
b. Determinar la complejidad del algoritmo propuesto (temporal y espacial).
3.10. * Una fabrica electronica tiene un contrato para entregar las siguientes cantidades de radios en los
proximos 3 meses: mes 1, 200 radios, mes 2, 300 radios, mes 3, 300 radios. Cada radio fabricada
en los meses 1 y 2 cuesta 10 $ y si es fabricada en el mes 3, 12$. El costo de stock es de 1,50$ por
mes. El costo fijo de iniciar la produccion de radios un mes dado es 250$. Las radios fabricadas
durante un mes dado pueden ser entregadas ese mismo mes o despues. La produccion cada mes
debe ser un numero de radios multiplo de 100. El stock inicial es 0. Usar programacion dinamica
para determinar el plan de produccion optimo.
3.11. Dar un algoritmo de programacion dinamica para el problema de dar el vuelto con el menor numero
de monedas posible presentado en el ejercicio 3.6. Decir si funciona en todos los casos o solo en
algunos casos (infinito numero de monedas disponibles, para monedas de cualquier valor, etc.)
3.12. Sean u y v dos string de caracteres. Queremos transformar u en v con el menor numero de opera-
ciones posibles de alguno de los siguientes tipos:
borrar un caracter
agregar un caracter
cambiar un caracter
a. Por ejemplo uno puede transformar u = abbac en v = abcbc en tres pasos, (borrar b del segundo
lugar de u, agregar b en el penultimo lugar, cambiar la a que esta en el tercer lugar a c)
Es esta forma de transformar u en v optima?
b. Escribir un algoritmo de programacion dinamica que encuentre el mnimo numero de operaciones
necesarias para transformar u en v e informe cuales son las operaciones necesarias. Cual es la
complejidad del algoritmo en funcion de las longitudes de u y v?
3.13. Dar ejemplos de problemas donde no valga el principio de optimalidad.

3.14. a. Considerar el problema clasico de las 8 reinas que consiste en ubicar 8 reinas en un tablero de
ajedrez sin que ninguna amenace a las otras. Cuantas posibilidades habra que considerar si se
usa un algoritmo de fuerza bruta que analice todas las posiciones posibles?
b. Enunciar un algoritmo que use backtracking para resolver este problema. Es mejor que el de
a. ? Es un buen algoritmo?
3.15. Escribir un algoritmo de backtracking para la siguiente version del problema de la mochila: tenemos
n tipos de objetos. Un objeto de tipo i tiene un peso positivo wi y un valor positico vi . Suponiendo
que tenemos una cantidad no limitada de cada tipo de objetos y que la mochila puede cargar un
peso maximo de W, queremos maximizar el valor total de los objetos includos en la mochila.
18
3.16. a. El problema de la suma de subconjuntos consiste en, dado un conjunto S = {a1 , . . . , an } de
numeros naturales y otro numero natural w, determinar si existe un subconjunto S 0 de S tal
que la suma de los elementos de S 0 sea igual a w. Escribir un algoritmo para resolver este
problema que consista en revisar todos los subconjuntos de S para determinar si alguno suma
w. Este tipo de algoritmo se llama algoritmo de fuerza bruta.
b. Analizar la complejidad del algoritmo de a.
c. Se le ocurre alguna idea mejor para resolver este problema?
3.17. a. Decir cuales de los algoritmos de los practicos 2 y 3 usan la tecnica de dividir y conquistar.
Justificar.
b. Que algoritmos de los mismos practicos son algoritmos recursivos?
c. Se puede decir que siempre es mejor usar la version recursiva de un algoritmo? Al reves?
3.18. Clasificar todos los algoritmos de este practico en buenos y malos.
19
Practica 4
Referencias para este practico: [4], [14]

El objetivo de este practico es modelar los problemas usando grafos. Algunos no podran ser resueltos a
esta altura de la materia.
4.1. Hay un conjunto de cinco personas y un conjunto de 5 trabajos para realizar. Sean las personas
Carlos, Marcela, Pedro, Fernando y Andrea, y los trabajos a, b, c, d y e. Carlos esta capacitado
para realizar los trabajos c y d, Marcela para c, Pedro para a, b y e, Fernando para c y d, y Andrea
para b y e. Es posible realizar una distribucion del trabajo de modo que se puedan realizar todos
los trabajos simultaneamente?
4.2. Un raton va cavando un tunel mientras recorre un cubo de queso de 30cm de lado. Quiere que el
tunel pase por todos los subcubos de 10cm de lado. Si empieza por un subcubo en un vertice del
cubo de queso, y se mueve hacia un subcubo que todava no ha recorrido, puede terminar en el
centro del cubo?
4.3. El grafo de la figura representa una red telefonica. Los vertices representan centrales y las aristas
lneas telefonicas. Se quiere estudiar la vulnerabilidad de la red ante algun defecto.
c g i
a b d f
e h j
a. Determinar las lneas o centrales cuya salida de servicio impide que se realicen llamadas entre
dos centrales cualesquiera.
b. Dar conjuntos minimales de lneas que mantengan conectadas todas las centrales.
c. Dar un conjunto minimal de lneas que no contenga las siguientes aristas: (c, d), (b, c), (b, e), (d, f ).
d. Si el numero de centrales es n, es cierto que en este caso con n1 lneas alcanza para mantenerlas
conectadas?
4.4. El grafo de la figura representa el mapa de una ciudad. Se quiere ubicar policas en las esquinas de
modo que todas las cuadras esten bajo vigilancia, o sea, cada cuadra tiene que tener un polica al
menos en una de las esquinas. Cual es el mnimo numero de policas necesarios?
4.5. Supongamos que el siguiente programa quiere ser llevado a una maquina con n procesadores y
memoria compartida, o sea que todos los procesadores tienen acceso a los mismos espacios de
memoria (n suficientemente grande como para no imponer restriccion de paralelismo). Supongamos
tambien que el tiempo de ejecucion de cada instruccion es de 1 microsegundo. Se sabe que la unica
20
restriccion que tenemos para que una instruccion deba ejecutarse antes que otra es que la segunda
necesite algun resultado que se compute en la primera. Esto determina una relacion de precedencia
entre instrucciones. Luego, si dos instrucciones no dependen una de otra pueden ejecutarse al mismo
tiempo.
a. Representar la relacion de precedencia entre instrucciones utilizando un digrafo.

b. Haciendo una distribucion de las instrucciones por los procesadores, cual sera el tiempo mnimo
de ejecucion del programa?
A1
B3
C4
D A+B
E CB
F D/C
GEA
H F +G
c. Si se asignan los siguientes tiempos de ejecucion, como variara su respuesta?
asignacion 1ms
+ 2ms
3ms
4ms
/ 5ms
4.6. En un sistema operativo tenemos divididos a los procesos y a los recursos en dos conjuntos disjuntos,
el de los pi y el de los rj respectivamente. El sistema operativo asigna recursos a procesos solo a
pedido de los segundos. Cuando un proceso pi pide un recurso rj , queda en espera (sin ejecutar),
hasta que el s.o. satisface el pedido; esto lo indicamos con un eje orientado de pi a rj . Cuando el s.o.
asigna el recurso que requiere el proceso para ejecutar, el proceso deja de estar en espera y continua
con su ejecucion; en este caso se elimina el eje de pedido y se indica que el proceso esta utilizando
el recurso con un eje entre ambos pero con sentido contrario al de pedido. En algun momento o
bien el proceso no necesita mas el recurso y lo libera dejandolo disponible para que lo utilize otro
proceso o bien termina de ejecutar y libera todos los recursos que tiene asignados. Se entiende
que cuando un proceso pide un recurso no puede estar liberando otro, pues no esta ejecutando.
a. Modelar la siguiente situacion:
p1 esta utilizando el recurso r2

p2 pide el recurso r1
Se pueden satisfacer los pedidos? Tener en cuenta que los procesos que ejecutan eventualmente
liberaran los recursos que estan utilizando.
b. Analizar la siguiente situacion:

Se pueden satisfacer los pedidos?
c. Que tiene de particular el grafo resultante en b.?
4.7. Dados los dibujos de la figura
21
a. Es posible realizarlos sin levantar el lapiz del papel? (Sin repetir aristas, comenzando y termi-
nando en el mismo nodo)
b. Expresar el problema como un problema de grafos.
c. Se puede particionar el grafo en circuitos simples disjuntos en las aristas?
4.8. Supongamos que un viajante de comercio debe visitar clientes en siete ciudades A, B, C, D, E, F
y G. Existen las siguientes rutas con sus respectivas longitudes:
de A a B 6 Km de BaC 7 Km de D a E 2 Km
de A a C 4 Km de CaD 4 Km de C a F 3 Km
de C a G 2 Km de EaG 4 Km de F a G 1 Km
de A a F 6 Km de BaG 8 Km
Cual sera el recorrido mas corto para cubrir todas las ciudades y volver a la de partida? Este
problema se conoce como el problema del viajante de comercio.
4.9. Supongamos que se tienen cuatro aulas y las siguientes materias con sus respectivos horarios para
un mismo da:
Algebra 8 a 12 hs.
Analisis I 10 a 14 hs.
Analisis II 14 a 18 hs.
Logica 11 a 15 hs.
Algoritmos I 12 a 16 hs.
Algoritmos II 9 a 13 hs.
Laboratorio 1 14 a 18 hs.
Laboratorio 2 14 a 18 hs.
Existe una forma de asignar aulas de forma que se puedan dictar todas las materias respetando
los horarios?
22
Practica 5
5.1. Cual es el mayor numero de vertices que puede tener un grafo con 19 aristas y tal que sus vertices
tienen grado al menos 3?
5.2. a. Cuantos vertices tendra un grafo con 12 aristas y todos sus vertices de grado 2?
b. Cuantos vertices tendra un grafo con 15 aristas, 3 vertices de grado 4 y los otros vertices de
grado 3?
c. Cuantos vertices tendra un grafo con 20 aristas y todos sus vertices del mismo grado?
5.3. Probar que para un digrafo G cualquiera se verifica
X X
din (vi ) = dout (vj )
i j
5.4. Probar que en cualquier grupo de 2 o mas personas, hay al menos 2 que tienen la misma cantidad
de amigos dentro del grupo.
5.5. Es posible que haya un grupo de 7 personas tal que cada persona conozca exactamente otras 3
personas del grupo?
5.6. Probar que un grafo es conexo si y solo si para toda particion de V en dos subconjuntos V1 y V2
(V1 6= , V2 6= , V1 V2 = , V1 V2 = V ) hay un arco de G que une un punto de V1 con uno de V2 .
5.7. Probar que un grafo de n vertices que tiene mas de ((n 1)(n 2))/2 aristas es conexo.
5.8. a. Probar que la union de dos caminos simples distintos entre dos nodos p y q contiene un circuito
simple.
b. Que pasa si los caminos no son simples?
5.9. Probar que en un grafo conexo cualquier par de caminos simples de longitud maxima tienen un
vertice en comun.
5.10. Dado un digrafo G, un vertice v es alcanzable desde un vertice u si existe un camino orientado de u
a v. Un digrafo se dice fuertemente conexo si dados dos vertices cualesquiera u y v, u es alcanzable
desde v.
a. Probar que si un digrafo es fuertemente conexo el grafo subyacente es conexo, pero la recproca
es falsa.
b. Orientar un grafo es darle una direccion a cada eje. Probar que un grafo conexo G es orientable
de forma que se convierta en un digrafo fuertemente conexo si y solo si cada eje de G pertenece
a un circuito simple de G.
c. Que condicion debe cumplir el mapa de calles de una ciudad para que se puedan hacer todas
las calles de una sola mano?
5.11. a. Determinar un subgrafo completo de tamano maximo para los grafos del ejercicio 5.17.
b. Determinar todos los subgrafos completos maximales para los grafos del ejercicio 5.17. Son
maximos?
23
5.12. Si G tiene vertices v1 , v2 , . . . , vn , se define como la secuencia de grados de G a la secuencia
d(v1 ), d(v2 ), . . . , d(vn ). Probar que una secuencia de numeros enteros no negativos
P d1 , d2 , . . . , dn
es la secuencia de grados de un grafo (o multigrafo, o pseudografo) si y solo si i di es par.
5.13. La secuencia D = (d1 , d2 , . . . , dn ) se dice grafica si hay un grafo simple con secuencia de grados D.
a. Mostrar que (7, 6, 5, 4, 3, 3, 2) y (6, 6, 5, 4, 3, 3, 1) no son secuencias graficas.
b. Si D es una secuencia grafica tal que d1 d2 . . . dn entonces:
Pn
di es par y
Pi=1
k Pn
i=1 di k(k 1) + i=k+1 mn(k, di ) para 1 k n.
Nota: Se puede probar que esta condicion es tambien suficiente para que una secuencia sea
grafica.
5.14. Dado un grafo G = (V, X), se define el grafo complemento de G como G = (V, X) donde un eje
eXe / X. Si G tiene n vertices, tal que exactamente n 1 de los mismos tienen grado impar,
cuantos vertices de grado impar tendra G?
5.15. * Sea N (v) el conjunto de todos los vertices adyacentes a v y N [v] = N (v){v}. Sea Rn el conjunto
de todos los grafos G con n vertices, que tienen las propiedades siguientes: para cualesquier par de
vertices no contiguos u y v, o bien N (v) esta incluido en N (u), o bien N (u) esta incluido en N (v),
y para cualesquier par de vertices contiguos u y v, o bien N [v] esta incluido en N [u], o bien N [u]
esta incluido en N [v].
a. Demostrar que en un grafo G Rn los vertices de un mismo grado son todos adyacentes de par
en par, o bien no adyacentes de par en par.
b. Demostrar que en un grafo G Rn existe al menos un vertice de grado n 1 si no hay vertices
aislados.
5.16. a. Dibujar todos los grafos no isomorfos de 4 vertices.

b. Dibujar todos los digrafos no isomorfos de 3 vertices.
c. Dibujar todos los grafos no isomorfos de 5 vertices y 4 aristas.
d. Dibujar todos los digrafos no isomorfos de 5 vertices y 4 aristas.
5.17. Cuales de los pares de grafos de la figura son isomorfos? Justifique sus respuestas.
24
5.18. Cuales de los pares de digrafos de la figura son isomorfos? Justifique sus respuestas.
5.19. Sean dos grafos G y H isomorfos.

a. Mostrar que G y H tienen igual cantidad de vertices.
b. Mostrar que G y H tienen la misma cantidad de aristas.
c. Mostrar que para cada d 0 el numero de vertices de grado d es igual en los grafos G y H.
d. Mostrar que para cada l el numero de ciclos simples de longitud l en los grafos G y H son
iguales.
e. Mostrar que G y H tiene la misma cantidad de componentes conexas.
f. Mostrar un ejemplo de dos grafos no isomorfos que cumplan todas las condiciones anteriores.
g. Analizar conceptos similares para digrafos.
5.20. Un grafo se llama regular si todos sus vertices tienen el mismo grado.
a. Dibujar todos los grafos regulares no isomorfos de 4 vertices.
b. Dibujar todos los grafos regulares no isomorfos de 5 vertices.
5.21. Un grafo G se dice autocomplementario si G y G son isomorfos.
a. Hallar un grafo autocomplementario no trivial.
b. Mostrar que cualquier grafo autocomplementario debe tener 4k o 4k + 1 vertices, para algun
entero k.
5.22. Escribir un algoritmo que dados dos grafos G y H indique si son o no isomorfos. Que complejidad
tiene este algortimo? Es un buen algoritmo?
5.23. Dado un digrafo, se define su grafo subyacente como aquel que resulta de eliminar las direcciones
a los arcos del digrafo. Si entre dos vertices haba dos aristas de direccion opuesta, estos se funden
en uno solo no orientado. Dada la matriz de adyacencia de un digrafo, como se construye la matriz
de adyacencia de su grafo subyacente?
5.24. a. Caracterizar la matriz de adyacencia de un grafo bipartito.
b. Probar que un grafo es bipartito si y solo si para todo n impar los elementos de la diagonal de
An son nulos (A matriz de adyacencia del grafo).
5.25. Se define la matriz R de alcance de un digrafo G como:

1 si vj es alcanzable desde vi
rij =
0 si vj no es alcanzable desde vi
Como se puede calcular R a partir de la matriz de adyacencia?

5.26. a. Escribir un algoritmo que dado un grafo G indique si es o no un grafo bipartito. Idem para
digrafos.
b. Definir un procedimiento que dado un grafo G calcule G. Idem para digrafos.
c. Calcular las complejidades de los algoritmos de a. y b.
25
5.27. a. Escribir una funcion que dado un grafo G verifique si cada eje del G pertenece a un circuito
simple de G. Analizar distintas estructuras de datos.
b. Escribir un procedimiento que dado un grafo G, si puede lo oriente de forma que se convierte
en un digrafo fuertemente conexo. Analizar distintas estructuras de datos. Utilizar la funcion
definida en a.
c. Analizar las complejidades de los algoritmos de a. y b.
5.28. a. Escribir un algoritmo que dado un grafo G devuelva un subgrafo completo maximo del mismo.
b. Escribir un algoritmo que dado un grafo G liste todos sus subgrafos completos maximales.
c. Analizar las complejidades de los algoritmos de a. y b.
5.29. Dados los grafos y digrafos de la figura:
E
B
A D C
A D
C F
B E G F
B E
A D C
A D
C F
B E G F
a. Escribir las matrices de adyacencia e incidencia.

b. Representar mediante listas de aristas y listas de adyacencias.
c. Calcular los conjuntos de sucesores y de predecesores de los vertices de los digrafos de la figura
y de los digrafos del ejercicio 5.18.
d. Dadas las siguientes matrices de adyacencia representar el correspondiente grafo o multigrafo
(no orientado).

0 1 0 0 1
1 1 2 1
1 0 1 1 1
1 0 3 0
A = 0 1 0 0 0 A =
2 3 1 1
0 1 0 0 1
1 0 1 1
1 1 0 1 0
e. Calcular el grado de los vertices de los grafos de a. y d. usando las matrices de adyacencias
correspondientes.
f. Determinar todos los caminos simples de A a D y de E a B, a partir de la matriz de adyacencias
de los grafos de a.
g. Representar los digrafos cuyas matrices de adyacencia son

0 1 1 0

1 1 2 1

0 0 0 1 1 0 3 0
A = A=
1 1 0 0

2 3 1 1

0 0 1 0 1 0 1 1
26
Practica 6

6.1. a. Cual es el maximo numero de vertices que puede tener un grafo conexo de 20 aristas?
b. Probar que si G es un arbol con un numero par de ejes, entonces G tiene al menos un nodo de
grado par.
c. Supongamos que el promedio de los grados de los nodos de G es exactamente 2. Si G es conexo,
cuantos circuitos tiene G?
6.2. Es cierto que:
a. Si un grafo no tiene puentes entonces todo nodo tiene grado par?
b. Un grafo conexo con n ejes tiene exactamente un circuito?
c. Existe un grafo conexo con n + 1 ejes que tiene exactamente dos circuitos?
(tanto en b. como en c., n es la cantidad de nodos del grafo)
6.3. a. Probar que todo arbol no trivial es un grafo bipartito.
b. Hay arboles bipartitos completos?
6.4. Dibujar todos los arboles no isomorfos de 4 vertices, 5 vertices y 6 vertices.
6.5. Probar que todo arbol con dos o mas vertices tiene al menos 2 hojas.
6.6. Se dice que un grafo es un bosque si no tiene ciclos. Probar que G es un bosque si y solo si al sacar
cualquier eje de G aumenta el numero de componentes conexas.
6.7. Probar que el grafo complemento de un arbol es conexo o tiene un vertice aislado y el resto forma
un subgrafo completo.
PProbar que la secuencia grafica (d1 , d2 , . . . , dn ), di N, es la secuencia de un arbol si y solo si

6.8. *
i di = 2(n 1) y es conexo.
6.9. a. Puede haber un arbol binario con un numero par de vertices? Justificar.
b. Cual es el maximo numero de vertices que puede tener un arbol m-ario de altura h?
c. Probar que un arbol m-ario de altura h tiene a lo sumo mh hojas.
d. Probar que un arbol m-ario con l hojas tiene altura h dlogm le. Si el arbol es balanceado,
probar que h = dlogm le.
e. Se define el nivel de un vertice v en un arbol como su distancia a la raz, o sea, como la longitud
del unico camino de la raz al vertice. Mostrar que en un arbol binario con l hojas, la suma de
los niveles de las mismas es mayor igual a dl log2 le, y el nivel promedio es mayor o igual a
log2 l.
Nota: dxe = mn{z Z : z x}.
6.10. Dibujar todos los arboles generadores de los siguientes grafos:
27
6.11. a. Probar que si un grafo conexo tiene un unico arbol generador entonces es un arbol.
b. Es posible reconstruir un grafo si se conocen todos sus arboles generadores? Como?
c. * Dar un metodo para determinar el numero de arboles generadores de un grafo sin listarlos
explcitamente.
6.12. a. Usar BFS para numerar el grafo de la figura a partir del nodo marcado con 0.
b. Idem a. para DFS.

6.13. Escribir un algoritmo recursivo y otro iterativo que implementen BFS. Que tecnicas utilizan estos
algoritmos?
6.14. a. Probar que con DFS se alcanzan todos los vertices de un grafo conexo.
b. Idem a. para BFS.
6.15. a. Escribir un programa para contruir un arbol generador dado por DFS dada la matriz de adya-
cencia de un grafo.
b. Idem para BFS.
6.16. Probar que la altura de cualquier arbol generador determinado por DFS a partir de una raz dada
r, es mayor o igual que la altura de un arbol generador construdo por BFS a partir de la misma
raz r.
6.17. a. Como podra reescribirse alguno de los algoritmos anteriores para usarlo para determinar si un
grafo es o no conexo?
b. Enunciar un algoritmo para determinar el numero de componentes conexas de un grafo.
6.18. a. Determinar la complejidad del algoritmo de Prim.
b. Escribir un programa para el algoritmo de Prim.
c. Que tecnica utiliza este algoritmo?
6.19. Dado el algoritmo de Kruskal para determinar un arbol generador mnimo de un grafo conexo
G = (V, X) y una funcion l(e) : X R:
PASO 1: poner i = 1, T = {e}, con e de longitud mnima

PASO 2: mientras i < n 1 hacer:
PASO 3: elegir e tal que l(e) sea mnima entre los que no forman circuito
con los arcos que ya estan en T
PASO 4: poner T = T {e}
PASO 5: poner i = i + 1
a. Probar que el algoritmo de Kruskal construye un arbol generador mnimo.

b. Determinar la complejidad del algoritmo de Kruskal.
c. Escribir un programa para el algoritmo de Kruskal utilizando matrices de adyacencia y listas de
adyacencias como estructuras de datos.
d. Que tecnica utiliza este algoritmo?
28
6.20. Vialidad Nacional quiere construir, de la forma mas economica posible, caminos que vinculen 5
ciudades (aunque para ir de una a otra haya que pasar por una tercera). Los costos de los tramos
entre cada par de ciudades estan dados en la tabla. Decir que tramos deberan construirse.
B C D E
A 5 10 80 90
B 70 60 50
C 8 20
D 10
6.21. a. Enunciar un algoritmo que determine un arbol generador maximo de un grafo dado.
b. Aplicar el algoritmo al grafo de la figura.
3 2
4
3 3
2 2 6
5
6 6
4 1
7
6.22. Probar que si todos los arcos de un grafo G tienen distinta longitud entonces G tiene un unico
arbol generador mnimo.
6.23. Sea T un arbol generador mnimo de un grafo G determinado por el algoritmo de Kruskal.
a. Probar que T contiene todos los arcos de longitud mnima salvo que los mismos incluyan un
circuito.
b. Realizar la misma demostracion del punto anterior pero sin asumir que el arbol fue generado
por un algoritmo en particular.
29
Practica 7
7.1. a. Usar el algoritmo de Dijkstra para calcular el camino mas corto desde el vertice I a todos los
demas en el siguiente grafo:
II 3 III
4 2
I 7 2 1 IV
3 2
VI 3 V
b. Suponiendo que todos los arcos tuvieran la misma longitud repetir a. usando BFS.
c. Suponiendo que despues de resolver a. se descubriera que falta un arco en el grafo o que hay que
modificar alguna longitud, es necesario repetir el algoritmo completo o se pueden aprovechar
los resultados obtenidos?
7.2. a. Dar un ejemplo que muestre porque no se puede aplicar el algoritmo de Dijkstra cuando exis-
ten arcos de longitud negativa. Se puede construir un ejemplo en el cual Dijkstra funcione
correctamente a pesar de tener arcos de longitud negativa?
b. Cual es el trabajo computacional necesario para calcular los caminos de longitud mnima entre
todos los pares de vertices de un grafo usando Dijkstra?
c. Se puede considerar a Dijkstra como un algoritmo goloso?
7.3. Reescribir el algoritmo de Dijkstra para el caso en que los nodos del grafo esten organizado en un
heap de acuerdo a los valores de . Mostrar que en este caso el trabajo computacional que requiere
el algoritmo es O(m log2 n). En que casos conviene este tipo de estructuras?
7.4. a. Usar el metodo de Ford para determinar el camino mnimo entre el vertice I y los demas en el
siguiente grafo:
2 II 4
III
I
1 3
1 6 2 3
2
V
IV 3 1 VI
2 2
1
30
b. Calcular el camino mas corto entre todos los pares de vertices del grafo de la parte a. usando el
metodo de Floyd.
c. Idem b. usando el metodo de Dantzig. Comparar con b.
d. Idem 7.1c para Ford, Floyd y Dantzig.
7.5. a. Como se puede modificar el algoritmo de Ford para usarlo para detectar circuitos de longitud
negativa? Que pasa si no todos los vertices son alcanzables desde el vertice 1?
b. Mostrar que el algoritmo de Ford requiere en el peor caso O(mn) comparaciones.
7.6. a. Como influye en el algoritmo de Floyd la manera en que se hayan numerado los vertices del
grafo? Y en Dantzig?
b. Estimar el numero de operaciones necesarias para ejecutar el algoritmo de Floyd.
c. idem b. para Dantzig.
d. Como puede usarse el algoritmo de Floyd para detectar la existencia de circuitos de longitud
negativa? Y el de Dantzig?
e. Se pueden aplicar los algoritmos de Floyd y Dantzig a grafos no orientados?
7.7. Explicar porque el algoritmo de Floyd es un algoritmo que usa la tecnica de programacion dinamica.
7.8. a. Escribir un programa para el algoritmo de Dijkstra. Utilizar las estructuras vistas para repre-
sentar grafos (ademas de matriz de adyacencia) para implementarlo.
b. idem a. para Ford, Floyd y Dantzig.
7.9. * Si se quiere determinar el camino mas corto de el nodo s al nodo t, usando Dijkstra, se puede
parar cuando se ha rotulado en forma definitivia el nodo t. Veremos aqu una modificacion del
algoritmo que hace que hace que t sea rotulado mas rapidamente en la practica.
Sea h(i) 0 una cota inferior de la longitud del camino mas corto de un nodo i al nodo t, que
satisface h(i) h(j) + cij para
p todo eje (i, j). Por ejemplo si los nodos son puntos en el plano se
puede tomar h como h(i) = (xi xt )2 + (yi yt )2 , es decir la distancia euclideana entre i y t.
En este caso h(i) es una cota inferior a la longitud del camino mas corto entre i y t.
a. Sea cijh = cij + h(j) h(i) para todo (i, j). Mostrar que con estas nuevas longitudes los caminos
mnimos entre dos nodos no cambian.
b. Si aplicamos Dijkstra con cijh como longitudes de los arcos, por que esta modificacion (llamada
algoritmo A ) mejora el comportamiento emprico del algoritmo?
c. Que pasa si la funcion h no cumple la condicion de que h(i) h(j) + cij ? Puede usarse el
algoritmo A ?
7.10. Beba tiene un departamento de vacaciones en Punta del Este, que quiere alquilar en el perodo que
va del 1/12/95 al 31/3/96, por periodos cortos. Ha recibido numerosas ofertas, en las que figuran
el da que la persona ingresa al departamento (despues de las 15hs), el da que se va (antes de las
12hs) y el monto ofrecido del alquiler. Modelar el problema de elegir las ofertas que maximicen el
beneficio de Beba como un problema de camino mnimo.
7.11. La siguiente tabla muestra algunos posibles horarios de guardia para los choferes de una compana
de omnibus. Se quiere asegurar, al menor costo posible, que al menos un chofer este de guardia en
el perodo de 9 a 17hs. Modelar y resolver este problema como un problema de camino mnimo.
Horario 9-13 9-11 12-15 12-17 14-17 12-16 16-17
Costo 30 18 21 38 20 22 9
7.12. Modelar el problema de la mochila, para el caso donde se pueden llevar varios elementos iguales,
como un problema de camino mnimo.
7.13. * Una compana de construcciones necesita las siguientes cantidades de personal calificado para
una tarea especial en los meses de marzo a agosto:
Mes Marzo Abril Mayo Junio Julio Agosto
Personal 4 6 7 4 6 2
El personal debe ser contratado por mes. Si en febrero haba 3 personas y en setiembre deben
quedar 3 tambien, el problema que se quiere resolver es, determinar cuantos trabajadores deben
contratarse o despedirse en cada mes, de modo de minimizar el costo, sabiendo que:
31
Emplear un trabajador nuevo cuesta 100$ por trabajador y mandarlo a otra obra 160$.
No se pueden contratar mas de 3 trabajadores por mes, y no se pueden trasladar mas de un
tercio de los trabajadores de la obra al final de cada mes.
El costo de tener un obrero de mas es de 200$ por persona y el de tener uno menos tambien,
porque se deben pagar horas extra. No se pueden pagar mas del 25 % de horas extra, sobre el
horario regular.
Formular este problema como un problema de camino mnimo y resolverlo usando programacion
dinamica.
7.14. Volvamos al problema del practico 3 de dar el cambio con monedas. En su forma mas general
podemos decir que el problema del cambio de dinero consiste en determinar si es posible cambiar
un numero p dado en monedas de denominaciones conocidas a1 , . . . , ak . Por ejemplo, si k = 3, a1 =
3, a2 = 5, a3 = 7, podremos cambiar los numeros 8, 54, etc., pero no el numero 4.
Pk
En general, este problema consiste en responder si p = ai xi , para xi 0, i = 1, . . . , k.
i=1
Modelar el problema como un problema de camino mnimo.
a. Describir un metodo para identificar todos los numeros en un rango dado [l, u] que pueden ser
cambiados.
b. Describir un metodo para decidir si un numero p puede ser cambiado, y luego identificar las
denominaciones de las monedas, tal que sean la menor cantidad posibles.
7.15. Escribir los algoritmos para determinar el tiempo mnimo de ejecucion de un proyecto y para
determinar cuales son las actividades crticas, usando un grafo de actividades en los nodos.
7.16. Dada la red PERT de un proyecto se calcula por el metodo CPM:
ti = fecha temprana en la cual una etapa o evento i puede ser completado.
li = fecha tarda o ultima en la cual puede completarse una etapa i sin atrasar todo el proyecto.
a. Deducir a partir de ti y li formulas para calcular para cualquier actividad i j la fecha mas
temprana y tarda (tcij y lcij ) de comienzo de la misma y (tfij y lfij ) de terminacion.
b. Se define el margen libre de la actividad i j como tj ti dij , y el margen independiente
como tj li dij . Interpretar el significado de estos margenes.
7.17. Dada la siguiente red PERT de un proyecto, donde los numeros en los arcos indican el tiempo que
demanda la actividad representada por dicho arco:
II 7 V
5 8
7
3
I 1 VI
6
4 4
III 2 IV
a. Calcular para cada etapa i, ti y li , y para cada actividad i j, tcij , lcij , tfij y lfij , como fueron
definidos en el ejercicio anterior.
b. Encontrar el o los caminos crticos.
c. Calcular el margen total, libre e indenpendiente para cada actividad.
d. Suponiendo que se descubre que el tiempo dado para la actividad 3 5 debio ser 5, actualizar
los resultados de lo calculado en a., b. y c. sin repetir el algoritmo completo.
e. Cuanto puede crecer el tiempo de la actividad 3 5 sin alterar la fecha temprana de finalizacion
del proyecto?
32
7.18. Se quieren planificar las actividades necesarias para la fabricacion de una maquina grande que se
va fabricando por partes segun se describe en el siguiente cuadro:
nombre descripcion duracion predecesores

A buscar elementos para parte 1 5
B buscar elementos para parte 2 3
C buscar elementos para parte 3 10
D armar parte 1 7 A
E armar parte 2 10 B
F armar parte 4 5 D,E
G armar parte 3 9 B,C
H armado final 4 F,G
I inspeccion final y prueba 2 H
a. Armar el grafo PERT (actividades en los arcos) correspondiente a este problema.

b. Construir una tabla donde para cada actividades aparezcan los valores tcij , lcij , tfij y lfij y los
margenes total, libre e independiente. Indicar que actividades estan en el camino crtico. Cual
es el tiempo mnimo necesario para completar la fabricacion?
c. Construir el grafo de actividades en los nodos y repetir b. a partir del mismo.
7.19. Para obtener una licenciatura especializada en Investigacion Operativa, un estudiante tiene que
cursar las siguientes materias cuatrimestrales:
materia correlativas
Calculo I
Calculo II Calculo I
Estadstica I Calculo I
Estadstica II Estadstica I
Estadstica III Estadstica II, Calculo II
Programacion lineal
Programacion no lineal Calculo II, Prog. lineal
Programacion estocastica Calculo II, Prog. lineal, Estadstica III
Usar un grafo PERT para determinar el tiempo mnimo en que se puede terminar la carrera y
cuales son las materias en las cuales no es posible atrasarse.
33
Practica 8
8.1. a. Encontrar un circuito euleriano en el grafo de la figura.

b. Encontrar una particion en circuitos simples de las aristas del grafo de la figura.
8.2. Analizar nuevamente el ejercicio 4.7.

8.3. Determinar si los grafos de la figura tienen circuitos eulerianos. Sacar conclusiones.
8.4. Probar que un grafo G conexo tiene un circuito euleriano si y solo si el conjunto de aristas de G se
puede particionar en circuitos simples de modo que cada eje pertenezca a uno y solo uno de dichos
circuitos.
8.5. Llamemos w(G) al numero de componentes conexas de G. Mostrar que si G es conexo y todos sus
d(v)
vertices tienen grado par, entonces para cualquier vertice v se cumple que w(G v) .
2
8.6. Dar condiciones bajo las cuales un grafo tiene un camino euleriano pero no un circuito euleriano.
Demostrar.
8.7. Un grafo se dice arbitrariamente atravesable desde un vertice v0 si con el siguiente procedimiento
siempre se construye un circuito euleriano:
salir de v0 por cualquier eje incidente

mientras sea posible hacer:
al llegar a un vertice u, salir por un eje no utilizado
fin
34
a. Probar que un grafo que tiene un circuito euleriano es arbitrariamente atravesable desde un
vertice v0 si y solo si todo ciclo simple contiene a v0 .
b. Probar que si G es arbitrariamente atravesable desde v0 entonces v0 tiene grado maximo.
8.8. a. Para que valores de n, Kn tiene circuito euleriano?

b. Hay algun Kn que tenga camino euleriano pero no circuito?
8.9. a. Probar que un digrafo conexo tiene un circuito euleriano orientado si y solo si din (v) = dout (v)
para todo vertice v del digrafo.
b. Encontrar un circuito euleriano orientado en el digrafo de la figura.
c. Analizar el concepto de camino euleriano orientado para un digrafo.

8.10. Probar que todo digrafo conexo que tiene un circuito euleriano orientado es fuertemente conexo.
Es cierta la recproca?
8.11. Dada la demostracion del teorema de Euler:
a. Escribir una funcion que determine si todos los vertices son de grado par.
b. Escribir un programa que dado un grafo, verifique si cumple con las condiciones del teorema de
Euler (utilizar la funcion definida en a.) y genere un circuito.
c. Analizar estructuras de datos alternativas para implementar.
d. Calcular la complejidad de a. y b.
e. Mostrar que se puede realizar una implementacion de b. con complejidad O(m).
8.12. Decir por que el grafo de la figura no tiene camino ni circuito hamiltoniano.
8.13. El siguiente es el grafo original en el cual Hamilton baso su juego (ver [13]). Encontrar un circuito
hamiltoniano en el mismo. Una version del juego original consista en que uno de los jugadores
elega un camino con 5 vertices y el otro deba extender el camino a un circuito hamiltoniano. Hay
algun camino simple de 5 vertices que no pueda ser extendido a un circuito hamiltoniano?
35
8.14. Un digrafo G se dice completamente conexo si cada par de vertices esta conectado con exactamente
un eje orientado en una de las dos posibles direcciones. Probar que si un digrafo G es completamente
conexo entonces tiene un camino hamiltoniano orientado.
8.15. Probar que un grafo bipartito con un numero impar de vertices no contiene un circuito hamilto-
niano.
8.16. Si G es un grafo con n 4 y d (grado mnimo) n 2 entonces G tiene un circuito hamiltoniano.

8.17. Sea G un grafo y u y v dos nodos no adyacentes tal que d(u) + d(v) n. Probar que G es
hamiltoniano sii G+ el eje uv es hamiltoniano.
8.18. * Si 15 profesores cenaron juntos en una mesa circular durante una conferencia, y si cada noche cada
profesor se sento entre dos profesores distintos, cuantos das duro como maximo la conferencia?
8.19. Mostrar directamente sin utilizar ningun teorema ya demostrado en clase que cualquier grafo simple
de 6 vertices, todos de grado 3, tiene un circuito hamiltoniano.
Sugerencia: Pensar como es el complemento del grafo.
8.20. Analizar la siguiente modificacion al algoritmo DFS para determinar un circuito hamiltoniano en
un grafo:
Inicializar
Entrar un grafo G con vertices {1, 2, . . . , n}
poner path(1) 1, path(i) 0 para i = 2, . . . , n + 1
j2
f orward true
mientras j < n + 1 hacer
si f orward = true entonces
Build
sino
path(j) 0
j j1
si j 6= 1 entonces
Build
sino
devolver que no hay circuito hamiltoniano y parar
fin si
fin si
si j = n + 1 entonces
si (1, path(n)) X entonces
path(j) 1
sino
f orward false
j j1
fin si
fin si
fin mientras
devolver path y parar.
procedimiento Build
Encontrar el menor k > path(j) tal que k 6= path(i) para i < j y (path(j 1), k) X.
si no existe tal k entonces
f orward false
sino
path(j) k
j j+1
f orward true
36
fin si
a. Mostrar que el conjunto de aristas que brinda el algoritmo principal cuando devuelve path() es
un circuito hamiltoniano.
b. Mostrar que si el algoritmo no encuentra un circuito hamiltoniano entonces G no es hamiltoniano.
c. Determinar la complejidad de este algoritmo. Cual era la complejidad de DFS? Que tecnica
se ha usado en este modificacion de DFS? Comentar.
d. Encontrar una familia de grafos de n vertices tal que el algoritmo cree mas de (n 3)! caminos
ninguno de los cuales pueda extenderse a un circuito hamiltoniano.
8.21. Basandose en la demostracion del teorema que dice que dado un grafo G si para todo vertice v se
n
verifica que d(v) entonces el grafo tiene circuito hamiltoniano.
2
a. Escribir una funcion que dado un grafo G determine si en el se cumplen las hipotesis del teorema.
b. Escribir un programa que dado un grafo G, verifique si se cumplen las condiciones del teorema
y si es as, que genere un circuito hamiltoniano en G.
c. Analizar estructuras de datos alternativas para implementar.
d. Calcular la complejidad de los algoritmos de a. y b.
e. Decir en que punto falla el algoritmo cuando se lo aplica a un grafo que no cumple las hipotesis
del teorema. Dar ejemplos.
8.22. Dado un grafo G = (V, X) donde a cada eje e X se le ha asignado una longitud l(e). El problema
conocido como problema del viajante de comercio consiste en determinar el circuito hamiltoniano de
longitud total mnima. Suponiendo que G sea un grafo completo construir un algoritmo que genere
todos los posibles circuitos hamiltonianos de G y determine uno de longitud mnima. Analizar la
complejidad de dicho algoritmo.
8.23. Analizar el siguiente algoritmo para resolver el problema del viajante en forma aproximada:
PASO 1: Dar un grafo completo G con longitudes asignadas a las aristas.

PASO 2: Determinar un arbol generador mnimo T de G.
PASO 3: Construir un grafo orientado D(T ) reemplazando cada eje de T por dos aristas
orientadas en direcciones opuestas.
PASO 4: Usar el algoritmo de Euler modificado para grafos orientados para determinar
un circuito Euleriano en D(T ). Suponer que el circuito queda formado por las
aristas
{(x1 , y1 ), (x2 , y2 ), . . . , (x2n2 , y2n2 )}
PASO 5: Poner C {x1 } y marcar x1 .
PASO 6: Para i 1, 2n 3 hacer
PASO 7: Si yi no esta marcado, marcarlo y poner C C {yi }.
PASO 8: Poner C C {x1 }.
PASO 9: Informar C y parar.
a. Mostrar un ejemplo en que el resultado del algoritmo anterior no sea un circuito hamiltoniano
de longitud mnima.
b. Analizar la complejidad del algoritmo.
c. Probar que si l(C) es la longitud del circuito determinado por el algoritmo y l(H) es la longitud
de un circuito hamiltoniano de longitud mnima y ademas en el grafo se cumple que vale la
desigualdad triangular para las distancias, entonces l(C) 2 l(H). Comentar este resultado.
37
8.24. Analizar el siguiente algoritmo goloso (metodo del vecino mas cercano) para resolver el problema
del viajante de comercio en un grafo completo. Elegir v1 un vertice cualquiera.. Poner C1 = {v1 }.
Mientras Cj no contenga todos los vertices de V , elegir vj+1 como el vertice mas cercano a vj y
poner Cj+1 = Cj {vj+1 }. Agregar el eje entre vn y v1 .
a. Mostrar que este no es un algoritmo exacto para resolver el porblema del viajante de comercio.
Determinar su complejidad.
b. Es una buena heurstica?
c. Escribir un nuevo algoritmo para el mismo problema, que elija en primer lugar el nodo mas
lejano a v1 , y despues vaya eligiendo e insertando en cada paso el nodo que aun no esta en el
camino ya construido Cj y que esta mas cerca de algun nodo de Cj . Es este algoritmo exacto?
Es bueno? Es mejor que al anterior? Peor?
38
Practica 9
Referencias para este practico: [4], [22], [28], [17], [9], [5]
9.1. Decir cuales de los siguientes grafos son planares. Justificar.
9.2. Probar que si T es un arbol, T es planar.

9.3. a. Modificar la formula de Euler para que sirva para un grafo con k componentes conexas.
b. Mostrar que la formula m 3n 6 es valida tambien para grafos planares no conexos.
9.4. Probar que un grafo planar donde todo vertice tiene grado mayor o igual a 3, se verifica que
m 3r 6.
9.5. a. Probar que todo grafo planar tiene por lo menos un vertice de grado menor o igual a 5.
b. Probar que todo grafo planar con menos de 12 vertices tiene un vertice de grado a lo sumo 4.
c. Probar que si G tiene 11 o mas vertices, entonces G o su complemento son no planares.
9.6. Es cierto que todo grafo no planar es homeomorfo a K5 o K3,3 ?
9.7. Probar que si G es un grafo planar con circuitos, todos ellos de longitud mayor o igual a k, la
(n 2) k
desigualdad m 3n 6 puede ser mejorada a m .
k2
9.8. Supongamos que se dibujan l cuerdas de un crculo que se cortan en p puntos interiores (se supone
que en cada interseccion se cortan solamente 2 lneas). Cuantas regiones se forman de este modo
en el interior del crculo?.
9.9. * Un grafo se llama platonico si es conexo, planar, todos sus vertices tienen el mismo grado d1 y
todas sus regiones tienen el mismo numero d2 de aristas frontera (con d1 3 y d2 3). Probar
que si G es un grafo platonico:
d1 n d1
a. m = yr= n
2 d2
b. n (2d1 + 2d2 d1 d2 ) = 4d2
c. como n y 4d2 son enteros positivos, resulta que: 2d1 + 2d2 d1 d2 > 0. Usar esto para probar
que (d1 2)(d2 2) < 4.
d. Encontrar los 5 valores de d1 y d2 que verifican esta ultima desigualdad y dibujar los grafos
platonicos correspondientes.
9.10. a. Aplicar el algoritmo para decidir si un grafo es planar de Demoucron, Malgrange y Pertuiset, a
los grafos del ejercicio 9.1.
b. Escribir detalladamente el algoritmo de Demoucron, y mencionar las estructuras que usara para
implementarlo. Determinar su complejidad. Usar la relacion entre aristas y vertices que tiene
un grafo planar.
39
Practica 10
Referencias para este practico: [4], [22], [28], [17], [9], [5]
10.1. a) Calcular el numero cromatico de los siguientes grafos:
K6
C9
10.2. Se tiene una lista de tareas a desarrollar. Existen tareas que utilizan el mismo recurso, y cada tarea
demora una hora. Dado que los recursos son limitados (se dispone de una unidad por recurso), es
imposible que dos tareas que comparten algun recurso, se desarrollen al mismo tiempo. Determinar
cuantas horas son necesarias como mnimo para cumplir con todas las tareas. Modelar el problema
como un problema de coloreo.
10.3. Decidir si las afirmaciones siguientes son V o F. Justificar:
a) Si un grafo G contiene al grafo completo Ks como subgrafo inducido entonces (G) s.

b) Si todos los subgrafos completos de G tienen tamano menor o igual que s, entonces (G) s.
c) El problema de encontrar el numero cromatico de un grafo G es equivalente al problema de
encontrar el subgrafo completo maximo de G.
d ) Si (G) s entonces el grado de todo vertice de G es menor o igual que s 1.
40
10.4. Se va a realizar un congreso en el cual se dictaran varios cursos. Se tiene la lista de inscriptos y
en base a ella se quiere armar el cronograma de horarios de tal manera que todos los participantes
puedan asistir a los cursos que se anotaron, es decir, no se superpongan los horarios de cursos que
seran asistidos por una misma persona. Modelar este problema como un problema de coloreo.
10.5. Se quieren usar torres existentes para transmision de ondas para celular. El problema es que dos
torres que estan muy cerca pueden interferirse, si se utiliza la misma frecuencia para ambas. Cual es
el menor numero de frecuencias diferentes que hace falta usar en este caso? Modelar este problema
como un problema de coloreo y resolver para la instancia dada por la matriz de distancias entre
las torres y la distancia mnima para usar la misma frecuencia es 50 km..
B C D E F G H
A 170 140 28 189 25 186 67
B 100 46 70 26 2 214
C 0 56 110 34 16
D 18 30 90 13
E 134 48 53
F 14 55
G 50
10.6. Un grafo G es color crtico si sacando un vertice cualquiera disminuye el numero cromatico de G.
a) Para cada grafo del ejercicio 10.1, decidir si, al sacar cualquier vertice de los grafos , disminuye
el numero cromatico.
b) Probar que todo grafo k-cromatico (k 2) contiene un subgrafo k-cromatico color crtico.
10.7. Probar que si G es k-cromatico y color crtico entonces:
a) G es conexo.
b) Todo vertice de G tiene grado mayor o igual a k 1.
c) G no tiene un vertice tal que al sacarlo, G quede un grafo disconexo.
d ) G no contiene un conjunto de corte que sea un subgrafo completo de G.
10.8. El grafo junta de los grafos G y H, denotado H + G, se define agregando un eje entre cada vertice
de H y cada vertice de G. Probar que (G + H) = (G) + (H). Concluir que el grafo junta de
dos grafos color crticos es color crtico.
10.9. Probar que para cualquier conjunto independiente S de un grafo color crtico G se cumple que
(G S) = (G) 1.
10.10. Sea G un grafo
a) Probar que G es bipartito si y solo si (G) = 2 (suponiendo que tiene al menos una arista).
b) Enunciar un algoritmo para determinar si un grafo es 2-coloreable.
c) Determinar la complejidad del algoritmo dado en b).
10.11. Sea G un grafo de n vertices, Cmax (G) el tamano del subgrafo completo maximo y Imax el tamano
del conjunto independiente maximo. Probar que Cmax (G) + Imax (G) + (G).
10.12. Probar que si G es un grafo de n vertices y G es su complemento, entonces:
a) (G) + (G) n + 1
2
n+1
b) * n (G) (G)
2

c) * (G) + (G) 2 n
10.13. Sea G un grafo regular de n vertices. Probar que si (G) + (G) = n + 1 entonces G es uno de los
siguientes grafos:
a) el grafo formado por n vertices aislados
41
b) Kn
c) un circuito simple de longitud impar.
10.14. Analizar el siguiente algoritmo secuencial para colorear un grafo:
1. Dado un grafo G = (V, X) con V = {v1 , v2 , . . . , vn }, poner f (v1 ) = 1.
2. Para i = 2, n poner f (vi ) = mn{k/k 1 y f (vj ) 6= k para (1 j < i) y vj adyacente a vi }
3. Parar.
a) Determinar la complejidad del algoritmo de a.

b) Decidir si este algoritmo siempre calcula el numero cromatico de un grafo. De que depende
que esto suceda ?
c) Dar ejemplos donde el algoritmo no encuentre numero cromatico, si existe.
d ) Demostrar que para todo grafo G existe un orden de rotulado de los vertices para el cual el
algortimo de a. determina el numero cromatico de G.
e) Deducir que si se corre el algoritmo de a. para todas las posibles permutaciones de los rotulos
de G se obtiene un algoritmo exacto para determinar el numero cromatico de un grafo G.
Cual es la complejidad de este algoritmo?.
10.15. *
a) Probar que si v1 , . . . vn es un ordenamiento de los vertices de V , (G) max{mn{di + 1, i}}.
i
b) Hay algun caso en que valga la igualdad en la formula de a.?
c) Probar que U S = max mn{i, d(vi ) + 1} es una cota superior del numero de colores usado por
el algoritmo secuencial con ese ordenamiento. Es esta una buena cota? Hay algun caso en
que la heurstica use realmente este numero de colores?
d ) Supongamos que en el algoritmo secuencial se ordenan previamente los vertices de V de modo
que quede d(v1 ) d(v2 ) . . . d(vn ). Llamamos a este algoritmo, algoritmo secuencial
largest first SLF y llamamos ULF a la cota superior del numero de colores usados por el
algoritmo en este caso. Mostrar que se verifica que ULF US.
e) Se puede concluir de b. que el algoritmo SLF es siempre mejor que el algoritmo secuencial
con otros ordenamientos de los vertices? Se puede obtener una buena cota para la diferencia
entre el numero de colores usado por ULF y el numero cromatico del grafo?
10.16. a) Escribir un algoritmo exacto para determinar el numero cromatico usando la tecnica de back-
tracking
b) Probar que el algoritmo dado en a. es correcto y determinar la complejidad.
10.17. Hallar el numero cromatico de G. De cuantas formas distintas se puede colorear G si se disponen
de 19 colores?
v2
v1 v3
v6 v5 v4 v7
10.18. El polinomio cromatico PG (k) de un grafo rotulado G es un polinomio en k, tal que para cada k,
PG (k) es la cantidad de maneras distintas de colorear el grafo con k colores.
a) Calcular el polinomio cromatico de cada uno de los siguientes grafos:
42
Kn
b) Como se puede determinar el numero cromatico de un grafo a partir de su polinomio cromati-

co?
c) Dar una cota inferior para el grado del polinomio cromatico de un grafo.
10.19. a) Escribir un algoritmo para calcular el polinomio cromatico usando un arbol donde los hijos
de un nodo se construyen poniendo un eje entre dos nodos no adyacentes (si usan distinto
color) o pegandolos (si usan el mismo color ).
b) Explicar por que la funcion PG (k) es efectivamente un polinomio en k.
c) Determinar la complejidad del algoritmo de a.
10.20. Hallar el polinomio cromatico de:
a) Los ciclos de n nodos
b) Los grafos Gn , donde Gn es un grafo compuesto de n ciclos de 4 vertices dispuestos en fila
unidos por un vertice.
Gn
10.21. Calcular el ndice cromatico de los siguientes grafos:
43
10.22. (Teorema de Vizing) Sea (G) el grado maximo de G. Dar ejemplos de grafos, donde el ndice
cromatico sea igual a 0 (G) = (G) y grafos donde 0 (G) = (G) + 1.
10.23. Supongamos que 11 equipos deben jugar entre si. Suponiendo que un equipo no puede jugar mas
de un partido por da, cuantos das son necesarios? Modelar este problema cono un problema de
coloreo de aristas y como un problema de coloreo de vertices.
10.24. Dado un grafo G, se define el grafo linea L(G) como el grafo que tiene un vertice por cada arista
de G, y dos vertices de L(G) son adyacentes si y solo si, las aristas correspondientes a esos vertices
se intersecan en G. Probar que 0 (G) = (L(G)).
10.25. Sea m(G) el tamano maximo de un matching en G.
a) Demostrar que 0 (G) m(G) | E(G) |.

b) Usando el ejercicio anterior, hallar una cota inferior para el numero cromatico de un grafo
linea L(G).
44
Practica 11
11.1. Para cada grafo de la figura, encontrar:

a. las correspondencias maximales y cuales de ellas son maximas.
b. los recubrimientos minimales de los vertices y cuales son mnimos.
c. los conjuntos independientes maximales y cuales son maximos.
d. los recubrimientos minimales de las aristas y cuales son mnimos.
11.2. Decidir si es verdadera o falsa cada una de las siguientes afirmaciones. Si es verdadera probarla y
si es falso encontrar un contraejemplo.
a. Todo grafo tiene al menos una correspondencia (matching).
b. Todo grafo tiene al menos un recubrimiento de los vertices.
c. Todo grafo tiene al menos un conjunto independiente.
d. Todo grafo tiene al menos un recubrimiento de las aristas.
e. En todo grafo, cualquier recubrimiento de vertices tiene un numero de aristas mayor o igual que
el de cualquier correspondencia.
f. En todo grafo, cualquier recubrimiento de aristas tiene una cantidad mayor o igual de vertices
que cualquier conjunto independiente.
g. Cualquier recubrimiento de vertices contiene una correspondencia maxima.
11.3. Probar que:
a. Un grafo tiene un recubrimiento de los vertices si y solo si no tiene vertices aislados.
b. Si G tiene n (n > 1) vertices, cualquier recubrimiento de los vertices de G tiene al menos dn/2e
aristas.
c. Todo recubrimiento contiene un recubrimiento minimal.
d. Un recubrimiento minimal no contiene circuitos.
e. Cual es el maximo numero de aristas que puede tener un recubrimiento minimal de los vertices?
f. Un recubrimiento de los vertices de un grafo es minimal si y solo si no contiene caminos ni
circuitos simples de longitud mayor o igual a 3.
11.4. Probar que si G es un grafo sin vertices aislados, se verifica que donde es el cardinal del
conjunto independiente maximo y es el cardinal del recubrimiento de vertices mnimo.
45
11.5. Probar que en un grafo bipartito G, m , donde m es la cantidad de aristas, es el cardinal
del conjunto independiente maximo de G y es el cardinal del recubrimiento mnimo de aristas de
G.
11.6. Revisar los ejercicios de modelizacion del practico 4. Cuales se pueden modelizar como problemas
de matching, recubrimiento o de conjunto independiente? Como se los puede resolver?
11.7. Analizar el siguiente algoritmo para determinar un conjunto independiente en un grafo G:
PASO 1: Poner I
PASO 2: Mientras V 6= hacer
PASO 3: Encontrar un vertice x tal que d(x, G) sea mnimo.
PASO 4: Poner I I {x}
PASO 5: Poner V V \({x} {y : y adyacente a x}).
PASO 6: Poner G (V, X(V )).
PASO 7: Informar I
a. Probar que el algoritmo anterior encuentra un conjunto independiente en G.

b. Determinar la complejidad del mismo. Que tecnica utiliza?
c. Mostrar que el algoritmo no necesariamente encuentra un conjunto independiente maximo.
d. Dado que no se conocen algoritmos de complejidad polinomial para el problema de determinar
un conjunto independiente maximo en un grafo, se podra usar este algoritmo como algoritmo
aproximado para resolver el problema? Sera un buen algoritmo aproximado?
11.8. Analizar el siguiente algorimo para colorear un grafo:

PASO 1: U V , k 0
PASO 2: Mientras U 6= hacer
PASO 3: Poner k k + 1
PASO 4: determinar un conjunto independiente maximo W en el subgrafo
de G generado por U .
PASO 5: Asignar a los nodos de W el color k.
PASO 6: Poner U U \W .
PASO 7: Informar k, que es el numero de colores con que se ha coloreado el
grafo.
a. Probar que el algoritmo produce un coloreo valido del grafo. Calcula el numero cromatico de
G?
b. Cual es la complejidad del algoritmo?
c. Si el problema de encontrar un conjunto independiente maximo pudiera ser resuelto en forma
polinomial, esto implicara, a partir del algoritmo anterior que lo mismo ocurrira para el
problema de coloreo de grafos?
d. Probar que reemplazando el PASO 4, por el algoritmo del ejercicio 11.7, se obtiene una heurstica
para el problema de determinar el numero cromatico de un grafo, de complejidad polinomial.
Es una buena heurstica?
11.9. Dado un grafo bipartito G = (V, X) con V = V1 V2 , o sea todos las aristas del grafo sean la forma
(v, w), con v V1 y w V2 , se dice que hay una correspondencia completa C de los vertices de V1
en los vertices de V2 si existe una correspondencia C tal que todo vertice de V1 es incidente a un
arco de C.
a. Dar ejemplos de grafos bipartitos que tengan y no tengan una correspondencia completa de V1
en V2 .
46
b. Probar que G tiene una correspondencia completa de V1 en V2 si y solo si todo subconjunto de
r vertices de V1 es adyacente a r o mas vertices de V2 , para todo r positivo.
11.10. Dada la red de la figura donde en cada arco figura la capacidad y el valor de un flujo dado:
a 1, 3 b
2, 2 2, 3
s 1, 1 1, 2 t
1, 2 1, 3
c
a. Determinar todos los posibles caminos de aumento.

b. Construir a partir del flujo dado, el flujo maximo de s a t.
c. Encontrar un corte mnimo que separe a s de t. Que ocurre con el valor del flujo calculado en
b. en los arcos del corte mnimo?
11.11. Encontrar el flujo maximo que puede ir de s a t en la siguiente red:
a 6 b
3 2 7 2
2 c d 4
s t
5 7
9 6
e 1 f
11.12. a. Construir una red de 4 nodos en la que el metodo de Ford y Fulkerson necesita F iteraciones
para obtener el flujo de valor maximo (partiendo de un flujo inicial con valor 0).
b. Cuantas comparaciones se necesitan dado el numero de aristas de una red para cada iteracion
del metodo de Ford y Fulkerson?
11.13. * Mostrar que el algoritmo de Edmonds y Karp (modificacion del algoritmo original de Ford y
Fulkerson) tiene complejidad O(nm2 ).
11.14. Decir si son correctas o no las siguientes afirmaciones. Justificar.
a. Si todos los arcos de una red tienen distintas capacidades existe un unico corte de capacidad
mnima.
b. Si todos los arcos en una red tienen distintas capacidades existe un unico conjunto de arcos por
el cual puede pasar un flujo de valor maximo.
11.15. Como se puede hacer para encontrar el flujo mnimo en una red con fuente s y sumidero t, donde
existen cotas inferiores para el flujo que debe pasar por cada arcos?
11.16. Como se puede modificar el metodo de Ford y Fulkerson, cuando se usan redes no orientadas para
evitar que se pueda tener simultaneamente f (vi vj ) > 0 y f (vj vi ) > 0?
11.17. Un agente de viaje debe arreglar el viaje de 10 turistas de Buenos Aires a Viena en una fecha dada
sabiendo que hay 7 lugares libre de Buenos Aires a Ro, 4 de Ro a Pars, 8 de pars a Viena, 2 de
Buenos Aires a Viena, 5 de Buenos Aires a Madrid, 3 de Madrid a Pars y 2 de Madrid a Viena.
Puede organizar el viaje? Como?
11.18. Supongamos que hay 5 comisiones formadas, de las cuales cada una desea enviar un representante
distinto a una reunion. Los miembros de A son a, b y c, los miembros de B son b y c, los miembros
de C son a, b y d, los de D son d, e, f y los de E son e y f . Transformar el problema en un problema
de flujo maximo y resolverlo.
47
11.19. En la siguiente red x1 , x2 , x3 son las fuentes de algun elemento. Se dispone de 5 unidades en x1 ,
10 en x2 y 5 en x3 . Se requieren 5 unidades en y1 , 10 en y2 , y 5 en y3 y se desea saber si se pueden
enviar a traves de la red. (sugerencia: agregar una fuente s y un sumidero t artificiales a la red).
3 a 6
x1 y1
3 2 5 1
7 2
4 b 8 c 2
x2 y2
9 7
3 1 6 4
x3 y3
7 d 8
11.20. En la siguiente red ademas de las capacidades de los arcos, los vertices distintos de s y t tienen una
cota superior de flujo que pueden pasar a traves de ellos. Encontrar el flujo maximo en este caso.
(Sugerencia: reemplazar cada vertice por dos vertices nuevos).
a[5] 6 b[4]
3 2 7 2
c[4] d[5] 3
2 4
s t
3
9 7 5 6
e[5] 1 f [4]
11.21. a. Sea G un grafo conexo no orientado. Mostrar que existen k caminos que no tienen aristas en
comun entre a y b si y solo si cualquier corte que separe a de b tiene al menos k arcos.
b. Sea G un grafo conexo no orientado. Mostrar que existen k caminos sin vertices en comun si y
solo si cualquier conjunto de vertices que desconecta a de b tiene al menos k vertices.
11.22. a. Como se puede calcular el numero de caminos disjuntos en las aristas que se pueden trazar
entre a y b, para a y b vertices dados?
b. idem a. para camino sin vertices en comun.
11.23. La red no orientada que se presenta a continuacion representa la red de cables troncales de un
sistema telefonico. La capacidad de un eje es el numero maximo de llamadas que una lnea puede
soportar. Se quiere determinar cual es el numero maximo de llamadas que se pueden hacer a traves
de la red de la localidad A a la localidad Z.
10
30 10 10 10
5
5
A 20 30 Z
10
20 20 5 20
30
11.24. a. Se quieren mandar mensajeros de A a Z en el grafo que se muestra a continuacion. Como ciertos
tramos de camino pueden estar bloqueados se requiere que cada mensajero use distintas aristas,
es decir que los caminos que sigan pueden tener vertices pero no aristas en comun.
48
A Z
b. Que pasa si hasta tres mensajeros pueden usar cada eje?

11.25. Supongamos que aparte de las capacidades a los arcos de una red se les haga corresponder el costo
cij correspondiente a que una unidad circule por ese arco. Se desea calcular en este caso cual es el
mnimo costo al cual se puede mandar un flujo de valor F , desde s hasta t. Para esto se propone
el siguiente algoritmo:
Poner flujo inicial f (e) 0 para todo arco e y el contador de flujo H 0

Mientras H 6= F hacer:
Definir longitudes cij de los arcos de la red del siguiente modo:
Si e = i j ponemos
cij cij si 0 f (e) < c(e)
cij si f (e) = c(e)
cji cij si 0 < f (e)
donde cji se entiende como la longitud del eje j i
Encontrar el camino mas corto de s a t usando los valores de cij
Aumentar el flujo en ese camino usando el valor
M mn( mn {c(e) f (e)}, mn {f (e)}, F H)
e hacia e hacia
Poner H H + M
Fin
a. Convencerse de que el algoritmo funciona y usarlo para calcular el costo mnimo con el cual se
pueden enviar 18 unidades de s a t, en la siguiente red, donde en cada arco esta marcado la
capacidad y el costo por unidad:
15, 4 14, 1
s t
11, 2 13, 6
16, 1 8, 2
17, 3
b. Como se puede usar el algoritmo anterior para determinar cual es el flujo maximo que se puede
enviar si se dispone de una cierta cantidad fija de dinero? En la red de a. calcular cual es el flujo
maximo que se puede mandar a un costo de 100.
11.26. * Hay problemas en los cuales se requiere que una cantidad mnima de flujo pase por cada arco, es
decir se pide que:
(*) b(e) f (e) c(e) para todo e X con b(e) no negativo.
a. Suponiendo que se dispone de un flujo inicial que verifica (*), modificar el algoritmo de Ford y
Fulkerson para este caso.
b. Encontrar el flujo maximo en la siguiente red donde se indican cotas inferiores y superiores del
flujo que debe pasar por cada arco. (Determinar a ojo un flujo inicial).
49
1, 7 3, 10
2, 5 2, 10 1, 6
2, 6 1, 7 2, 9 2, 6
s 1, 8 1, 9
t
2, 6
3, 7 2, 6 0, 8
c. Probar que si S, S es un corte de P

G que separa
P a s de t entonces
P si f es un
Pflujo compatible con
(*) y F su valor se verifica que: b(e) c(e) F c(e) b(e)
eSS eSS eSS eSS
d. ProbarPque si existe
P un flujo compatible con (*) entonces para todo corte S de G, se verifica
que: c(e) b(e) 0
eSS eSS
(esta condicion es tambien suficiente para que exista un flujo compatible pero la demostracion
es un poco mas complicada)
e. Mostrar que si a partir de G se construye un nuevo grafo G0 donde se agrega una fuente s0 y
un sumidero t0 , y a todo arco e: i j en X se le asigna una cantidad c0ij = c(e) b(e) y se le
hace corresponder dos arcos, uno s0 j con capacidad c0s0 j = b(e) y otro i t0 con capacidad
c0i0 t = b(e), ademas agregando aristas s t y t s donde c0st = c0ts = , entonces el problema
de buscar un flujo compatible con (*) en G se puede reducir a buscar un flujo maximo de s0 a
t0 en G0
f. Aplicar el metodo de e. a encontrar un flujo compatible en la siguiente red. Calcular despues el
flujo maximo.
11.27. Para poder brindar un servicio medico apropiado a un costo razonable los administradores de un
hospital deben buscar constantemente la forma de tener la mnima cantidad de personal compatible
con la necesidad de proveer niveles de atencion satisfactorios. Un hospital urbano tiene tres salas
que atender, la de emergencias, la de cuidados intesivos neonatales y la de ortopedia. El hospital
tiene tres turnos de trabajo, cada uno con diferentes necesidades en cuanto a cantidad de enfermeras
necesarias. El hospital necesita identificar el mnimo numero de enfermeras requerido para cumplir
las siguientes condiciones:
a. El hospital debe asignar al menos 13, 32 y 22 enfermeras en cada departamento entre todos los
turnos.
b. El hospital debe asignar al menos 26, 24 y 18 enfermeras en cada uno de los tres turnos.
c. El mnimo y maximo numero de enfermeras asiganadas a cada departamento en cada turno
esta dado por la siguiente tabla:
Departamento
Turno 1 2 3
1 6, 8 11, 12 7, 12
2 11, 12 11, 12 7, 12
3 2, 4 10, 12 5, 7
Modelar el problema como un problema de flujo maximo y resolverlo.

11.28. Un comerciante tiene el siguiente problema. En cada uno de T perodos puede vender, comprar o
conservar en deposito para futuras ventas, un producto dado, sujeto a las siguientes restricciones.
En cada perodo i puede comprar a lo sumo i unidades, almacenar i unidades y debe vender
debido a compromisos anteriores i unidades. No puede vender el producto en el mismo perodo en
el que lo compra. Asumiendo que pi , wi y si son respectivamente el costo del producto, el costo
de almacenamiento del producto y el precio de venta del mismo, que poltica de compra y venta
debe adoptar el comerciente para maximizar su beneficio? Plantear el problema como un problema
de flujo de costo mnimo para T = 4.
50
Practica 12
12.1. Mostrar que los siguientes problemas pertenecen a P:

a. Ordenar una lista de n numeros.
b. Chequear si un grafo es conexo.
c. Chequear si un grafo tiene un ciclo.
12.2. Mostrar que la relacion p es transitiva (P1 p P2 y P2 p P3 P1 p P3 ).
12.3. Considerar el conjunto de todos los grafos que contienen a K4 como subgrafo inducido. Pertenece
a P el problema de determinar si un grafo es de esta clase? Pertenece a NP?
12.4. Describir una Maquina de Turing no determinstica que funcione en tiempo lineal para el problema
34 del Practico 2 (sugerencia: adivinar la longitud de la mitad de la cadena).
12.5. Disenar algoritmos no determinsticos polinomiales para los problemas que aparecen a continuacion.
Describir los algoritmos utilizando pseudocodigo ampliado con la instruccion Guess(). Calcular la
complejidad de los algoritmos propuestos.
a. Determinar si un grafo es conexo.
b. Determinar si dos grafos son isomorfos.
c. Determinar si un grafo tiene un circuito hamiltoniano.
12.6. Demostrar que si un problema NP, entonces puede ser resuelto en tiempo determinstico
O(2p(n) ).
12.7. Decir si las siguientes afirmaciones son verdaderas, falsas o no se sabe:
a. P NP
b. P co-NP
c. P = NP co-NP
d. P = NP co-NP = NP
e. co-NP = NP SAT co-NP
f. co-NP NP NP = co-NP
g. co-NP NP P = NP
12.8. Es cierto que si dos problemas X e Y son NP-completos entonces X p Y , y tambien Y p X?
Justificar.
12.9. Sean X e Y dos problemas de decision tales que X p Y . Que se puede inferir?
a. Si X esta en P entonces Y esta en P.
b. Si Y esta en P entonces X esta en P.
c. Si Y es NP-completo entonces X tambien.
d. Si X es NP-completo entonces Y tambien.
51
e. Si Y es NP-completo y X esta en NP entonces X es NP-completo.
f. Si X es NP-completo e Y esta en NP entonces Y es NP-completo.
g. X e Y no pueden ser ambos NP-completos.
12.10. Decir si las siguientes afirmaciones son verdaderas o falsas:
a. Si P = NP entonces todo problema NP-completo es polinomial.
b. Si P = NP entonces todo problema NP-hard es polinomial.
c. Las clases NP-completo y co-NP-completo son disjuntas si y solamente si P 6= NP (un problema
de decision es co-NP-completo cuando pertenece a co-NP y todo otro problema perteneciente a
co-NP es polinomialmente reducible a el).
12.11. Que se puede inferir del hecho de que el problema del viajante de comercio (TSP) es NP-completo,
suponiendo P 6= NP?:
a. No existe un algoritmo que resuelva instancias arbitrarias de TSP.
b. No existe un algoritmo que eficientemente resuelva instancias arbitrarias de TSP.
c. Existe un algoritmo que eficientemente resuelve instancias arbitrarias de TSP, pero nadie lo ha
encontrado.
d. TSP no esta en P.
e. Todos los algoritmos que resuelven TSP corren un tiempo polinomial para algunas entradas.
f. Todos los algoritmos que resuelven TSP corren un tiempo exponencial para todas las entradas.
12.12. Considere el problema de isomorfismo en grafos (es el grafo G isomorfo al grafo H?). Que puede
decir de este problema? Esto implica P 6= NP?
12.13. Que se puede inferir del hecho de que Isomorfismo esta en NP pero no se sabe si es NP-completo,
suponiendo P 6= NP?:
a. Existe un algoritmo que resuelve instancias arbitrarias de Isomorfismo.
b. Existe un algoritmo que resuelve eficientemente instancias arbitrarias de Isomorfismo.
c. Si encontramos un algoritmo polinomial que resuelva Isomorfismo, podemos usarlo como una
caja negra para resolver TSP.
12.14. a. Sea un grafo G = (V, X) y W V . Demostrar la equivalencia de las siguientes afirmaciones:
V W es un recubrimiento de arcos de G.
W es un conjunto independiente de G.
W es un clique de Gc (el grafo complemento de G).
b. A partir del punto anterior, encontrar reducciones polinomiales entre los problemas Mnimo
Recubrimiento de Arcos, Maximo Conjunto Independiente y Maximo Clique.
c. A que clase de complejidad pertenecen estos 3 problemas? Por que?
12.15. Construir una reduccion polinomial de Clique a SAT (sugerencia: considerar variables booleanas
representando la matriz de adyacencia de un grafo, junto con k n variables vij , donde n es la
cantidad de vertices del grafo y k es el tamano del clique. vij sera True sii el i-esimo elemento del
clique es el j-esimo vertice del grafo).
12.16. Encontrar una reduccion polinomial del problema Circuito Hamiltoniano al problema del viajante
de comercio (TSP) (sugerencia: construir un grafo completo con pesos en los arcos tales que el
menor circuito hamiltoniano corresponda a un circuito hamiltoniano del grafo original). Sabiendo
que el primer problema es NP-completo, que se puede decir del segundo?
12.17. Cual de los siguientes dos problemas esta en P y cual es NP-completo? Justificar.
a. Entrada: Un grafo conexo con n nodos, dos nodos u y v de G, y un entero k. Pregunta: Existe
un camino simple de u a v de longitud k?
b. Entrada: Un grafo conexo con n nodos, y dos nodos u y v de G. Pregunta: Existe un camino
simple de u a v de longitud 8?
52
12.18. Utilizando la NP-completitud de otro problema, demostrar que el problema Camino mnimo con-
dicionado es NP-completo:
Entrada: un grafo G = (V, X) con un peso positivo asociado a cada eje, un par de vertices s, t V ,
un subconjunto de nodos V 0 V y un entero k > 0.
Pregunta: Existe un camino entre s y t en G que pasa por todos los vertices de V 0 y de peso total
menor o igual que k?
12.19. Mostrar que el problema de decidir si una formula booleana tiene al menos dos diferentes asigna-
ciones de variables que la hacen verdadera, es
NP-completo.
12.20. Se podra utilizar una maquina con alto paralelismo para resolver un problema NP-completo en
tiempo polinomial, suponiendo P 6= NP?
12.21. Discutir algunas de las alternativas posibles cuando se debe resolver en la practica un problema
que se sabe que es NP-completo.
12.22. Cual sera la importancia de que alguien...
a. encuentre un algoritmo polinomial que resuelve un problema NP-completo?
b. pruebe que un problema en NP es intratable?
12.23. a. Cual es la diferencia entre un algoritmo polinomial y uno pseudo-polinomial?
b. Dar un ejemplo de un algoritmo pseudo-polinomial. Indicar en que circunstancias este algoritmo
presenta dificultades.
53

Prac 2012

Cargado por

Copyright:

Formatos disponibles

Prac 2012

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Prac 2012

Cargado por

Copyright:

Formatos disponibles

Algoritmos y Estructuras de Datos III

Segundo Cuatrimestre de 2012

DEPTO. DE COMPUTACION - FCEyN - UBA

RESPETELAS Y HAGALAS RESPETAR

a) A los accidentados se les proveeran los primeros auxilios.

BOMBEROS: Telefono 100

Control de los riesgos electricos

Instrucciones generales para los trabajos

Que hay que entregar

Referencias para este practico: [9], [8], [27]

1.1. Probar por induccion:

1.6. Cual es el error en la siguiente demostracion?

Referencias para este practico: [2], [8], [26], [9]

b. Dado un vector v, su dimension d y un elemento e:

c. Dado un numero natural n:

d. Escribir el algoritmo clasico para pasar de la representacion decimal a binaria de un numero

a. Ordenar la secuencia de 2.13a usando Meansort.

a. Ordenar la secuencia de 2.13a usando B-sort.

Referencias para este practico: [2], [8], [26], [9]

Determinar la complejidad de ambas. Cual resulta mejor?

a. Escribir un algoritmo recursivo para resolver este problema.

donde la constante c depende de la densidad de grabado y la velocidad del dispositivo. Queremos

i. en orden no decreciente de los si

Elegir en cada paso la moneda de mayor valor entre las disponibles.

3.13. Dar ejemplos de problemas donde no valga el principio de optimalidad.

Referencias para este practico: [4], [14]

a. Representar la relacion de precedencia entre instrucciones utilizando un digrafo.

a. Modelar la siguiente situacion:

p1 esta utilizando el recurso r2

p1 esta utilizando el recurso r2

4.7. Dados los dibujos de la figura

Referencias para este practico: [4], [5], [12]

5.16. a. Dibujar todos los grafos no isomorfos de 4 vertices.

5.19. Sean dos grafos G y H isomorfos.

Como se puede calcular R a partir de la matriz de adyacencia?

a. Escribir las matrices de adyacencia e incidencia.

Referencias para este practico: [4], [5], [32]

PProbar que la secuencia grafica (d1 , d2 , . . . , dn ), di N, es la secuencia de un arbol si y solo si

b. Idem a. para DFS.

PASO 1: poner i = 1, T = {e}, con e de longitud mnima

a. Probar que el algoritmo de Kruskal construye un arbol generador mnimo.

Referencias para este practico: [19], [4], [1]

nombre descripcion duracion predecesores

a. Armar el grafo PERT (actividades en los arcos) correspondiente a este problema.

Referencias para este practico: [5], [4], [12]

8.1. a. Encontrar un circuito euleriano en el grafo de la figura.

8.2. Analizar nuevamente el ejercicio 4.7.

salir de v0 por cualquier eje incidente

8.8. a. Para que valores de n, Kn tiene circuito euleriano?

c. Analizar el concepto de camino euleriano orientado para un digrafo.

8.16. Si G es un grafo con n 4 y d (grado mnimo) n 2 entonces G tiene un circuito hamiltoniano.

PASO 1: Dar un grafo completo G con longitudes asignadas a las aristas.

9.2. Probar que si T es un arbol, T es planar.

10.1. a) Calcular el numero cromatico de los siguientes grafos:

a) Si un grafo G contiene al grafo completo Ks como subgrafo inducido entonces (G) s.

a) Determinar la complejidad del algoritmo de a.

b) Como se puede determinar el numero cromatico de un grafo a partir de su polinomio cromati-

10.21. Calcular el ndice cromatico de los siguientes grafos:

a) Demostrar que 0 (G) m(G) | E(G) |.