# Resumen de Teoría de Árboles
**Aclaración: Las demostraciones fueron omitidas, se encuentran en los apuntes de Paula Zabala.**
## Indice
[TOC]
### Definiciones Básicas
- **Árbol:** Un árbol es un grafo conexo sin circuitos simples.
### Propiedades y Teoremas
- **Teorema 1:** Un grafo $G = (V, X)$ es un árbol si y solo si:
1. G es conexo y no contiene circuitos simples.
2. Existe exactamente un camino simple entre todo par de vértices.
3. Cada arista de G es un puente.
- **Lema 1:** La unión de dos caminos simples distintos entre dos vértices contiene un circuito simple.
- **Lema 2:** Una arista $e \in X$ es puente si y solo si no pertenece a un circuito simple de $G$.
### Características de Árboles
- **Hoja:** Un vértice de grado 1 en un árbol.
- **Lema 3:** Todo árbol no trivial tiene al menos dos hojas.
- **Lema 4:** Si $G = (V, X)$ es un árbol, entonces el número de aristas $m = n - 1$.
- siendo $m$ = `#aristas`
- y siendo $n$ = `#vertices`
### Árboles Generadores
- **Definición de Árbol Generador (AG):** Un subgrafo generador (que tiene el mismo conjunto de vértices) de $G$ que es árbol.
- **Teorema 2:** Un grafo $G$ es un árbol si y solo si es conexo y $m = n - 1$.
- **Geodésico:** Un camino geodésico en un grafo es el camino más corto entre dos vértices. Este concepto es fundamental al considerar árboles generadores, pues ellos buscan mantener la mínima distancia entre los vértices.
- **Un árbol generador de un grafo**, es un subgrafo que es un árbol e incluye todos los vertices del grafo original. **La clave de un árbol generador es que no debe incluir a todos los bordes del grafo original**, **pero sí debe conectar todos los vértices de manera que no haya ciclos**, manteniendo la minima cantidad de bordes necesaria para que el grafo original siga siendo conectado.
- Grafo: Árbol sin ciclos.
- Conecta todos los vertices: Todos los vértices están incluidos en el árbol generador y hay un camino entre cualquier par de vértices.
- Sin ciclos: Garantiza que hay exactamente un camino simple entre cualquier par de vértices.
- Ejemplo:
- Considera un grafo $G$ con cinco vértices $A,B,C,D,E$ y las siguientes aristas: $AB,AC,BD,BE,CE,DE$
- Un posible árbol generador para este grafo podría incluir las aristas $AB,AC,BD,DE$. Este subconjunto de aristas conecta todos los vértices sin formar ciclos.
```
Grafo original G:
A --- B
| / \
| D E
| /
C--
|
|
E
```
```
Arbol generador T
A --- B
|
| D
| /
C--
```
- En este arbol generador $T$, **todos los vértices están conectados**, **pero las aristas $BE$ y $CE$ no se incluyen para evitar ciclos** y así mantener la estructura de árbol.
### Árboles Enraizados
- **Árbol Enraizado:** Un árbol con un vértice distinguido llamado raíz.
- **Teorema 3:**
1. Un árbol $m$-ario de altura $h$ tiene a lo sumo $m^h$ hojas.
2. Un árbol $m$-ario con $l$ hojas tiene una altura $h \geq \lceil \log_m l \rceil$.
### Árboles Generadores Mínimos
- **Definición:** Un árbol generador de un grafo que minimiza la suma de los pesos de las aristas.
- **Algoritmos para Árboles Generadores Mínimos:**
- **Prim:** Construye un árbol incrementando un conjunto de vértices y aristas seleccionando la arista de menor costo que conecta un vértice dentro del conjunto a uno fuera del conjunto.
- **Kruskal:** Selecciona aristas en orden creciente de peso sin formar ciclos, hasta que se elijan $n-1$ aristas.
### Recorrido de Árboles
- **BFS (Búsqueda en Anchura):** Visita todos los vértices en un nivel antes de pasar al siguiente.
- **DFS (Búsqueda en Profundidad):** Explora cada rama del árbol lo más profundo posible antes de retroceder.
### Propiedades y Teoremas
- Corolario 1: Sea $G = (V, X)$ un grafo sin circuitos simples y $c$ componentes conexas. Entonces $m = n - c$.
- Corolario 2: Sea $G = (V, X)$ un grafo con $c$ componentes conexas. Entonces $m \geq n - c$.
- Teorema: Un grafo $G$ es un árbol si y solo si:
1. G es un grafo sin circuitos simples y $m = n - 1$.
2. G es conexo y $m = n - 1$.
### Árboles Enraizados
- Nivel: La distancia de la raíz a un vértice.
- Altura: El máximo nivel de los vértices.
- Vértices Internos: Vértices que no son hojas ni la raíz.
- Árbol $m$-ario: Todos los vértices internos tienen grado a lo sumo $m+1$ y la raíz a lo sumo $m$.
- Árbol Exactamente $m$-ario: Todos los vértices internos tienen grado $m+1$ y la raíz $m$.
- Árbol Balanceado: Todas las hojas están a nivel $h$ o $h-1$.
- Árbol Balanceado Completo: Todas las hojas están a nivel $h$.
- Relación Padre-Hijo: Dos vértices adyacentes, siendo el padre el de menor nivel.
- Teorema: Si $T$ es un árbol exactamente $m$-ario balanceado no trivial, entonces $h = \lceil \log_m l \rceil$.
### Árboles Generadores
- Teorema:
1. Todo grafo conexo tiene (al menos) un árbol generador.
2. Un grafo conexo $G$ tiene un único árbol generador si y solo si $G$ es un árbol.
3. Sea $T = (V, X_T)$ un AG de $G = (V, X)$ y $e \in X \setminus X_T$. Entonces $T' = T + e - f = (V, X_T \cup \{e\} \setminus \{f\})$, con $f$ una arista del único circuito de $T + e$, $T'$ es árbol generador de $G$.
### Recorrido de Árboles, Grafos o Digrafos
- Algoritmo de Recorrido: Pseudocódigo del algoritmo para recorrer árboles, grafos o digrafos.
- BFS para Calcular Distancia: Modificación del algoritmo BFS para calcular distancias.
- DFS con Más Información: Clasificación de arcos en DFS (tree edges, backward edges, forward edges, cross-edges) y uso de variables adicionales (timer, desde, hasta).
### Aplicaciones con DFS
- Detección de Ciclos: Un grafo (digrafo) tiene un ciclo (ciclo orientado) si y solo si existe un backward edge.
- Sort Topológico: Ordenar los nodos de acuerdo a su valor en el arreglo hasta de mayor a menor.
- Determinar las Componentes Fuertemente Conexas de un Digrafo
- Determinar los Puntos de Corte y las Aristas Puentes de un Grafo
### Tree Edges (Aristas de Árbol)
- Durante el recorrido DFS, cuando se visita un vértice por primera vez, y se explora uno de sus vecinos no visitados, la arista que conecta estos dos vértices se considera una "tree edge"
- Las "tree edges" forman parte del árbol DFS resultante y no crean ciclos.
- **En otras palabras, una "tree edge" es una arista que se utiliza para avanzar en el recorrido DFS y descubrir nuevos vértices**.
- Ejemplo: Si durante un recorrido DFS, se visita el vértice $A$ y luego se explora su vecino no visitado $B$, la arista $(A,B)$ sería una tree edge.
### Backward Edges (Aristas hacia atrás)
- Una "backward edge" es una arista que conecta un vértice con uno de sus ancestros en el arbol DFS.
- Cuando se encuentra una "backward edge" durante el recorrido DFS, indica la presencia de un ciclo en el grafo.
- Las "backward edges" apuntan hacia atrás en el árbol DFS, desde un vértice hacia uno de sus ancestros.
- Ejemplo: Si durante el recorrido DFS se visita el vértice $A$, luego se avanza hacia su vecino $B$, y desde $B$ se encuentra una arista que vuelve al vértice A (que es un ancestro de $B$ en el árbol DFS), esa arista $(B,A)$ sería una "backward edge".
### Diferencias entre "Tree edges" y "Backward edges"
- Las "tree edges" forman parte del árbol DFS y se utilizan para avanzar en el recoddio, mientras que las "backward edges" indican la presencia de ciclos en el grafo y apuntan hacia atrás en el arbol DFS
# Arbol generador minimo
- Supongamos que conectar $n$ puntos tiene un costo.
- Cuando el grafo tiene un costo asociado a las aristas o a los vertices, lo llamamos **grafo pesado**
- Definición 7: SEa $T = (V,X)$ un arbol y $l:X \to \mathbb{R}$ una función que asigna costos a las aristas de $T$. Se define el **costo** de $T$ como $l(T) = \sum_{e \in T} l(e)$.
- Dado un grafo $G = (V,X)$ un **arbol generador minimo** de $G, AGM(G) =T$, es un arbol generador de $G$ de minimo costo, es decir:
- $$l(T)\leq l(T') \ \forall T' \ \text{arbol generador de } G$$
- Dado un grafo pesado en las aristas, $G =(V,X)$ el problema de arbol generador minimo consiste en encontrar un AGM de $G$.
- 
## Grafo ralo vs grafo denso
- Un **grafo ralo** es que tiene relativamente pocas aristas en comparación con el número de vértices.
- Generalmente se considera ralo si el número de aristas es del orden $O(n)$, siendo $n$ el nro de vértices. O sea que para cada vértice está conectado solo con un número reducido de otros vertices.
- un grafo denso tiene un número de aristas que se acerca al maximo posible de aristes entre vertices. Se considera denso si el número de aristas de del orden $O(n^2)$.
- Un grafo con una proporción significativa de las aristas posibles presentes también se considera denso.
## Algoritmo de Prim
- Este algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices del grafo, donde el peso total de todas las aristas en el arból es el minimo posible.
- Encuentra el arbol generador minimo o minimal spanning tree para sus componentes conexas.
- Complejidad con una matriz de adyacencia: $O(|V|^2)$
- Complejidad con un heap binario y una lista de adyacencia: $O(|E| log \ |V|)$
- Complejidad con un heap fibonacci y una lista de adyacencia: $O(|E| + |V| \ log \ |V|)$
- [Video explicativo](https://www.youtube.com/watch?v=cplfcGZmX7I)
- El algoritmo incrementa contiunuamente el tamaño de un árbol, comenzando por un vertice inicial al que se le van agregando sucesivamente vertices cuya distancia a las anteriores es minima.
- Esto significa que en cada paso, las aristas a considerar son aquellas que inciden en vertices que ya pertenecen al arbol
### Invariante de prim
- $T_i$ es un subconjunto de un arbol generador minimo.
- aclaración: Cuando hablamos de $T_i$ nos referimos al subconjunto AGM que fue construido hasta la iteración $i$-esima del algoritmo. $T_i$ es el AGM que in cluye $i$ aristas, $i+1$ vertices.
- Esto garantiza que a medida que se añaden aristas y vértices al conjunto $T_i$, el algoritmo siempre se está moviendo hacia la construcción de un arbol generador minimo. Asegura que el AGM que estamso construyendo es válido.
- $T_i$ es un árbol.
- Al mantener $T_i$ como un árbol en cada paso, el algoritmo evita la creación de ciclos. Los ciclos ne deben de estar en el AGM. Y tienen que ser evitados para mantener el invariante.
- #$T_i= i$
- Esta propiedad indica que en el paso $i$, el arbol $T_i$ tiene exactamente $i$ aristas.
- $T_0 \subset T_1 \subset \dots T_i$
- Esta propiedad de inclusión asegura que estamos construyendo el arbol de manera incremental. Cada árbol $T_{i+1}$ es una extensión de $T_i$ con una arista adicional.
``` Prim (Grafo G)
/* Inicializamos todos los nodos del grafo.
La distancia la ponemos a infinito y el padre de cada nodo a NULL
Encolamos, en una cola de prioridad
donde la prioridad es la distancia,
todas las parejas <nodo, distancia> del grafo*/
por cada u en V[G] hacer
distancia[u] = INFINITO
padre[u] = NULL
Añadir(cola,<u, distancia[u]>)
distancia[u]=0
Actualizar(cola,<u, distancia[u]>)
mientras !esta_vacia(cola) hacer
// OJO: Se entiende por mayor prioridad aquel nodo cuya distancia[u] es menor.
u = extraer_minimo(cola) //devuelve el mínimo y lo elimina de la cola.
por cada v adyacente a 'u' hacer
si ((v ∈ cola) && (distancia[v] > peso(u, v)) entonces
padre[v] = u
distancia[v] = peso(u, v)
Actualizar(cola,<v, distancia[v]>)
```
## Algoritmo de Kruskal
- Busca un subconjunto de aristas que formando un arbol incluyen todos los vertices y donde el valor de la suma de todas las aristas es el arbol minimo (mismo objetivo que prim's).
- Se crea un bosque $B$ (conjunto de arboles), donde a cada vertice del grafo es un arbol separado.
- Se crea un conjunto $C$ que contenga a todas las aristas del grafo.
- Mientras que $C$ no esté vacío:
- eliminar una arista de peso minimo C
- Si esa arista conecta dos arboles diferentes, se añade al bosque, combinando los 2 arboles en un solo arbol.
- CC: se desecha la arista.
- Al terminar el algoritmo, tiene un sol ocomponente, el cual forma un arbol MST.
- [Video explicativo](https://www.youtube.com/watch?v=71UQH7Pr9kU)
- pseudo: TBD
- complejidad: TBD
### Invariante de kruskal
- Tenemos un bosque generador de $i$ aristas que es subgrafo de algún AGM.
- Alternativa: Tenemos un bosque generador de $i$ aristas que es mínimo entre los bosques de $i$ aristas.
## Diferencias y similitudes entre ambos algoritmos:
### Similitudes:
- Objetivo común: buscar MST de un grafo.
- Se aplican sobre grafos ponderados y conexos.
- Ambos son greedy
### Diferencias:
- Enfoque de construcción:
- Kruskal: empieza considerando un bosque de arboles (inicialmente, cada vértice es un arbol individual) y une estos árboles en AGM agregando la arista más ligera disponible que conecte dos arboles diferentes. Utiliza una estructura de datos de conjuntos disjuntos para gestionar y unir los arboles.
- Prim: empieza con un vertice arbitrario y crece el AGM añadiendo en cada paso la arista más ligera que conecta un vertice dentro del arbol con otro fuera de él. Se mantiene un conjunto de vértices que ya están en el AGM y otro de vértices que aun no están incluidos.
- Estructuras de datos utilizadas:
- Kruskal: Generalmente utiliza una estructura de datos de conjuntos disjuntos (Union-Find) para mantener y verificar si dos vértices están en el mismo conjunto, lo cual ayuda a prevenir ciclos.
- Prim: Utiliza generalmente un montículo (heap) para obtener rápidamente la arista de menor peso que conecta el AGM en crecimiento con un vértice no incluido aún.
- Aplicabilidad
- Kruskal: Es más versátil para situaciones donde el grafo inicial no está completamente conectado, ya que puede manejar un bosque de árboles generadores mínimos.
- Prim: Requiere que el grafo de entrada esté conectado desde el inicio porque crece continuamente desde un punto de partida único.
## Definición minimax y maximin
- **Definición de minimax**: Un camino minimax entre dos vértices u y v es el camino que **minimiza el máximo peso de sus aristas** entre todos los caminos que los unen.
- Teorema: Sea $G$ un grafo pesado y $T$ un AGM de $G$. Cualquier camino en $T$ es minimax en $G$
- **O sea, queremos minimizar el peor caso en un conjunto de opciones**.
- También recordar que camino AGM $\Rightarrow$ minimax (demostrado y visto en clase).
- **Definición de maximin**: un camino que entre dos vértices $u$, $v$ es el camino que **maximiza el minimo peso de sus aristas** Entre todos los caminos posibles que los conectan.
- Esto es lo contrario a minimax.
- Minimax enfoca en reducir el impacto de la peor arista en el camino.
- Maximin busca asegurar la "mejor" arista más débil posible
- Ejemplos:
- Supongamos un grafo $G$ con vértices $A,B,C,D$ y aristas entre ellos con lo siguientes pasos:
- $A$ a $B$ : $3$
- $A$ a $C$ : $1$
- $B$ a $C$ : $2$
- $B$ a $D$ : $5$
- $C$ a $D$ : $4$
- Si buscamos un **camino minimax** de $A$ a $D$, necesitamos encontrar el camino que minimice el máximo peso de las aristas utilizadas.
- 
- $A \to^1 C \to^4 D$ : coste 4 $\Rightarrow$ es minimax
- $A \to^3 B \to^2 C \to^4 D$ : coste 4 $\Rightarrow$ es minimax
- $A \to^3 B \to^5 D$ : coste 5 No es minimax!
- Ahora maximin:
- $A \to^1 C \to^4 D$ : coste 1 No es maximin
- $A \to^3 B \to^2 C \to^4 D$ : coste 2 No es maximin
- $A \to^3 B \to^5 D$ : coste 3 $\Rightarrow$ es maximin
## Disjoint Set
- Es una estructura de datos que nos provee las siguientes operaciones eficientemente:
- find-set($u$): Dado un vértice nos dice a qué componente conexa pertenece.
- union($u,v$): une las componentes conexas a las que pertenecen $u$ y $v$
- 
aasdasd