# 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