ARBOLES Y

GRAFOS
Grupo 15
 INTEGRANTES

1. Evelin Garcia Rojas

2. Maribel Flores Arenas
3. Andrea Guadalupe Mamani Valdez
4. Juan David Arispe leon
5. Luis Alberto Angulo Soto
6. Angela Molle Amaru
7. Sebastian Rojas Becerra
8. Fabiola Coca Omonte
9. Rodrigo Pierre Soliz Cespedes
ÁRBOLES - ESTRUCTURAS DE DATOS NO
LINEALES

Los Árboles se caracterizan

por almacenar sus nodos en
forma jerárquica y no en
forma lineal como las Listas
Ligadas como Colas y Pilas.
 DATOS IMPORTANTES

Para comprender mejor qué es un árbol comenzaremos explicando como está

estructurado.
■ Nodos: Se le llama Nodo a cada
elemento que contiene un Árbol.
■ Nodo Raíz: Se refiere al primer nodo
de un Árbol.
■ Nodo Padre: Se utiliza este
término para llamar a todos
aquellos nodos que tiene al
menos un hijo.
■ Nodo Hijo: Los hijos son
todos aquellos nodos que
tiene un padre.
■ Nodo Hermano: Los nodos
hermanos son aquellos nodos
que comparte a un mismo
padre en común dentro de la
estructura.
Nodo Hoja: Son todos aquellos nodos que no tienen hijos, los cuales siempre se
encuentran en los extremos de la estructura.
Nodo Rama: Estos son todos aquellos nodos que no son la raíz y que además tiene al
menos un hijo.
 PROPIEDADES
Nivel: Nos referimos como nivel a cada generación
dentro del árbol. Por ejemplo, cuando a un nodo hoja
le agregamos un hijo, el nodo hoja pasa a ser un nodo
rama pero además el arbol crece una generación por
lo que el Árbol tiene un nivel más . Cada generación
tiene un número de Nivel distinto que las demás
generaciones
■ Un árbol vacío tiene 0 niveles
■ El nivel de la Raíz es 1
■ El nivel de cada nodo se calculado contando cuantos nodos existen sobre el, hasta llegar a la
raíz + 1, y de forma inversa también se podría, contar cuantos nodos existes desde la raíz hasta
el nodo buscado + 1.
ALTURA

■ Le llamamos Altura al número máximo de niveles de un Árbol.

■ La altura es calculado mediante recursividad tomando el nivel mas grande de los dos sub-árboles
de forma recursiva de la siguiente manera: altura = Max(altura(hijo1), altura(hijo2), altura(hijoN))
+1
PESO
■ Conocemos como peso a el número de nodos que tiene un Árbol.
■ Este factor es importante por que nos da una idea del tamaño del árbol y el tamaño en
memoria que nos puede ocupar en tiempo de ejecución.
■ El peso se puede calcular mediante cualquier tipo de recorrido el cual vaya contando los nodo
a medida que avanza sobre la estructura. El peso es un árbol es igual a la suma del peso de los
sub-árboles hijos + 1 peso = peso(hijo1) + peso(hijo2) + peso(hijoN)+ 1
ORDEN
■ El orden de un árbol es el número máximo de hijos que puede tener un Nodo.
■ El número de hijos es un valor que no se calcula, sino que se conoce antes de crear un árbol.
■ Los hijos de un Nodo pueden estar ordenados o no.
■ Se suele ordenar de izquierda a derecha.
GRADO
■ El grado es el número mayor de hijos que tiene un nodo y está limitada por el orden.
■ El grado se calcula contando de forma recursiva el número de hijos de cada sub-árbol hijo y el
número de hijos del nodo actual para tomar el mayor.
■ El grado de un árbol se define como el máximo grado de todos sus nodos.

grado = max(contarHijos(hijo1),contarHijos(hijo2), contarHijos(hijoN), contarHijos(this))

