-
Características
- Grafo en el cual entre todo par de vértices existe un único camino simple.
-
Un conjunto de árboles separados en el mismo grafo es llamado bosque.
- En un bosque que tiene K componentes se cumple que |V|=|A|+K
- Al agregar una arista entre dos vértices de un árbol, deja de ser árbol.
- Todas las aristas de un árbol son puentes.
-
Propiedades
- En todo árbol se cumple que: |V|=|A|+1
-
Nivel de un vértice
- Dado que el nivel de la raíz es cero y cada vértice tiene un nivel más que su padre, tenemos que:
si p es padre de v -> n(v)=n(p)+1
-
Altura de un árbol
- Es el mayor nivel alcanzado por las hojas
-
Árbol balanceado
- Se da cuando todas las hojas están en el nivel h o h-1
-
Elementos
-
Relacionados con los árboles de la naturaleza
-
Hojas
- Es un vértice cuyo grado es uno.
-
Rama
- Todo camino que va desde la raíz a alguna hoja.
-
Vértice interno
- Aquellos que no son la raíz ni las hojas.
-
Raíz
- Es un vértice único en el grafo cuyo grado positivo es cero.
-
Relacionados con los árboles genealógicos
-
Antecesor
- v es antecesor de w cuando existe un único camino simple de v a w.
-
Sucesor
- w es sucesor de v cuando existe un único camino simple de v a w.
-
Padre
- v es padre de w cuando existe una arista de v a w.
-
Hijo
- w es hijo de v cuando existe una arista de v a w.
-
Hermanos
- v y w son hermanos si tienen el mismo padre.
- Son un tipo de grafo conexo que no tiene ciclos.