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

Gutiérrez Lizarazo, Francisco JavierGonzález Díaz, Julián Ricardo2025-04-092025-04-092024González Díaz, Julián R. (2024) 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 [Trabajo de grado, Universidad de los Llanos]. Repositorio digital Universidad de los Llanos.https://repositorio.unillanos.edu.co/handle/001/4973La 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.Introducción. -- 1. Marco referencial. -- 1.1. Autovalor y autovector. -- 1.2. Sub-espacio propio. -- 10 1.3. Teoria de grafos. -- 1.4. Matriz hermitiana. -- 1.5. Espectro de un grafo. -- 2. Materiales y métodos. -- 2.1. Metodología. -- 3. Resultados. -- 3.1. Cota superior. -- 22 3.2. Cotas inferiores. -- 24 4. Análisis de resultados. -- 5. Conclusiones. -- 6. Recomendaciones. -- Bibliografía. -- Resumen analítico especializado.41 páginasapplication/pdfspaDerechos reservados- Universidad de los Llanos, 2024Estudio de las cotas del número cromático de un grafo usando el espectro de su matriz de adyacencia y la matriz laplaciana normalizadaTrabajo de grado - PregradoAtribución-NoComercial-SinDerivadas 4.0 Internacional (CC BY-NC-ND 4.0)info:eu-repo/semantics/openAccessTeoría de GrafosNúmero CromáticoMatrizde AdyacenciaMatriz LaplacianaAnálisis EspectralCotas Superior e InferiorTeoria de GrafosNumero CromaticoMatriz de AdyacenciaMatriz laplacianaAnalisis EspectralCotas Superior e InferiorUniversidad de los Llanoshttps://repositorio.unillanos.edu.co/homehttps://repositorio.unillanos.edu.co/homehttp://purl.org/coar/access_right/c_abf2