Teoría de grafos · Definición
Árbol
Antes de empezar necesitas conocer
Es la estructura mínima que mantiene conectados a todos los vértices; aparece en jerarquías, redes y algoritmos de búsqueda.
Definición
Un árbol \(T=(V,E)\) es un grafo conexo que no contiene ciclos.
Un árbol con \(n\) vértices tiene exactamente \(n-1\) aristas. Esto equivale a las demás caracterizaciones: es conexo y sin ciclos; es conexo y al quitar cualquier arista deja de serlo; entre cada par de vértices hay un único camino simple. Cualquiera de ellas puede tomarse como definición y las demás se vuelven teoremas.
Todo árbol con al menos dos vértices tiene al menos dos hojas, vértices de grado 1: los extremos de un camino de longitud máxima lo son. Quitar una hoja deja un árbol más pequeño, y por eso muchas demostraciones sobre árboles son por inducción en el número de vértices. Un grafo sin ciclos, no necesariamente conexo, se llama bosque, y cada una de sus componentes es un árbol.
Ejemplo guía: el camino \(1,2,3,4,5\) es un árbol con 5 vértices y 4 aristas; si se le agrega la arista \(15\) aparece un ciclo y deja de ser un árbol. Un error típico es verificar solo el número de aristas: \(n-1\) aristas no bastan, pues un triángulo más un vértice aislado tiene 4 vértices y 3 aristas pero no es conexo. Los árboles generadores y la fórmula de Cayley, que cuenta \(n^{n-2}\) árboles etiquetados, parten de esta idea.
Para pensar
Un grafo con 5 vértices y 4 aristas, ¿es siempre un árbol?
No: un triángulo más una arista entre los otros dos vértices tiene 5 vértices y 4 aristas, pero no es conexo y tiene un ciclo. Hace falta además que sea conexo o que no tenga ciclos.
Ejercicios 10
- ¿Cuántas aristas tiene un árbol con 10 vértices?
- Un árbol tiene 15 aristas. ¿Cuántos vértices tiene?
- Los vértices son \(1,\dots,5\). ¿Cuál de estos conjuntos de aristas forma un árbol?
- ¿Cuánto suman los grados de los vértices de un árbol con 7 vértices?
- Un árbol con 7 vértices tiene un vértice de grado 4, uno de grado 3 y los demás son hojas (grado 1). ¿Cuántas hojas tiene?
- Se quita una arista de un árbol. ¿Cuántas componentes conexas tiene el grafo resultante?
- ¿Cuántos árboles distintos hay con vértices etiquetados \(1,2,3,4\)?
- Un grafo sin ciclos tiene 10 vértices y 3 componentes conexas. ¿Cuántas aristas hay que agregar, sin crear ciclos, para que sea un árbol?
- Se agrega a un árbol una arista entre dos vértices que no eran adyacentes. El resultado:
- ¿Cuál de las siguientes afirmaciones es verdadera para todo árbol?
Referencias
- Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §11.1
- Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §10.5
- Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §12.1