1. Teoría de Grafos

Un grafo $G=(V,E)$ consiste en:

• Vértices ($V$): Conjunto de nodos o puntos.
• Aristas ($E$): Conjunto de pares de vértices que representan conexiones entre ellos.

Tipos de Grafos

1. Grafo no dirigido: Las aristas no tienen dirección.
   • Ejemplo: Redes de amistad en redes sociales.
2. Grafo dirigido (dígrafo): Las aristas tienen una dirección.
   • Ejemplo: Mapa de rutas de vuelos.
3. Grafo ponderado: Cada arista tiene un peso asociado.
   • Ejemplo: Distancias entre ciudades en un mapa.

Propiedades Importantes

• Grado de un vértice : Número de aristas conectadas a él.
  • En grafos dirigidos, se distingue entre grado de entrada y grado de salida.
• Ciclo : Un camino que comienza y termina en el mismo vértice.
• Conexión : Un grafo es conexo si existe un camino entre cualquier par de vértices.

Casos Especiales

1. Árbol : Un grafo conexo y acíclico.
   • Propiedad clave: Tiene exactamente $n−1$ aristas si tiene $n$ vértices.
2. Grafo completo : Cada par de vértices está conectado por una arista.
3. Grafo bipartito : Los vértices pueden dividirse en dos conjuntos disjuntos, y las aristas solo conectan vértices de diferentes conjuntos.

Ejemplo Ilustrativo
Consideremos un grafo no dirigido con $V=\{A,B,C,D\}$ y $E=\{(A,B),(B,C),(C,D),(D,A)\}$:

• Este grafo es cíclico porque contiene un ciclo ($A→B→C→D→A$).
• Es conexo porque todos los vértices están conectados.

1.2 Métodos de Recorrido de Árboles y Grafos

Recorridos de Árboles : Los árboles son casos especiales de grafos, y sus recorridos son fundamentales en ciencias de la computación.

1. Preorden : Visita el nodo raíz, luego los subárboles izquierdo y derecho.
   • Ejemplo: A,B,D,E,C,F.
2. Inorden : Visita el subárbol izquierdo, luego el nodo raíz, y finalmente el subárbol derecho.
   • Ejemplo: D,B,E,A,F,C.
3. Postorden : Visita los subárboles izquierdo y derecho, luego el nodo raíz.
   • Ejemplo: D,E,B,F,C,A.

Ejemplo Práctico: Dado el siguiente árbol binario

    A
   / \
  B   C
 / \   \
D   E   F

• Preorden : A,B,D,E,C,F.
• Inorden : D,B,E,A,F,C.
• Postorden : D,E,B,F,C,A.

Recorridos de Grafos

1. Búsqueda en Anchura (BFS):
   • Explora todos los vecinos de un vértice antes de avanzar a niveles más profundos.
   • Implementación: Usa una cola.
2. Búsqueda en Profundidad (DFS):
   • Explora tan profundamente como sea posible antes de retroceder.
   • Implementación: Usa una pila o recursión.

Ejemplo de BFS y DFS: Dado el grafo

A -- B -- C
|         |
D -- E -- F

• BFS desde A: A,B,D,C,E,F.
• DFS desde A: A,B,C,F,E,D.

1.3 Modelado de Problemas del Mundo Real

Red de Topología

• Representación: Los dispositivos son vértices, y las conexiones son aristas.
• Aplicación: Enrutamiento de paquetes en redes.

Sistema de Archivos Jerárquico

• Representación: Árbol donde cada nodo representa un archivo o directorio.
• Aplicación: Organización de archivos en sistemas operativos.

Red Social

• Representación: Usuarios como vértices, relaciones como aristas.
• Aplicación: Análisis de comunidades, recomendaciones de amigos.

Ejemplo Práctico: Modelar una red social simple

Alice -- Bob -- Carol
  |       |
David -- Eve

• Pregunta : ¿Cuál es el camino más corto entre Alice y Carol?
• Respuesta : $Alice→Bob→Carol$.