5.3 Árboles

Hay un tipo especial de grafo, denominado árbol, que se presenta en

múltiples aplicaciones. En ciencias de la computación los árboles son parti

ticularmente útiles. Por ejemplo se utilizan para organizar información de

tal modo que sea posible efectuar eficientemente operaciones que atañan a

esa información. Para construir algoritmos eficientes para localizar artticulos

en una lista. Para construir códigos eficientes para almacenar y transmitir

datos. Para modelar procedimientos que son llevados a cabo al utilizar una

secuencia de decisiones. Introduzcamos pués el concepto de árbol.

Árbol

Un árbol es un grafo T = (V, E) acíclico y conexo

Dado que un árbol no puede tener ciclos, no podrá contener ni aristas

múltiples ni bucles, por lo tanto cualquier árbol debe ser un grafo simple.

 

Componentes

  Propiedades

Si T = (V, E) es un grafo de orden n, son equivalentes

1. T es un árbol.

2. Entre cualquier par de vértices de T existe un único camino.

3. T es conexo y toda arista de T es una arista puente.

4. T es acíclico y maximal respecto a esta propiedad.

5. T es conexo y tiene tamaño n -1.

6. T es acíclico y tiene tamaño n - 1.