Fecha de entrega: 4 de mayo
Problema 1
Muestra que, si G tiene un apareamiento perfecto, entonces todo apareamiento maximal (en el sentido en que no existen aristas entre U y W libres) usa al menos la mitad de los vértices de G.
Problema 2
Utiliza el algoritmo de trayectorias de aumento para, si es posible, obtener un apareamiento perfecto del siguiente grafo.
Problema 3
Averigua si el siguiente grafo tiene un apareamiento perfecto.
Problem 4
Dadas al menos 3 rectas genéricas en el plano, muestra que entre las regiones en que dividen al plano se encuentra al menos un triángulo.
Problema 5
¿En cuántas regiones dividen al plano dos n-ágonos convexos?
Problema 6
¿Cuál es el mínimo y el máximo número de regiones en que dividen al plano n círculos?
Problema 7
- Muestra que 6 puntos genéricos en el plano forman al menos 3 cuadriláteros convexos.
- Encuentra 8 puntos genéricos en el plano que no contienen un pentágono convexo.
Comentarios
Publicar un comentario