Tarea 10, Matemáticas discretas

Fecha de entrega: 27 de abril

Problema 1

Muestra que, si los costos de todas las aristas son distintos, entonces hay un único árbol más barato.

Problema 2

Describe cómo construir árboles para los cuales:

1. el producto del costo de sus aristas es mínimo;


2. el máximo costo de sus aristas es mínimo.

Problema 3

Si la capital de un gobierno se encuentra en el vértice r, la primer línea construida será la línea más barata que sale de r, digamos, a s. Después, construiremos la línea más barata que sale de r o de s, y así sucesivamente. Muestra que el árbol que resulta es, de nuevo, el más barato.

Problema 4

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


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

Problema 5

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 6

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 7

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.