Tarea 11, Matemáticas discretas

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.

Bipartito.png

Problema 3

Averigua si el siguiente grafo tiene un apareamiento perfecto.

Chess.png

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

  1. Muestra que 6 puntos genéricos en el plano forman al menos 3 cuadriláteros convexos.
  2. Encuentra 8 puntos genéricos en el plano que no contienen un pentágono convexo.
Post Tagged with 

Comments & Responses

Leave a Reply