matematicas

4. Árboles
Definición, elementos y características.

Un árbol es un grafo en el cual existe un único camino entre cada par de vértices.
Características de los árboles en general:
1. Todo árbolque no es vacío, tiene un único nodo raíz.
2. Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y. Es decir, X
es hijo de Y.
3. Un nodo X es antecesor directo deun nodo Y, si el nodo X apunta al nodo Y. Es decir, X es padre de Y.
4. Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son
hermanos.
5. Todo nodo que notiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja.
6. Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.
7. Grado es el número de descendientesdirectos de un determinado nodo. Grado del árbol es el
máximo grado de todos los nodos del árbol, es decir, el grado más alto entre todos los nodos.
8. Nivel es el número de arcos que deben serrecorridos para llegar a un determinado nodo. Por
definición la raíz tiene nivel 1.
9. Altura del árbol es el máximo número de niveles de todos los nodos del árbol.
Si el grafo G es un árbol. ¿Puedeser conexo?, ¿puede ser cíclico?

Árboles de expansión
Definición. Un árbol T es un árbol de expansión de una gráfica G si T es una subgráfica de G que contiene a
todos los vértices de G.
Teorema.Una grafica G tiene un árbol de expansión si y sólo si G es conexa.
Búsqueda a lo ancho
Se comienza en el vértice inicial (vértice con índice 1) y se marca como vértice activo, se visitan en ordencreciente de índice todos los vecinos del vértice activo antes de pasar al siguiente. Hasta que todos los
vértices hayan sido visitados, en cada paso se van visitando en orden creciente de índicetodos los vecinos
del vértice activo. Cuando se han visitado todos los vecinos del vértice activo, se toma como nuevo vértice
activo el primer vértice X visitado después del actual vértice activo en...