Tarea 9, Matemáticas discretas

Fecha de entrega: 20 de abril

Problema 1

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


2. Encuentra el número de estrellas etiquetadas 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. 4330


2. 105200


3. 444440


4. 169767620


5. 4266410

Problema 4

Construye los árboles descritos por las siguientes codificaciones planares

1. 11110000


2. 11100100


3. 11010100


4. 11010010


5. 11001010