Arboles y grafos

Arboles

Matemáticas Discretas
Capítulo 6: Arboles

Introducción
Definición: Un árbol (libre) T es una gráfica que satisface:
Si v y w son vértices en T, entonces existe un único camino simple de v a w .

Arbol con raiz es un árbol en el cual un vértice particular se designa como la raíz.

1

2

Arboles

Arboles

Cont…
Graf Campeona de Wimbledon Graf Sabatini Graf Seles SelesNavratilova

Cont…
Un árbol es un grafo conexo y sin ciclos.

Propiedades:
Si G = (V,A) es un árbol de n vértices, entonces: a) Para todo par de vértices x e y existe un único camino de x a y. b) Todas las aristas de G son puentes. c) A = n - 1. d) Todo árbol tiene al menos dos hojas (vértices de grado uno).

V1 V2 V3

V4

V5

V6

V7

3

4

1

Arboles

Arboles

Cont…Uso típico de los arboles:
representación de estructuras jerárquicas organizaciones árbol genealógico directorios acceso rápido a datos ordenados en número desconocido como vectores ordenados respecto a vectores normales sistemas de ficheros avanzados elementos de representación en juegos sistemas de compresión

Cont…
La terminología
Hijo: X es hijo de Y, sí y solo sí el nodo X es apuntadopor Y. También se dice que X es descendiente directo de Y. Padre: X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y. Hermano: Dos nodos serán hermanos si son descendientes directos de un mismo nodo. Hoja: Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos).

5

6

Arboles

Arboles

Cont…
Cont...
Nodo Interior: Es unnodo que no es raíz ni terminal. Grado: Es el número de descendientes directos de un determinado nodo. Grado del Arbol: Es el máximo grado de todos los nodos del árbol. Nivel de un vértice: 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. Es la longitud del camino simple de la raíz al nodo.
7

Cont…
Cont...
Altura: Es elnúmero máximo de nivel, de todos los nodos, que aparece en el árbol. Peso: Es el número de nodos del árbol sin contar la raíz. Longitud de Camino: Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente.

8

2

Arboles

Arboles

Cont...Cont...
Ejemplo 1:
Para el árbol dado los vértices v1, v2, v3, v4, v5,v6, v7 tienen los niveles 0, 1, 1, 2, 2, 2, 2 La altura del árbol es 2
V1 V2 V3

Cont...
Cont...
Ejercicio en clases:
Para el árbol T considere que la raíz es e, g, d
d a b e j h c f g i

V4

V5

V6

V7
9 10

Arboles

Arboles

Cont…
Terminología y Caracterizaciones
Definición: Sea T un árbol con raíz v0.Suponga que x, y y z son vértices en T y que (v0, v1, ..., vn) es un camino simple en T. Entonces: a) Vn-1 es el padre de vn b) v0, v1, ..., vn-1 son ancestros de vn. c) Vn es un hijo de vn-1. d) Si x es un ancestro de y, y es un descendiente de x. e) Si x y y son hijos de z, x y y son hermanos. f) Si x no tiene hijos, x es vértice terminal (o una hoja) g) Si x no es un vértice terminal, x es unvértice interno (o una rama). h) El subárbol de T con raíz en x es la gráfica con conjunto de vértices V y conjunto de aristas E, donde V es x junto con los descendientes de xy 11

Cont...
Cont... Teorema:
Sea T una gráfica con n vértices. Las siguientes afirmaciones son equivalentes: a) T es un árbol b) T es conexa y acíclica c) T es conexa y tiene n-1 aristas d) T es acíclica y tiene n-1aristas

12

3

Arboles

Arboles

Arboles de expansión
Definición:
Un árbol T es un árbol de expansión de una gráfica G si T es una subgrafica de G que contiene a todos los vértices de G. Observemos la definición del siguiente modo: Sea una grafica G, encontramos una sub. grafica de G del tal modo que esta sub. grafica contenga todos los vértices de la grafica original, ósea de G, a...