Estudio de las cotas del número cromático de un grafo usando el espectro de su matriz de adyacencia y la matriz laplaciana normalizada (2024)
La teoría de grafos es una rama de las matemáticas discretas, dedicada al estudio de estructuras compuestas por vértices y aristas que conectan estos vértices. Estas estructuras abstractas sirven para modelar una amplia variedad de sistemas en ciencias de la computación, biología, ingeniería, entre otras, proporcionando un marco poderoso para analizar y resolver problemas complejos relacionados con la conectividad y la optimización. El origen de la teoría de grafos se remonta al siglo XVIII con el famoso problema de los puentes de Königsberg, planteado por Leonhard Euler. Este problema involucraba encontrar un camino que cruzara cada uno de los siete puentes de la ciudad de Königsberg, en Prusia (actualmente Kaliningrado, Rusia), exactamente una vez, regresando al punto de partida. Euler demostró que tal camino no existía, y al hacerlo, no solo resolvió el problema, sino que también sentó las bases de la teoría de grafos al introducir la idea de representar los componentes de un problema como vértices y aristas. Desde entonces, la teoría de grafos ha evolucionado significativamente, expandiéndose para incluir el estudio de como los vértices de un grafo pueden ser organizados, conectados y coloreados de maneras que revelan propiedades subyacentes de los sistemas que modelan.