Fecha de entrega: 22 de abril
Problema 1
Problema 2
Problema 3
Sea G un grafo bipartito con el mismo número de nodos de cada lado tal que cada k vértices del lado izquierdo tienen k+1 vecinos del lado derecho. Muestra que cada arista de G se puede extender a un apareamiento perfecto.
Problema 4
Problema 5
Muestra que, si G tiene un apareamiento perfecto, entonces todo apareamiento codicioso usa al menos la mitad de los vértices de G.
Problema 6
Utiliza el algoritmo de extensiones de apareamientos codiciosos para, si es posible, obtener un apareamiento perfecto del siguiente grafo.
Problema 7
Averigua si el siguiente grafo tiene un apareamiento perfecto.
Problema 1
- Muestra que un árbol es un grafo bipartito.
- ¿Es cierto que todo grafo bipartito es un árbol?
Problema 2
- ¿Existe un grafo bipartito con vértices de grados 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 6 y 6?
- Un grafo bipartito tiene 16 vértices de grado 5 y cierto número de vértices de grado 8. Si sabemos que los vértices de grado 8 se encuentran en el mismo lado, ¿cuántos vértices de grado 8 puede tener?
Problema 3
Sea G un grafo bipartito con el mismo número de nodos de cada lado tal que cada k vértices del lado izquierdo tienen k+1 vecinos del lado derecho. Muestra que cada arista de G se puede extender a un apareamiento perfecto.
Problema 4
- Muestra que un grafo bipartito en el cual todos sus vértices tienen el mismo grado tiene un apareamiento perfecto.
- Da un ejemplo de un grafo con todos sus vértices del mismo grado que no tiene un apareamiento perfecto.
Problema 5
Muestra que, si G tiene un apareamiento perfecto, entonces todo apareamiento codicioso usa al menos la mitad de los vértices de G.
Problema 6
Utiliza el algoritmo de extensiones de apareamientos codiciosos para, si es posible, obtener un apareamiento perfecto del siguiente grafo.
Problema 7
Averigua si el siguiente grafo tiene un apareamiento perfecto.
Comentarios
Publicar un comentario