Teoría de Grafos
La teoría de grafos es el estudio matemático de los grafos, estructuras formadas por vértices (puntos) conectados por aristas (líneas), usadas para modelar redes y relaciones.
Definition
La teoría de grafos estudia diagramas hechos de puntos (vértices) conectados por líneas (aristas), diagramas que modelan todo tipo de redes: conexiones de amigos, mapas de carreteras, internet. Formalmente, un grafo $G = (V, E)$ consiste en un conjunto de vértices $V$ y un conjunto de aristas $E$ de pares de vértices, y puede ser dirigido (las aristas tienen dirección) o no dirigido; los conceptos clave incluyen el grado de un vértice, las componentes conexas, los ciclos, los caminos y los árboles generadores. Más formalmente, $E \subseteq V \times V$ (dirigido) o $E \subseteq \{\{u,v\}: u,v \in V\}$ (no dirigido); la teoría de grafos se interseca con la combinatoria, el álgebra (la teoría espectral de grafos usa los valores propios de la matriz de adyacencia), la topología (encajes de grafos en superficies) y los algoritmos (el isomorfismo de grafos se relaciona con P frente a NP).
Example
Imagina un mapa de ciudades (vértices) conectadas por carreteras (aristas): la teoría de grafos responde preguntas como "¿Cuál es la ruta más corta de la ciudad A a la ciudad B?" Los Siete Puentes de Konigsberg preguntaban si podías cruzar los $7$ puentes exactamente una vez; Euler demostró que era imposible en 1736, fundando la teoría de grafos, mostrando que un grafo tiene un camino Euleriano si y solo si exactamente $0$ o $2$ vértices tienen grado impar. El Teorema de los Cuatro Colores, que todo grafo planar puede colorearse con $4$ colores de modo que ningún par de vértices adyacentes comparta color, fue demostrado en 1976 por Appel y Haken usando verificación computacional de $1{,}936$ casos.
Key Insight
Cada vez que las cosas están conectadas, la teoría de grafos se aplica: las redes sociales, las placas de circuitos, las rutas de vuelo y los árboles genealógicos son todos grafos, y la solución de Euler al problema de los Puentes introdujo el recorrido de grafos, que hoy sustenta la navegación GPS, el rastreo web y el enrutamiento de redes. La teoría espectral de grafos usa los valores propios del Laplaciano para estudiar la conectividad, la difusión y las caminatas aleatorias en grafos, con aplicaciones en el aprendizaje automático (redes neuronales de grafos).