SUB-ARBOL
■ Un Sub-Árbol es todo aquel Árbol generado a partir de una sección determinada del Árbol.
■ Podemos sacar un Sub-Árboles del Árbol para procesarlo de forma separada, para que sea un
árbol independiente.
■ Podemos eliminar Sub-Árboles completos, agregarlos, entre otras operaciones.
 ARBOLES N-ARIOS

Un árbol n-ario es una estructura

recursiva, en la cual cada elemento tiene
un número cualquiera de árboles n-arios
asociados. Estos árboles corresponden a
la generalización de un árbol binario. La
diferencia radia en que esta estructura
puede manejar múltiples sub árboles
asociados a cada elemento, y no
solamente 2, como en el caso de los
árboles binarios.
 USOS

■ Árbol de búsqueda binario.- que se utiliza en muchas aplicaciones de búsqueda donde los
datos son constantemente entrada/salida tales como map y set objetos en muchos idiomas,
bibliotecas.
■ Binary Space Partition.- que se Utiliza en casi todos los de vídeo 3D juego para determinar qué
objetos deben ser prestados.
■ Binario trata.- se Utiliza en casi todos los de alto ancho de banda del router para almacenar
router-tablas.
■ Hash Árboles.- se usa en los programas p2p y especializado imagen de la firma en la que un
hash debe ser verificado, pero todo el archivo no está disponible.
 ARBOLES BINARIOS
Definición.

Los árboles binarios son estructuras de datos muy similares a las listas doblemente enlazadas, en el
sentido que tienen dos punteros que apuntan a otros elementos, pero no tienen una estructura
lógica de tipo lineal o secuencial como aquellas, sino ramificada. Tienen aspecto de árbol, de ahí su
nombre.
Un árbol binario es una estructura de datos no lineal en la que cada nodo puede apuntar a uno o
máximo a dos nodos. También se suele dar una definición recursiva que indica que es una estructura
compuesta por un dato y dos árboles. Esto son definiciones simples. Este tipo de árbol se caracteriza
porque tienen un vértice principal y de él se desprende dos ramas. La rama izquierda y la rama
derecha a las que también se les conoce como subárboles.
La rama izquierda y la derecha, también son dos árboles binarios. El Vértice principal se
denomina raíz y cada una de las ramas se puede denominar como subárbol izquierdo y
subárbol derecho
 Tipos de Árboles Binarios
Árboles binarios distintos. - Árboles binarios similares. -
Árboles binarios Equivalentes. - Árboles binarios completos. -
 RECORRIDO SOBRE ÁRBOLES

El recorrido de árboles se refiere al proceso de visitar de

una manera sistemática, exactamente una vez, cada nodo
en una estructura de datos de árbol Tales recorridos están
clasificados por el orden en el cual son visitados los nodos.
Los siguientes algoritmos son descritos para un árbol
binario, pero también pueden ser generalizados a otros
árboles.
 TIPOS DE RECORRIDO SOBRE ÁRBOLES

Existen 4 tipos de recorrido sobre

árboles:

Pre-orden:En un recorrido en
preorden, visitamos primero el nodo
raíz, luego recursivamente
realizamos un recorrido en preorden
del subárbol izquierdo, seguido de
un recorrido recursivo en preorden
del subárbol derecho.
In-orden: En un recorrido en
inorden, realizamos
recursivamente un recorrido en
inorden en el subárbol izquierdo,
visitamos el nodo raíz, y
finalmente hacemos un recorrido
recursivo en inorden del subárbol
derecho
Post-orden: En un recorrido en
postorden, realizamos
recursivamente recorridos en
postorden del subárbol izquierdo y
del subárbol derecho seguidos de
una visita al nodo raíz
Busqueda en amplitud: Se recorre primero
la raíz, luego se recorren los demás nodos
ordenados por el nivel al que pertenecen en
orden de Izquierda a derecha.

Este tipo de búsqueda se caracteriza por que

la búsqueda se hace nivel por nivel y de
izquierda a derecha.
TEORIA DE GRAFOS
ORIGEN
La teoría de grafos, nacida en el siglo
XVIII, se fundamenta en la matemática
discreta y aplicada, abarcando conceptos
de combinatoria, álgebra, probabilidad,
geometría, aritmética y topología. Surgió
con el problema de los puentes de
Königsberg, resuelto por Euler en 1736,
marcando el inicio de la teoría.
 ES APLICADA EN:
