Árboles.

Grafo conexo que no contienen ningún ciclo, existiendo siempre entre dos vértices una cadena. Igualmente se denomina así a un procedimiento  frecuentemente utilizado para tratar problemas de enumeración y probabilidad.

Elementos de un árbol.

Raíz: Vértice del que salen uno o más arcos pero no entran.

Brote: Vértice en el que termina uno o más arcos, pero del que no sale ninguno.

Nodo raíz: Es cuando salen más arcos de los que entran.

Nodo brote: Es cuando entran más arcos de los que salen.

Nodo eslabón: Nodo del que salen y entran igual cantidad de arcos.

Nodo eslabón simple: Es el que entra en un arco y sale en otro.

Propiedades de los árboles.

a) El grafo es conexo.

b) El grafo no tiene ciclos.

c) Si 'v' es el número de vértices; V-1 será el número de aristas.

d) Si suprimimos una arista cualquiera, el grafo deja de ser conexo.

e) Si se agrega una arista entre los dos vértices no adyacentes se forma un ciclo.

f) Para cada par de vértices hay una sóla cadena que los conecte.

En cumplimiento  de dos cuales quiera de estas propiedades define a un árbol.