- Altura de un nodo = distancia a la raíz

- Nivel de un nodo = altura + 1

- Profundidad árbol = máximo nivel

Arboles binarios

Arbol ABB (Arbol binario de búsqueda)

Es una árbol binario que para cada nodo, a su izquierda tiene elementos menores a el y a su derecha elementos mayores a el

Para la eliminacion hay que considerar 3 casos

- Grado 0 = Simplemente se elimina el nodo

- Grado 1 = Se promueve el hijo, se sube un nivel toda el subárbol que no es null y se elimina el nodo
- Grado 2 = Se promueve un nodo. No se elimina el nodo buscado, se elimina el nodo que se promueve y se actualizan
los datos del nodo buscado a los datos del nodo promovido
o Se promueve el hijo lo mas a la derecha posible del subárbol izq
o Se promueve el hijo lo mas a la izquierda posible del subárbol derecho

ABB + inorden = secuencia ordenada

Arbol AVL

Es un árbol binario de búsqueda que esta balanceado por su altura, es decir, su factor de equilibrio (diferencia entre subárbol
izquierdo y derecho) es a lo sumo 1

Arboles general o n-arios

La implementación del árbol n-ario no se ve en esta materia. Se trabaja directamente con los operadores de los cuales
tampoco tenemos la implementacion

Int Vacio(A); Devuelve verdadero si A es arbol vacio

Int Nulo(p); Devulve verdadero si p es la posición nula
Posición HijoMasIzq(p, A); Devuelve la posición del hijo mas a la izquierda de p, si p es hoja
devuelve una posición nula
Posicion HermanoDer(p, A); Devuelve la posición del hermano de la derecha de p (mismo padre),
si p es el del extremo derecho, devuelve una posición nula
Int (o char) Info(p, A); Devuelve el dato del nodo en la posición p en el arbol A
Posición Raiz(A); Devuelve una posicion que es la raíz del árbol A
Posición Padre(p, A); Devuelve la posición del padre de la posicion p en el árbol A, si p es
la raíz, devuelve una posición nula
Es un error llamar a una de estas funciones con p NULO (excepto Nulo(p))

Recorridos

Pre-orden In-orden Post-orden

1. Visitar nodo 1. Inorden a subarbol 1 1. Postorden subarbol 1…n
2. Preorden subarbol 1…n 2. Visitar nodo 2. Visitar
3. Inorden subarbol 2…n
La raiz se muestra primera Muestro cuando subo por la izq Muestro cuando subo por la derecha. La
raíz se muestra ultima

Bosque = Conjunto de arboles

Arboles binarios de arboles generales o bosques

1. Si es un bosque, se unen todas las raices

2. Unir todos los hermanos
3. Cortar todos los enlaces con los hijos menos con el de mas a la izquierda
4. Rotar en sentido horario levemente

A partir de este árbol binario, podemos obtener la cantidad de hojas, profundidad y grado del árbol general o bosque

- Cantidad de arboles que generaban el bosque = altura de la rama derecha de la raíz, ya que estos son las raíces de los
arboles

Si se quiere calcular propiedades especificas de un árbol y no del bosque. Recorro el subárbol derecho de la raíz hasta la raíz
del árbol deseado y analizo a partir de su hijo izquierdo (para no analizar la primer rama derecha que seria otro árbol)
 Arbol binario de árbol general Arbol general

Cant sin hijos en izquierda

La rama derecha mas larga

Grafos

- Digrafo = Grafo pero las aristas tienen dirección

- Grafo/Digrafo ponderado = Las aristas tienen peso
- La arista (v, w) es incidente en v y w
- Si existe (v, w) en un grafo las mismas son adyacentes
- Si existe la arista (v, w) en un digrafo, w es adyancente a v
- Multigrafo = Grafo o digrafo que admite mas de una arista entre un par de nodos
- Orden del grafo = cantidad de elementos en V (cant de vertices)
- Grado de un vertice = Aristas incidentes en el
o Grado de entrada = aristas que cuyo origen es v
o Grado de salida = aristas que cuyo destino es v
o El graod de un nodo con bucle = Ge(v) + Gs(v) - #bucles
- Subgrafo = Sea G = (V, E), un subgrafo G’ = (V’, E’) tal que 𝑉′ ⊆ 𝑉 y 𝐸′ ⊆ 𝐸
- Un camino o trayectoria es una sucesión de aristas distintas que conectan un origen y un destino. Si existe P(v, w)
entonces w es alcanzable desde v
- Longitud de un camino = cantidad de aristas que lo componen
- Ciclo = camino con destino = origen
- Camino simple = no repite vértices
- Grafo conexo = existe un camino entre todo par de vértices
o Si un grafo no es conexo, esta compuesto de componentes conexas
- Un grafo conexo acíclico (sin ciclos) se lo conoce como libre

Implementacion

Siendo N la cant de vértices

 - Matricial
