MATEMATICA DISCRETA II-2015

PRACTICO 5 (Matchings)
I): Hallar matchings perfectos en los siguientes grafos bipartitos o probar que no existen.
i ii iii iv v vi vii viii
i ii iii iv v vi vii
A 1 1 0 1 1 0 0 0
A 0 1 1 0 0 0 1
B 1 0 0 1 0 0 1 0
B 0 1 0 1 0 1 1
C 1 0 1 0 1 1 0 0
C 0 1 0 0 0 0 0
a) b) D 0 1 0 0 0 0 0 0
D 1 1 0 0 0 1 0
E 0 1 0 0 1 0 0 1
E 1 1 0 0 1 1 0
F 1 0 0 0 0 1 1 0
F 0 0 0 1 0 0 0
G 1 0 1 0 0 0 1 0
G 0 1 0 0 0 1 0
H 1 1 0 1 0 0 0 0

i ii iii iv v vi vii viii i ii iii iv v vi vii viii

A 0 0 1 1 0 1 0 1 A 0 1 1 0 1 0 1 0
B 1 1 1 0 1 0 0 1 B 0 0 0 0 0 1 1 1
C 0 1 0 1 0 0 1 1 C 1 0 0 0 1 0 0 1
c) D 1 1 1 1 1 1 1 0 d) D 0 0 0 0 0 0 0 1
E 1 0 0 1 1 1 1 1 E 1 1 1 0 0 0 0 0
F 1 1 1 1 1 0 0 1 F 0 1 1 0 0 1 1 0
G 1 1 1 1 0 1 0 1 G 0 0 0 1 1 0 0 0
H 1 0 0 0 1 1 0 0 H 0 1 1 0 0 0 1 1
II): Probar que un grafo bipartito G = (X ∪ Y, E) con |X| = |Y | = 11 y E = 111 tiene un matching
perfecto.
III): Las siguientes matrices representan el costo de asignar los trabajos I, II, . . ., etc a los trabajadores
A, B, . . .,etc. de una empresa X. El costo lo pagaran los trabajadores. Hallar un matching que minimize el
mayor costo que deba pagar un trabajador.

I II III IV V VI V II V III IX
I II III IV V VI V II V III
A 9 8 8 5 6 6 8 6 8
A 1 2 5 5 3 8 2 9
B 5 6 7 4 2 3 6 5 6
B 9 8 8 9 8 8 1 3
C 5 5 5 2 2 3 4 3 9
C 3 1 5 8 9 6 5 8
D 8 7 4 5 5 5 4 6 4
a) D 9 1 7 9 3 8 8 5 b)
E 8 5 8 6 5 3 7 7 7
E 8 9 2 4 8 5 9 9
F 8 7 7 4 5 5 7 5 7
F 9 8 3 8 8 9 8 1
G 10 7 9 7 7 5 8 8 8
G 5 4 8 9 1 8 9 8
H 7 7 7 4 5 5 7 5 7
H 8 8 9 1 8 3 1 1
I 8 5 7 5 5 3 7 7 7

IV): Para completar un cierto proyecto se deben realizar ciertos trabajos I, II, ...., etc. Hay 7 trabajad-
ores que pueden hacer los trabajos, pero por motivos de politica interna no se quiere que ningún trabajador
realice mas de un trabajo. La siguiente matriz representa el tiempo en dias de asignar los trabajos I, II, . . .,
etc a los trabajadores A, B, . . .,etc. Los trabajos se pueden realizar en paralelo, i.e., no dependen uno de
otro.

I II III IV V V I V II
A 31 42 7 4 11 2 7
B 2 5 31 3 10 768 768
C 6 10 31 768 11 5 1
D 2 2 3 9 10 4 99
E 4 4 2 6 3 10 7
F 3 10 8 4 5 99 31
G 31 42 10 768 6 2 3

1
Encontrar un matching que minimize el tiempo para completar el proyecto y dar ese tiempo.
V): Para completar un cierto proyecto se deben realizar ciertos trabajos I, II, ...., etc. los cuales son
dependientes: antes de poder hacer I hay que hacer II, antes de hacer II hay que hacer III, etc. Hay 8
trabajadores que pueden hacer los trabajos, pero por motivos de politica interna no se quiere que ningún
trabajador realice mas de un trabajo. La siguiente matriz representa el tiempo en dias de asignar los trabajos
I, II, . . ., etc a los trabajadores A, B, . . .,etc. Encontrar un matching que minimize el tiempo para completar
el proyecto y dar ese tiempo.

I II III IV V VI V II V III
A 1 2 5 5 3 8 2 9
B 9 8 8 9 8 8 1 9
C 3 1 5 8 9 6 5 9
D 1 9 7 9 3 8 8 9
E 8 9 2 4 8 5 9 9
F 9 8 3 8 8 9 8 9
G 5 4 8 9 1 8 9 9
H 8 8 4 8 8 8 3 9

VI): Las siguientes matrices representan el costo que la empresa X debera incurrir al asignar los trabajos
I, II, . . ., etc a los trabajadores A, B, . . .,etc. Asignar todos los trabajos de forma tal que el costo total de la
empresa X sea minimo.

