🧠 Compendio de Teoría de Grafos y Árboles

Matemática Discreta – Ciencias de la Computación (UFM)
Basado en: Grafos 1, Grafos 2 y Árboles (octubre 2025)

🕸️ Teoría de Grafos: El Universo Conectado

Definición Formal de un Grafo

Un grafo G es una tupla ordenada:
G = (V, E) donde:

• V = conjunto de vértices o nodos.
• E = conjunto de aristas que conectan pares de vértices.
• |V| = número de vértices.
• |E| = número de aristas.

Ejemplo:
V = {A, B, C, D}
E = {{A, B}, {A, C}, {C, D}}

Tipos de Grafos

Grado de un Vértice

• deg(v) = número de aristas incidentes a v.
• En digrafos (grafos dirigidos):
  • deg⁺(v) = número de aristas que salen (grado de salida).
  • deg⁻(v) = número de aristas que llegan (grado de entrada).

🧩 Teorema del Apretón de Manos (Handshaking Theorem)

• Cada arista cuenta dos veces (una por cada extremo).
• El número de vértices con grado impar siempre es par.

Propiedades y Aplicaciones

• Grado promedio:
  
• En redes sociales, el grado sirve para medir conectividad, popularidad e influencia.
• Ejemplo en redes dirigidas (Twitter):
  • Influencer → deg⁻ alto, deg⁺ bajo (muchos seguidores, pocos seguidos).
  • Bot → deg⁺ alto, deg⁻ bajo (muchos seguidos, pocos seguidores).

Isomorfismo de Grafos

Dos grafos son isomorfos si tienen la misma estructura, aunque los nombres de los vértices cambien.

Condiciones Necesarias para Isomorfismo:

1. Igual número de vértices y aristas.
2. Igual secuencia de grados.
3. Misma conectividad y número de ciclos.

💬 En palabras simples:

“Una rosa con otro nombre sigue siendo una rosa.”

Conectividad

🔁 Tipos de Recorridos en Grafos

⚙️ Caminos Especiales

Caminos Eulerianos

• Camino euleriano: recorre cada arista una sola vez.
• Circuito euleriano: camino euleriano que empieza y termina en el mismo vértice.

🧠 Teorema de Euler (1736):

1. Un grafo conexo tiene circuito euleriano ⇔ todos los vértices tienen grado par.
2. Tiene camino euleriano (no circuito) ⇔ exactamente dos vértices de grado impar.

📍 Ejemplo histórico: Los Puentes de Königsberg → imposible (4 vértices impares).

Caminos Hamiltonianos

• Camino hamiltoniano: visita cada vértice exactamente una vez.
• Circuito hamiltoniano: camino hamiltoniano cerrado.

🧮 Teorema de Dirac:

Si G tiene n ≥ 3 vértices y deg(v) ≥ n/2 para todo vértice, entonces G tiene un ciclo hamiltoniano.

🔎 Algoritmos de Recorrido

BFS (Breadth-First Search)

• Explora el grafo por niveles (amplitud).
• Utiliza una cola (Queue).
• Encuentra caminos más cortos (en términos de número de aristas).
• Complejidad: O(|V| + |E|)

📘 Usos:

• Distancia mínima entre nodos.
• Broadcasting (difusión).
• Comprobación de bipartición.

DFS (Depth-First Search)

• Explora el grafo en profundidad.
• Utiliza una pila (Stack) o recursión.
• Detecta ciclos y realiza backtracking.
• Complejidad: O(|V| + |E|)

📘 Usos:

• Detección de ciclos.
• Ordenamiento topológico.
• Exploración de laberintos.

🌳 Árboles: Estructura Jerárquica

Definición Formal de un Árbol

Un árbol es un grafo conexo y acíclico que cumple la propiedad fundamental:

|E| = |V| – 1

Generalmente, tiene un nodo raíz y los demás nodos tienen exactamente un padre.

Terminología Clave

Tipos de Árboles Binarios

Propiedad Fundamental de los Árboles

En un árbol con n nodos, el número de aristas es n − 1.

📘 Demostración por inducción:
Remover una hoja y su arco reduce en 1 los nodos y en 1 las aristas. Por lo tanto, la relación se mantiene.

Recorridos de Árboles

Aplicaciones Reales de los Árboles

• Sistemas de archivos (carpetas/subcarpetas).
• Árboles genealógicos y organigramas.
• Árboles de decisión (Machine Learning).
• Índices y estructuras de búsqueda (bases de datos).
• Procesos de sistema operativo y DOM web.

⚡ Fórmulas Clave