En esencia, la teoría de grafos trata sobre el estudio de objetos (vértices) que comparten relaciones (bordes) con otros objetos.
Sé que esto suena increíblemente simple, pero lo distingue como un campo de otros, como la teoría de números (donde el foco primario está contando) y la geometría (donde el foco primario es el espacio).
Debido a que se trata de objetos y relaciones, es increíblemente útil para problemas del mundo real que se refieren a objetos relacionados. Las aplicaciones prácticas incluyen:
- Informática teórica: ¿cómo empiezo a resolver el problema P = NP?
- ¿Qué haría como programador (específicamente un ingeniero de software) que implicaría un conocimiento matemático sólido?
- ¿Por qué las máquinas de Turing son un equivalente teórico tan prolífico de lo que puede hacer una computadora real?
- ¿Cómo se puede aplicar la lógica modal a las matemáticas?
- ¿Qué pasaría si todos olvidaran cómo codificar en un instante?
- Química: los objetos son átomos, las relaciones son enlaces.
- Redes sociales: los objetos son personas, las relaciones son (irónicamente) relaciones.
- Estudio científico: los objetos son papeles, las relaciones son citas.
- Circuitos eléctricos: los objetos son resistencias, condensadores, inductores, las relaciones son cables físicos.
- Aprendizaje automático / búsqueda: los objetos son teorías que explican fenómenos, las relaciones son modificaciones o derivaciones de esas teorías.
- Internet: los objetos son computadoras, las relaciones son conexiones de datos.
En todas estas disciplinas, nos encontramos haciendo el mismo conjunto de preguntas, en dos categorías generales:
- ¿Cuál es la relación entre dos o más nodos en el gráfico (ruta más corta, conectividad, vendedor ambulante, etc.)?
- ¿Cuáles son las propiedades del gráfico en su conjunto (árbol de expansión mínimo, presencia de ciclo, grado, camarillas, grados de separación)
Lo sorprendente es que resolver un problema en un área beneficia a todos los campos que dependen de él.
La aplicación teórica / matemática es que la teoría de grafos es isomorfa a los problemas en otros dominios de las matemáticas y, por lo tanto, es muy valiosa como una forma de probar propiedades. Por ejemplo, si alguien demostrara que existe una solución de tiempo polinomial para el problema del vendedor ambulante, entonces tenemos una solución para todos los problemas de tiempo no polinomiales.
