Post on 19-Jun-2015
description
Árboles Binarios y Grafos
Árboles Binarios• Un árbol binario es una estructura
recursiva. Cada nodo es la raíz de su propio subárbol y tiene hijos, que son raíces de árboles llamados subárbols derecho e izquierdo del nodo, respectivamente.
• Un árbol binario se divide en tres subconjuntos:
• R Nodo raíz
{ I1, I2,…,In }Subárbol izquierdo de R
{ D1, D2,…,Dn }Subárbol derecho de R.
R
I1
D1
I2 I3 D2
Pablo
D3
•En un árbol binario, cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.
X
Y Z
Padre o Raíz
Subárbol Izquierdo Subárbol Derecho
Pablo
•En un árbol binario, cada elemento tiene cero, uno o dos hijos. El nodo raíz no tiene un padre, pero sí cada elemento restante tiene un padre.
•En el ejemplo, X es un antecesor de Y
X
Y Z
Padre o Raíz
Subárbol Izquierdo Subárbol Derecho
Pablo
Ejemplo:A
B C
D E F G
Árbol Binario Equilibrado
A
B
C D
E
F
Árbol Binario No-Equilibrado
• Un árbol binario puede estar equilibrado o no equilibrado. Para que un árbol binario este equilibrado cada uno de sus sub árboles izquierdos y derechos deben de cumplir la siguiente condición: Estar vacios o presentar el mismo número de elementos
Pablo
Caracteristicas de Arboles Binario
Características
Estructuras de control de informaciónNo más de 2 subárboles por nodo
Puede contener de 1 a 2n
cada nodo puede ser la raíz de unsubárbol
Recursivos
Cada nodo puede tener 0,1 ó 2 hijos
Noel
Recorrido de Un Árbol Binario•Un árbol binario puede ser recorrido de tres
formas PRE-ORDEN•1. Preorden: La raíz se procesa antes que los
subárboles izquierdo y derecho.•El recorrido en preorden (NID) conlleva los
siguientes pasos: 1. Recorrer la raíz (N) 2. Recorrer el subárbol izquierdo (I)3. Recorrer el subárbol derecho (D)
Noel
Algoritmo Preeorden• Si A no es vacío entonces
inicio ver los datos den la raíz de T preeorden (subárbol izquierdo del raíz de T) preeorden (subárbol derecho del raíz de T) fin.
Noel
EjemploA
B C
D E F G
1
2
3 4
5
6 7
Recorrido PreOrden:
A B D E C F G
Noel
A
B
C D
E
F
1
2
3
4
5 6
Recorrido PreOrden:
A B C D E F
Noel
•Recorrido En orden: Procesa primero el subárbol izquierdo, después la raíz y a continuación el subárbol derecho. El significado “en” es que la raíz se procesa entre los subárboles. Si el árbol no está vacio, el método implica los siguientes pasos:
1. Recorrer todo el subárbol Izquierdo (I)2. Visitar el Nodo Raíz (N)3. Recorrer todo el subárbol Derecho (D)
Noel
Algoritmo
•Si el árbol no esta vacío entonces inicio recorrer el subárbol izquierdo visitar el nodo raíz recorrer el subárbol derecho
•Fin
Noel
2
5
1
7
4
8
10
12
Primerose resuelve este lado
2
3
4
5
6
8
9
10
1 7 5 4
Ahora resuelve este lado
8 12 10
Recorrido : = 1 7 5 4 2 8 12 10
Noel
A
B
C D
E
F
Recorrido: C B E F D A
1
2
3
4
5
6A
B
H
I J
K
L M
C
D
E
F G
1
2
34
5
6
7
8
9
10
11
12
13
Recorrido: I L K M H J B A C D F E G
Noel
•Recorrido postorden: (IDN) procesa el nodo raíz (post) después de que los subárboles izquierdo y derecho se han procesado. Se comienza situándose en la hoja más a la izquierda y se procesa. A continuación se procesa el subárbol derecho. Por último, se procesa el nodo raíz. Las etapas del algoritmo son:
1. Recorrer el subárbol izquierdo (I)2. Recorrer el subárbol derecho (D)3. Recorrer el nodo Raíz (N)
Noel
Algoritmo
•Si A no esta vacio entonces inicio postorden (subárbol izquierdo del raíz de A) postorden (subarbol derecho del raíz de A) Visualizar los datos del raíz de A
•Fin
Noel
EjemploA
B C
D E F G
1 2
3
4 5
6
7Recorrido: D E B F G C A
+
*
A B
^
/
c d
3.5
1
3
2
4
6
5
8
7
9
Recorrido: A B * C D / 3.5 ^ +
Noel
GRAFOS•Para las ciencias de la
computación y la matemática, un grafo es una representación gráfica de diversos puntos que se conocen como nodos o vértices, los cuales se encuentran unidos a través de líneas que reciben el nombre de aristas.
Josue
Caracterización de grafos
• Grafos simples: Un grafo es simple. si a lo más existe una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.
• Grafos conexos: Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.
Un grafo es doblemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.Un grafo es doblemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.
Un grafo es doblemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.
Grafos simples
Josue
•Grafo dirigido: Un grafo dirigido es un tipo de grafo en el cual las aristas tienen una dirección definida,1 a diferencia del grafo generalizado, en el cual la dirección puede estar especificada o no.
•Grafo aleatorio Se denomina grafo aleatorio a un grafo que es generado por algún tipo de proceso aleatorio. La teoría de los grafos aleatorios cae en la intersección entre la teoría de grafos y la teoría de probabilidades y se fundamenta en el estudio de ciertas propiedades de los grafos aleatorios. Josue
En matemática y ciencias de la computación, un hipergrafo es una generalización de un grafo, cuyas aristas aquí se llaman hiperaristas, y pueden relacionar a cualquier cantidad de vértices, en lugar de sólo un máximo de dos como en el caso particular.
Hipergrafo
Josue
Gracias
FIN.