Tarea 10, Matemáticas discretas

Fecha de entrega: 22 de abril

Problema 1

1. Muestra que un árbol es un grafo bipartito.


2. ¿Es cierto que todo grafo bipartito es un árbol?

Problema 2

1. ¿Existe un grafo bipartito con vértices de grados 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 6 y 6?


2. 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

1. Muestra que un grafo bipartito en el cual todos sus vértices tienen el mismo grado tiene un apareamiento perfecto.


2. 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.