Se utiliza una matriz de adyacencia. Es decir una matriz NxN tal que
𝑐 𝑠𝑖 (𝑖, 𝑗) ∈ 𝐸
𝑎
0 𝑒𝑛 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜
o Si es un grafo c = 1
o Si es un multigrafo c = cantidad de aristas entre (i, j)
o Si es ponderado c = peso de la arista (i, j)
- Listas
Se utiliza un vector de dimensión N. Donde cada elemento es un puntero a una lista. En la lista de posición i se incluyen
los vértices destinos de las aristas que comienzan en i

Recorridos (Grafos)

- Amplitud =
o Se selecciona un nodo inicial. Se visita y se marca como visitado
o Todos los nodos adyacentes no visitados se visitan y se marcan como visitados
o Se visitan los adyacentes no visitados de las ya visitados, en el orden en el que se visitaron
o Se presigue hasta que no haya un nodo sin visitar
A–B–C–D–E–G–F–H–I
- Profundidad
o Se selecciona un nodo inicial. Se visita y se marca como visitado
o Luego se visita un nodo adyacente al inicial y se marca como visitado
o Se prosigue visitando un nodo adyacente al ultimo nodo visitado, en caso de no haber, se va intentando con
los ya visitado en orden inverso
A–B–C–D–G–F–E–H–I
A–B–E–F–G–D–C–H–H

Algoritmos para arboles abarcadores de costo mínimo (AAM)

Un AAM es un árbol que conecta todos los vértices de V, su costo es la suma de las aristas que lo componen

- Kruskal =
o Generar un grafo 𝑇 = (𝑉, ∅)
o Construir componentes conexas cada vez mas grandes, se examinan las aristas de E en orden creciente de
costo. Se agrega la arista si conecta dos vértices que se encuentran en CC diferentes; en caso contrario, se
descarta
 - Prim =
o Asignar un conjunto U de vértices un vertice cualquiera, a partir de el se constituirá el AAM
o Localizar la arista (u, w) con menor costo que conecta un vertice de U con un vertice de V-U, agregar V a U y la
arista al árbol
o Termina cuando V = U

Caminos mas cortos

- Dijkstra (caminos mas corto con un solo origen)

o Se considera S como el conjunto de vértices cuya distancia mas corta desde el origen ya se conoce. D como el
vector en el cual se almacenan las distancias minimas del origen a w. P como el vector camino
o Incluir en S el origen
o Calcular distancias (D[w]) desde el origen a cada uno de los vértices que no se encuentran en S
o Elegir w tal que D[w] es el mínimo y agregarlo a S
o Repetir hasta que S incluya todos los vértices
 Cada vez que se encuentra una nueva mínima distancia a w, pasando por un nuevo vertice k, y se cambia el
valor de D[w], a su vez se tiene que cambiar el valor de P[w] = k

𝑆 = {1} 𝐷[3] = min(∞, 10 + 50) = 60

1) 𝐷 = [0, 10, ∞, 30, 100] → 10 es el mínimo (vertice 2) → 𝐷[4] = min(30, ∞) = 30
𝑃 = [0, 0, ∞, 0, 0] 𝐷[5] = min(100, ∞) = 100
𝑆 = {1, 2}
𝐷[3] = min(60, 30 + 20) = 50
2) 𝐷 = [0, 10, 60, 30, 100] → 30 es el mínimo (vertice 4) →
𝐷[5] = min(100, 30 + 60) = 90
𝑃 = [0, 0, 2, 0, 0]
𝑆 = {1, 2, 4}
3) 𝐷 = [0, 10, 50, 30, 90] → 50 es el mínimo (vertice 3) → 𝐷[5] = min(90, 50 + 10) = 60
𝑃 = [0, 0, 4, 0, 4]
𝑆 = {1, 2, 3, 4}
4) 𝐷 = [0, 10, 50, 30, 60] → 60 es el mínimo (vertice 5)
𝑃 = [0, 0, 4, 0, 3]
- Floyd = Realiza lo mismo que Dijkstra pero con una matriz de distancias (A), calculando lo mínima de todos entre
todos. Evitamos re calcular minimos cuando k = i o k = j
0 8 5 0 0 0
1) 𝐴 = 3 0 ∞ 𝑦 𝑃 = 0 0 ∞
∞ 2 0 ∞ 0 0
𝐴(2, 3) = min(∞, 3 + 5) = 8
𝑘=1
𝐴(3, 2) = min(2, ∞ + 8) = 2

0 8 5 0 0 0
2) 𝐴 = 3 0 8 𝑦 𝑃 = 0 0 1
∞ 2 0 ∞ 0 0
𝐴(1, 3) = min(5, 8 + 5) = 5
𝑘=2
𝐴(3, 1) = min(∞, 2 + 3) = 5
0 8 5 0 0 0
3) 𝐴 = 3 0 8 𝑦 𝑃 = 0 0 1
5 2 0 2 0 0
𝐴(1, 2) = min(8, 5 + 2) = 7
𝑘=3
𝐴(2, 1) = min(3, 8 + 5) = 3
0 7 5 0 3 0
4) 𝐴 = 3 0 8 𝑦 𝑃 = 0 0 1
5 2 0 2 0 0
- Warshall = Crea una matriz de existencia de caminos entre pares de vertices
PREORDEN

INORDEN

POSTORDEN
KRUSKAL

PRIM
AMPLITUD

PROFUNDIDAD