← Volver a los ejercicios

Reconocer un árbol y contar sus piezas

Un árbol es un grafo no dirigido, conexo y acíclico, y tiene n − 1 aristas. Comprobar la conexidad o la ausencia de ciclos cuesta un recorrido; contar las aristas no cuesta nada. Aquí se decide con lo más barato que alcance en cada caso, y donde no alcance se dice que no alcanza.

1. Ocho grafos descritos por sus números

De cada uno se dan la cantidad de vértices, la cantidad de aristas y, en algunos, si es conexo o acíclico. Al escoger una opción aparece la retroalimentación de esa opción.

Resueltos: 0 de 8

2. Tres grafos dibujados

Los vértices van de p a w en los tres. Las aristas no tienen sentido ni peso.
¿Cuántas aristas tiene?
¿Cuántas hojas, es decir vértices de grado 1?
¿Cuántos ciclos independientes tiene?

3. Para llevarse

Sin solución aquí. Tome el segundo grafo y quite la arista que cierra el ciclo. La cuenta de hojas sube en uno: diga cuál de los dos extremos de esa arista se vuelve hoja y por qué el otro no, mirando solo sus grados. Después escriba, para un grafo acíclico cualquiera, cuántas componentes tiene en función de n y de |E|, y pruebe la fórmula con el tercer grafo.