Matematicas Discretas

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 árbol que 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 de un 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 no tiene 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 descendientes directos 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 ser recorridos 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. ¿Puede ser 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 orden creciente 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 índice todos 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 el desarrollo del algoritmo.

ALGORITMO :

Sea G = (V, A) un grafo conexo, V’ = V un conjunto de vértices, A’ un vector de arcos inicialmente vacío y P un vector auxiliar inicialmente vacío:

1. Se introduce el vértice inicial en P y se elimina del conjunto.

2. Mientras V’ no sea vacío repetir los puntos 3 y 4. En otro caso parar.

3. Se toma el primer elemento de P como vértice activo.

4. Si el vértice activo tiene algún vértice adyacente que se encuentre en V’:

Se toma el de menor índice.

Se inserta en P como último elemento.

Se elimina de V’.

Se inserta en A’ el arco que le une con el vértice activo.

Si el vértice activo no tiene adyacentes se elimina de P.

...