Teoría de Grafos
La teoría de grafos estudia los grafos —estructuras de vértices unidos por aristas— como modelos matemáticos de relaciones y redes por pares.
Definition
El estudio matemático de los grafos, que son conjuntos de vértices junto con un conjunto de aristas, cada una uniendo un par de vértices, y de las propiedades invariantes bajo la estructura de esas conexiones.
Scope
El área abarca la estructura, propiedades y parámetros de los grafos: conectividad, caminos y ciclos, árboles, planaridad, coloraciones, emparejamientos y flujos, así como cuestiones extremales y probabilísticas sobre cómo las propiedades de los grafos se restringen mutuamente. Es fundamental para las matemáticas discretas y proporciona el lenguaje para las redes en la informática, la investigación operativa y las ciencias naturales y sociales.
Sub-topics
Core questions
- ¿Qué propiedades estructurales se derivan de la conectividad de un grafo, la secuencia de grados o la estructura de ciclos?
- ¿Cuándo se puede dibujar un grafo en el plano sin cruces o colorear con pocos colores?
- ¿Qué tan grande o denso puede ser un grafo sin evitar una subestructura dada?
- ¿Cómo permiten los caminos, emparejamientos y flujos optimizar una red?
Key concepts
- Vértices, aristas y grado
- Conectividad y componentes
- Caminos, ciclos y árboles
- Planaridad
- Coloración de grafos
- Emparejamientos y flujos
Clinical relevance
Los grafos modelan redes de comunicación y transporte, redes de interacción social y biológica, estructuras de circuitos y dependencias, y problemas de programación, lo que convierte a la teoría de grafos en una herramienta fundamental en la informática y la investigación operativa.
History
La teoría de grafos se remonta a la solución de Euler en 1736 del problema de los puentes de Königsberg y maduró en el siglo XX a través de trabajos sobre coloración, conectividad y los métodos probabilísticos y estructurales de Erdos, Tutte y otros.
Key figures
- Leonhard Euler
- William Tutte
- Bela Bollobas
Related topics
Seminal works
- diestel2017
- bollobas1998
Frequently asked questions
- ¿Cuál es la diferencia entre un grafo y una red?
- Un grafo es el objeto matemático abstracto de vértices y aristas; una red generalmente se refiere a un grafo dotado de datos adicionales como pesos, capacidades o direcciones que modelan un sistema real.
- ¿Por qué fue importante el problema de los puentes de Königsberg?
- La demostración de Euler de que ningún recorrido podía cruzar cada uno de los siete puentes exactamente una vez abstrajo el problema a vértices y aristas, fundando la teoría de grafos y la topología.