Segundo Parcial 10/07/2002 (Algoritmos III)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia


1)
Hay que hallar un circ. hamiltoniano. Un tablero de ajedrez de nxn se puede colorear con 2 colores, por lo que es un grafo bipartito. Entonces n tiene que ser par, porque esto asegura que las 2 particiones tengan la misma cantidad de vertices, por lo tanto se puede cerrar el circuito, mientras que si fuera par habria que cerrar el circuito en una misma particion, y esto no es posible.


2)
Esta hecho en 3) de 8/ago/2005


3)
La idea es que como u y v no son adyacentes pueden pintarse del mismo color, porque todos los adyacentes a u tambien lo seran a v y por lo tanto no hay forma que tengan el mismo color que u (o v)


4)
Te haces el grafo bipartito, para que cuando hagas el flujo te da la cantidad maxima de tareas que podes ejecutar, o sea, por cada maquina podes ir a cada tarea y cada tarea te consume algunos recursos. la idea es que tenes un flujo minimo de las tareas a los recursos (lo obligas a consumir esa cantidad) y de los recursos a t tenes el eje con la cantidad de recursos, entonces el flujo maximo ahi te dice cuales se pueden ejecutar a la vez. igual tenes el problema de elegirlas en el mejor orden

todas las tareas duran lo mismo. haces el matching de tareas que pueden ir juntas y las pones a la vez, las que te quedan las tenes que poner de a 1. haces un grafo con N nodos, cada uno representa una tarea, dos tareas son adyacentes si pueden ejecutar a la vez. haces el matching maximo de eso (tenes el algoritmo), metes los pares de tareas en las maquinas en el orden que se te cante el orto. las tareas que no tenian un matching forman un conjunto conflictivo que comparte recursos de a pares, a esas las tenes que meter de a 1 por vez. sea N la cantidad de tareas y J las que no matchean ( o sea que tenes (N - J) / 2 pares). terminas tardando ( N/2+J/2 ) * T donde T es el tiempo que demora una tarea cualquiera.


5)
1->2) Se puede agregar s y t conectandolos a todos los vertices a G formando H, y k pasaria a ser k+2
2->1) Se pueden sacar todos los caminos que no van de s a t de H