01 02 03
Ciencias de la computación Ciencias sociales Ciencias Físicas e
● Inteligencia artificial ● Modelado de Ingeniería de
● Lenguajes formales problemas y redes
● Teoría de cambio y diseño sociales Comunicación:
● Gráficos, sistemas operativos, ● Aplicaciones en física
compiladores y comunicación
05
04 Planificación y Programación: 06
● Programación de
Urbanismo y Cartografía: exámenes y horarios Gestión de Proyectos:
● Distribución de ● Determinación de
● Planificación urbana servicios públicos
● Coloreado de mapas tiempos en proyectos
● Diseño de boards
electrónicos
 GRAFOS
¿QUE SON GRAFOS?
Los grafos son estructuras discretas que constan de vértices y aristas que conectan
entre si esos vertices. Por lo tanto un grafo G costa de dos partes:

1) Un conjunto V = V (G) cuyos elementos se denominan vertices, puntos o nodos de G.

2) Un conjunto E = E(G) de pares de vértices distintos denominados aristas de G.

Ejemplo de
gráfica de grafo
 Tipos de grafos

Los grafos ofrecen un amplio esquema de

posibilidades. Esto es en parte gracias a
sus versátiles formas de composición
Grafos simples

● Son los que se generan cuando

un conjunto no vacío de vértices
o nodos está unido a otro a
través de una o más aristas.
Grafos dirigidos

● Son una especie de grafo que cuentan con

elementos clásicos de un grafo simple pero
con la particularidad de que sus aristas que
conectan los nodos tienen una
direccionalidad clara.
Grafos completos
● Un grafo completo de
forma similar cumple con
los requisitos de un grafo
simple o dirigido ● La diferencia que se presenta en
este tipo de grafos es que cada par
de nodos debe estar
interconectado entre sí con
diferentes conjuntos de aristas que
conforman un camino.
Grafos conexos
● son aquellos que cumplen con una
condición especial.

● Para que un grafo se considere conexo

entre los nodos que lo integran deben
existir “caminos simples”. De esta
estructuración de nodos nace lo que
conocemos como árboles de grafos.
Grafos etiquetados

● Los grafos etiquetados incorporan datos en las aristas que

le proporcionan peso a un grafo y estos son los más
comunes en el mundo informático en el que vivimos.
 Orden de un grafo

El orden de un grafo se define

como la cantidad total de vértices o
nodos que lo componen. En
términos matemáticos, si
denotamos el conjunto de vértices
como V, entonces el orden,
representado como ∣V∣,
corresponde al número de
elementos en ese conjunto.
 Cómo calcular el orden de un grafo
Para calcular el orden de un grafo:

1.Identificación de Vértices:

• Examina el grafo y determina cuáles son los

vértices. Cada punto o nodo en el grafo se considera
un vértice.

2. Conteo de Vértices:

• Simplemente cuenta cuántos vértices hay en el

grafo. Puedes hacer esto revisando la lista de vértices
si está proporcionada o contando visualmente los
puntos en el grafo.
3. Notación del Orden:
• Utiliza la notación ∣V∣ para
representar el orden del grafo, donde
V es el conjunto de vértices.

Por ejemplo, si tienes un grafo con

los vértices A, B, C y D, el conjunto
de vértices sería V={A,B,C,D}, y el
orden del grafo sería ∣V∣=4, ya que
hay cuatro vértices en total.
Tipos de Orden de Grafos

● Ordenar Ciclico
En este caso existe un método directo, en
el que podemos establecer el orden del
grafo.
Se parte de un vértice dado en cero, y los
demás vértices se deben organizar en el
sentido de las agujas del reloj.
● Ordenar un Grafo con otro Grafo

● Orden de un Grafo con

otro Grafo
Debemos conectar dos nodos
enteros con otro nodo,
devolviendonos un subgrafo.