I II III IV V VI V II I II III IV V VI V II
A 8 5 4 6 8 6 5 A 7 4 6 9 1 9 4
B 4 4 6 6 8 6 5 B 8 5 9 2 7 5 4
C 8 6 9 9 8 9 9 C 7 2 3 3 7 3 6
a) b)
D 5 5 9 8 9 9 8 D 4 4 6 1 3 2 7
E 4 4 8 9 4 4 8 E 5 5 7 3 5 5 1
F 8 9 9 5 8 9 6 F 7 6 6 4 1 3 9
G 8 5 8 9 9 6 6 G 7 4 7 6 3 2 9
I II III IV V VI V II V III
A 1 2 3 3 1 8 4 2
I II III IV B 1 4 6 3 9 3 7 1
A 7 8 10 9 C 3 4 3 2 1 2 2 6
c) B 2 6 9 5 d) D 3 2 4 4 8 6 2 7
C 8 19 19 15 E 3 3 1 2 3 3 5 3
D 1 11 12 9 F 1 6 6 8 5 2 4 7
G 1 8 1 6 2 7 4 6
H 6 6 2 7 8 5 9 2
I II III IV V VI V II V III IX
A 1 2 2 4 7 3 3 9 8
B 5 6 5 6 9 9 7 8 6
C 4 5 6 6 9 4 6 6 7
D 2 3 4 5 9 9 2 9 3
e)
E 8 9 6 5 5 5 5 3 7
F 1 2 5 9 6 1 3 3 4
G 3 6 5 6 5 7 8 3 9
H 4 5 7 4 9 7 4 8 9
I 1 9 9 8 3 9 7 1 9

VII): La siguiente matriz representa el costo de asignar los trabajos I, II, . . ., etc a los trabajadores
A, B, . . .,etc. de una empresa X. El costo representa tanto el tiempo en horas que se tarda en hacer el

2
trabajo, como lo que cuesta el trabajo, en cientos de pesos. ([Link], el trabajador A tardará 9 horas en hacer
el trabajo I, y ademas la empresa debera pagar 900 pesos por el trabajo). Los trabajos se pueden realizar
en paralelo, i.e., no dependen uno de otro. La primera prioridad es terminar todos los trabajos en el menor
tiempo posible, pero, satisfecha esta prioridad, se desea que el costo total en dinero sea lo menor posible.
Es decir, la empresa desea encontrar, dentro del conjunto de matchings que minimizan el maximo, aquel
matching que tenga suma minima. Hallar tal matching, y decir en cuánto tiempo se terminarán todos los
trabajos y cuanto será el costo total en pesos.
I II III IV V VI V II V III IX
A 9 8 8 5 6 6 8 6 8
B 5 6 7 4 2 3 6 5 6
C 5 5 5 2 2 3 4 3 9
D 8 7 4 5 5 5 4 6 4
E 8 5 8 6 5 3 7 7 7
F 8 7 7 4 5 5 7 5 7
G 11 8 10 8 8 6 9 9 9
H 7 7 7 4 5 5 7 5 7
I 9 6 8 6 6 4 8 8 8

VIII): El ejercicio VII es un ejemplo de dada una matriz de costos, asignar los trabajos de forma de
minimizar la suma de los costos de entre todos los matchings que minimizen el mayor costo. Hacer esto con
la matriz del ejercicio VI c) y comparar con el costo que obtuvo antes.
IX): Ahora, pensar en el problema dual del anterior: de entre todos los matchings que minimizen
la suma, hallar uno que minimize el mayor costo. Desarrolle un algoritmo para resolver este problema y
aplicarlo en la matriz del ejercicio VII.
X): La siguientes matrices representa los ganancias que la empresa X obtendra al asignar los trabajos
I, II, . . ., etc a los trabajadores A, B, . . .,etc. Asignar todos los trabajos de forma tal que la ganancia total
de la empresa X sea maxima.

I II III IV V VI V II I II III IV V VI V II
A 8 1 7 3 9 3 1 A 1 5 1 4 5 4 5
B 5 7 3 4 8 7 1 B 6 1 4 5 1 1 5
C 8 4 8 8 8 8 7 C 1 5 6 6 1 6 9
a) b)
D 1 1 7 9 8 4 8 D 5 5 9 5 6 5 1
E 7 7 8 8 7 7 9 E 1 1 1 6 1 1 5
F 8 7 7 1 9 8 3 F 1 9 9 5 5 6 4
G 8 1 8 7 8 4 3 G 1 5 1 9 6 5 4
I II III IV V VI V II V III
A 9 8 7 7 3 6 1 8
B 9 6 4 7 2 5 8 3
C 7 6 7 8 3 7 7 4
c) D 7 8 6 6 6 4 7 8
E 5 5 3 7 5 5 9 5
F 3 4 4 6 9 7 1 8
G 3 6 3 4 7 8 1 4
H 4 4 7 8 6 9 2 7

XI): Suponga ahora que en el ejercicio anterior los numeros representan la ganancia que cada trabajador
obtendra para si mismo. Hallar un matching en cada caso que maximiza la ganancia minima.
XII): ¿Cual es la complejidad del algoritmo que resuelve el problema de minimizar la suma de entre
todos los matchings que minimizan el máximo? (com en el VII). ¿Cual es la complejidad del algoritmo que
resuelve el problema de minimizar el máximo de entre todos los matchings que minimizan la suma ? (el del
ej IX).