examen

Gráficas y Juegos
Mucuy Guevara y Alex Juárez
Parcial 4 (Tarea-Examen)
Se entrega el viernes 1o. de junio.
1. Los campesinos Nacho y Panchodejan pastar sus vacas en el mismo campo. Si hay 20
vacas pastando, cada vaca produce 5 unidades de leche (UL) en toda su vida. Si hay más
de 20vacas, entonces cada vaca tendra acceso a menos pasto y la producción de leche cae:
con 30 vacas en el campo, cada vaca produce 3.5 UL en toda suvida, con 40 vacas 2.5 UL.
Lo que cuesta cada vaca es equivalente a 1 UL y cada campesino puede comprar 10 o 20
vacas. Determina el equilibrio deNash de este juego. ¿El equilibrio de Nash cambia si
consideramos que Pancho sabe el número de vacas que va a comprar Nacho? ¿Y si Nacho
sabecuántas vacas va a comprar Pancho?
2. Escribe la prueba (que platicamos en clase) de que una digráfica simétrica tiene núcleo.
3. Sea D una digráfica.Demuestra que es posible enumerar a las componentes fuertemente
conexas (C1 , C2 , . . . Cl ) de tal manera que no haya flechas de Ci a Cj con i > j.4. Demuestra que un núcleo N es un conjunto independiente maximal, esto es que no existe
un conjunto independiente que contenga a N.
5. Pruebaque un núcleo es un absorbente minimal, es decir que no existe un conjunto absorbente contenido en N.
6. Demuestra que un digráfica transitivatiene núcleo y que todos sus núcleos tienen la
misma cardinalidad.
7. Demuestra que una digráfica que no tiene ciclos dirigidos tiene núcleo.