Hoja6b Optred

PROBLEMAS DE OPTIMIZACIÓN EN REDES.

Hoja 6

1. Sea G=(V,A) un grafo simple con V = {0, 1, 2, 3, 4, 5, 6, 7} y A = {01, 12, 23, 34, 45, 40, 26, 67, 73}.
Encontrar un emparejamiento máximo en Gempezando por el emparejamiento M = {12, 34, 67} ¿Es
completo? Encontrar un recubrimiento mínimo.
2. Con motivo de su regreso al país, Horacio desea invitar a su casa a sus antiguos amigos de estudios:Pablo, Diego, Gaspar, Julián y Nicolás. Sin embargo, a pesar de que Horacio mantiene buenas relaciones
con cada uno de sus compañeros, entre ellos han surgido diferencias al pasar de los años:
Nicolás yGaspar riñeron por cuestiones de trabajo.
Pablo es ahora de derechas mientras que Nicolás sigue siendo de izquierdas.
Julián le debe dinero a Nicolás.
Pablo, Julián y Diego son forofos de distintosequipos de futbol, por lo que siempre terminan
peleando.
Ante esta situación, Horacio se da cuenta de que será necesario hacer más de una reunión para poder
verlos a todos sin que se presentensituaciones incómodas, pero por otro lado, la situación económica lo
obliga a realizar el mínimo de reuniones posibles. ¿Cuántas reuniones debe organizar y a quien invitará
a cada una?
3. Se va a celebrar uncongreso en Sidney y un grupo de científicos residentes en New York, deciden a
última hora asistir al congreso. Al ir a la agencia de viajes, dada la premura del tiempo, les dicen que
quedan pocasplazas y les dan el siguientes esquema (ver gráfico), cada flecha indica la posibilidad de
vuelo entre dos ciudades, y el número que hay a lado de la flecha indica el número de plazas libres que
hay parapoder ir en vuelo de una ciudad a otra. Teniendo en cuenta todos estos datos, ¿cuál será la
mayor cantidad de científicos que podrán ir al congreso en Sidney?

4. Uno de los mayores problemas que seplantea en internet es decidir por donde enviar los ficheros que
reciben los distintos servidores. Una visión miope o local del asunto podría llevar a que cada router
enviase los mensajes por la...