Tarea 9, Matemáticas discretas

Fecha de entrega: 15 de abril

Problema 1

1. Encuentra el número de árboles no etiquetados con 6 vértices.


2. Una estrella doble es un árbol con exactamente dos vértices con grado mayor que 1. ¿Cuántas estrellas dobles hay con n vértices?

Problema 2

Considera una matriz de $latex 2\times n-1$, cuyo primer renglón está formado por los números del 1 al $latex n-1$, y el segundo por números arbitrarios entre 0 y $latex n-1$. Construye el grafo con vértices $latex 0,1,2\ldots,n-1$ y aristas descritas por las columnas de esta matriz.

1. Muestra que este grafo no siempre es un árbol.


2. Demuestra que, si este grafo es conexo, entonces es un árbol.


3. Muestra que cada componente conexa tiene a lo más un ciclo.

Problema 3

Construye los árboles descritos por las siguientes codificaciones de Prüfer.

1. 433


2. 10520


3. 44444


4. 16976762


5. 426641

Problema 4

Construye los árboles descritos por las siguientes codificaciones planares

1. 11110000


2. 11100100


3. 11010100


4. 11010010


5. 11001010

Problema 5

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

Problema 6

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 7

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.