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
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...
- Autores:
-
González Díaz, Julián Ricardo
- Tipo de recurso:
- Trabajo de grado de pregrado
- Fecha de publicación:
- 2024
- Institución:
- Universidad de los Llanos
- Repositorio:
- Repositorio Digital Universidad de los LLanos
- Idioma:
- spa
- OAI Identifier:
- oai:repositorio.unillanos.edu.co:001/4973
- Acceso en línea:
- https://repositorio.unillanos.edu.co/handle/001/4973
https://repositorio.unillanos.edu.co/home
- Palabra clave:
- Teoría de Grafos
Número Cromático
Matrizde Adyacencia
Matriz Laplaciana
Análisis Espectral
Cotas Superior e Inferior
Teoria de Grafos
Numero Cromatico
Matriz de Adyacencia
Matriz laplaciana
Analisis Espectral
Cotas Superior e Inferior
- Rights
- openAccess
- License
- Derechos reservados- Universidad de los Llanos, 2024
| id |
Unillanos2_13c2b7faf7dcaeced529bf5294df8cf1 |
|---|---|
| oai_identifier_str |
oai:repositorio.unillanos.edu.co:001/4973 |
| network_acronym_str |
Unillanos2 |
| network_name_str |
Repositorio Digital Universidad de los LLanos |
| repository_id_str |
|
| dc.title.spa.fl_str_mv |
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 |
| title |
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 |
| spellingShingle |
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 Teoría de Grafos Número Cromático Matrizde Adyacencia Matriz Laplaciana Análisis Espectral Cotas Superior e Inferior Teoria de Grafos Numero Cromatico Matriz de Adyacencia Matriz laplaciana Analisis Espectral Cotas Superior e Inferior |
| title_short |
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 |
| title_full |
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 |
| title_fullStr |
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 |
| title_full_unstemmed |
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 |
| title_sort |
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 |
| dc.creator.fl_str_mv |
González Díaz, Julián Ricardo |
| dc.contributor.advisor.none.fl_str_mv |
Gutiérrez Lizarazo, Francisco Javier |
| dc.contributor.author.none.fl_str_mv |
González Díaz, Julián Ricardo |
| dc.contributor.jury.none.fl_str_mv |
María Cristina Ordoñez Castro Galvis, Arturo Alexander |
| dc.subject.armarc.none.fl_str_mv |
Teoría de Grafos Número Cromático Matrizde Adyacencia Matriz Laplaciana Análisis Espectral Cotas Superior e Inferior |
| topic |
Teoría de Grafos Número Cromático Matrizde Adyacencia Matriz Laplaciana Análisis Espectral Cotas Superior e Inferior Teoria de Grafos Numero Cromatico Matriz de Adyacencia Matriz laplaciana Analisis Espectral Cotas Superior e Inferior |
| dc.subject.proposal.spa.fl_str_mv |
Teoria de Grafos Numero Cromatico Matriz de Adyacencia Matriz laplaciana Analisis Espectral Cotas Superior e Inferior |
| description |
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. |
| publishDate |
2024 |
| dc.date.issued.none.fl_str_mv |
2024 |
| dc.date.accessioned.none.fl_str_mv |
2025-04-09T17:12:00Z |
| dc.date.available.none.fl_str_mv |
2025-04-09T17:12:00Z |
| dc.type.none.fl_str_mv |
Trabajo de grado - Pregrado |
| dc.type.driver.none.fl_str_mv |
info:eu-repo/semantics/bachelorThesis |
| dc.type.version.none.fl_str_mv |
info:eu-repo/semantics/publishedVersion |
| dc.type.coar.none.fl_str_mv |
http://purl.org/coar/resource_type/c_7a1f |
| dc.type.content.none.fl_str_mv |
Text |
| dc.type.coarversion.none.fl_str_mv |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
| dc.type.category.none.fl_str_mv |
Proyectos de investigación |
| format |
http://purl.org/coar/resource_type/c_7a1f |
| status_str |
publishedVersion |
| dc.identifier.citation.none.fl_str_mv |
Gonzá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. |
| dc.identifier.uri.none.fl_str_mv |
https://repositorio.unillanos.edu.co/handle/001/4973 |
| dc.identifier.instname.none.fl_str_mv |
Universidad de los Llanos |
| dc.identifier.reponame.none.fl_str_mv |
https://repositorio.unillanos.edu.co/home |
| dc.identifier.repourl.none.fl_str_mv |
https://repositorio.unillanos.edu.co/home |
| identifier_str_mv |
Gonzá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. Universidad de los Llanos |
| url |
https://repositorio.unillanos.edu.co/handle/001/4973 https://repositorio.unillanos.edu.co/home |
| dc.language.iso.none.fl_str_mv |
spa |
| language |
spa |
| dc.relation.references.none.fl_str_mv |
Apkarian, N (2009) Spectral Bounds on the Chromatic Number.. Cvetkovic, D, Rowlinson, P., & Simi ´ c, S. (2009) ´ An introduction to the theory of graph spectra.. Londres. Cambridge University Press Dong, F, Koh, K. M, & Teo, K. L. (2005) Chromatic polynomials and chromaticity of graphs. World Scientific. Goodaire, E. G., & Parmenter, M. M. (2001). Discrete mathematics with graph theory Prentice Hall. PTR. Hoffman, K., Kunze, R., & Finsterbusch, H. E. (1973). Algebra lineal ´ . Prentice-Hall Hispanoamericana Jung, E. (2020). A New Lower Bound on the Chromatic Number of a Graph. Portland State University Spielman, D. A. (2019). Spectral and algebraic graph theory, 2019. http://cs-www. cs. yale. edu/homes/spielman/sagt. Version dated December, 19. Spielman, D. (2012). Spectral graph theory. Combinatorial scientific computing, 18, 18. Stanley, I & Grossman,S. M. (2012). Algebra lineal ´ .McGRAW-HILL INTERAMERICANA EDITORES, S.A, DE C.V |
| dc.rights.spa.fl_str_mv |
Derechos reservados- Universidad de los Llanos, 2024 |
| dc.rights.uri.none.fl_str_mv |
https://creativecommons.org/licenses/by-nc-nd/4.0/ |
| dc.rights.license.none.fl_str_mv |
Atribución-NoComercial-SinDerivadas 4.0 Internacional (CC BY-NC-ND 4.0) |
| dc.rights.accessrights.none.fl_str_mv |
info:eu-repo/semantics/openAccess |
| dc.rights.coar.none.fl_str_mv |
http://purl.org/coar/access_right/c_abf2 |
| rights_invalid_str_mv |
Derechos reservados- Universidad de los Llanos, 2024 https://creativecommons.org/licenses/by-nc-nd/4.0/ Atribución-NoComercial-SinDerivadas 4.0 Internacional (CC BY-NC-ND 4.0) http://purl.org/coar/access_right/c_abf2 |
| eu_rights_str_mv |
openAccess |
| dc.format.extent.none.fl_str_mv |
41 páginas |
| dc.format.mimetype.none.fl_str_mv |
application/pdf |
| dc.publisher.none.fl_str_mv |
Universidad de los Llanos |
| dc.publisher.faculty.none.fl_str_mv |
Facultad de Ciencias Humanas y de la Educación |
| dc.publisher.place.none.fl_str_mv |
Villavicencio- Meta |
| dc.publisher.program.none.fl_str_mv |
Licenciatura en Matemáticas |
| dc.publisher.branch.none.fl_str_mv |
Sede Barcelona |
| publisher.none.fl_str_mv |
Universidad de los Llanos |
| institution |
Universidad de los Llanos |
| bitstream.url.fl_str_mv |
https://repositorio.unillanos.edu.co/bitstreams/1918ddc5-5716-417a-b229-732fe88b4889/download https://repositorio.unillanos.edu.co/bitstreams/e7cac0be-b1aa-4366-938f-53bf31996332/download https://repositorio.unillanos.edu.co/bitstreams/8d6a7f46-9b37-4a4b-a54c-27eed33a21b4/download https://repositorio.unillanos.edu.co/bitstreams/78e71a4b-e758-446b-8f55-6e278c247896/download https://repositorio.unillanos.edu.co/bitstreams/be0c9e73-ac07-4b4b-b4c8-9f211edd9f9c/download https://repositorio.unillanos.edu.co/bitstreams/8f0014e9-68af-4088-9c66-e1efd9aeece7/download https://repositorio.unillanos.edu.co/bitstreams/41bbea0e-b840-400c-b200-20b4048beb89/download |
| bitstream.checksum.fl_str_mv |
db42aa70e6ecb08851bf57616391e2ac 7da6e34a2b7a0a1e0770a786b588b629 aecd7ec32de9f8e12aeeb7fbd344310f 4307042448992a32155873ffdaa4f6a9 fa52d5b54cfa98fb6263b1e7c0c79451 2d07e5c8ecc1ff67bcf66f536ac375b6 5f88005b1db17b1a45ddaa27e19e55c7 |
| bitstream.checksumAlgorithm.fl_str_mv |
MD5 MD5 MD5 MD5 MD5 MD5 MD5 |
| repository.name.fl_str_mv |
Repositorio Universidad de Los Llanos |
| repository.mail.fl_str_mv |
repositorio@unillanos.edu.co |
| _version_ |
1851059080001486848 |
| spelling |
Gutiérrez Lizarazo, Francisco Javiervirtual::553-1González Díaz, Julián RicardoMaría Cristina OrdoñezCastro Galvis, Arturo Alexandervirtual::554-12025-04-09T17:12:00Z2025-04-09T17:12:00Z2024Gonzá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/4973Universidad de los Llanoshttps://repositorio.unillanos.edu.co/homehttps://repositorio.unillanos.edu.co/homeLa 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.Informe final de trabajo de grado como requisito para optar por el título de Licenciado en Matemáticas.PregradoLicenciado(a) en Matemáticas41 páginasapplication/pdfspaUniversidad de los LlanosFacultad de Ciencias Humanas y de la EducaciónVillavicencio- MetaLicenciatura en MatemáticasSede BarcelonaDerechos reservados- Universidad de los Llanos, 2024https://creativecommons.org/licenses/by-nc-nd/4.0/Atribución-NoComercial-SinDerivadas 4.0 Internacional (CC BY-NC-ND 4.0)info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Estudio 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 - Pregradoinfo:eu-repo/semantics/bachelorThesisinfo:eu-repo/semantics/publishedVersionhttp://purl.org/coar/resource_type/c_7a1fTexthttp://purl.org/coar/version/c_970fb48d4fbd8a85Proyectos de investigaciónApkarian, N (2009) Spectral Bounds on the Chromatic Number..Cvetkovic, D, Rowlinson, P., & Simi ´ c, S. (2009) ´ An introduction to the theory of graph spectra.. Londres. Cambridge University PressDong, F, Koh, K. M, & Teo, K. L. (2005) Chromatic polynomials and chromaticity of graphs. World Scientific.Goodaire, E. G., & Parmenter, M. M. (2001). Discrete mathematics with graph theory Prentice Hall. PTR.Hoffman, K., Kunze, R., & Finsterbusch, H. E. (1973). Algebra lineal ´ . Prentice-Hall HispanoamericanaJung, E. (2020). A New Lower Bound on the Chromatic Number of a Graph. Portland State UniversitySpielman, D. A. (2019). Spectral and algebraic graph theory, 2019. http://cs-www. cs. yale. edu/homes/spielman/sagt. Version dated December, 19.Spielman, D. (2012). Spectral graph theory. Combinatorial scientific computing, 18, 18.Stanley, I & Grossman,S. M. (2012). Algebra lineal ´ .McGRAW-HILL INTERAMERICANA EDITORES, S.A, DE C.VTeoría de GrafosNúmero CromáticoMatrizde AdyacenciaMatriz LaplacianaAnálisis EspectralCotas Superior e InferiorTeoria de GrafosNumero CromaticoMatriz de AdyacenciaMatriz laplacianaAnalisis EspectralCotas Superior e InferiorPublicationhttps://scholar.google.com/citations?hl=es&user=cI_2vDwAAAAJvirtual::553-1https://scholar.google.com/citations?hl=es&user=ZbahyxUAAAAJvirtual::554-10000-0001-5692-4016virtual::553-10000-0002-6807-7691virtual::554-1https://scienti.minciencias.gov.co/cvlac/visualizador/generarCurriculoCv.do?cod_rh=0000887331virtual::553-1https://scienti.minciencias.gov.co/cvlac/visualizador/generarCurriculoCv.do?cod_rh=0000371661virtual::554-10014cb6d-c7e2-4184-9cb1-3224c7729a88virtual::553-10014cb6d-c7e2-4184-9cb1-3224c7729a88virtual::553-18a12e381-2d4d-4ac5-8c96-75b82479387dvirtual::554-18a12e381-2d4d-4ac5-8c96-75b82479387dvirtual::554-1LICENSElicense.txtlicense.txttext/plain; charset=utf-8402https://repositorio.unillanos.edu.co/bitstreams/1918ddc5-5716-417a-b229-732fe88b4889/downloaddb42aa70e6ecb08851bf57616391e2acMD53ORIGINALTrabajo de gradoTrabajo de gradoapplication/pdf272442https://repositorio.unillanos.edu.co/bitstreams/e7cac0be-b1aa-4366-938f-53bf31996332/download7da6e34a2b7a0a1e0770a786b588b629MD51Carta autorizaciónCarta autorizaciónapplication/pdf180329https://repositorio.unillanos.edu.co/bitstreams/8d6a7f46-9b37-4a4b-a54c-27eed33a21b4/downloadaecd7ec32de9f8e12aeeb7fbd344310fMD52TEXTTrabajo de grado.txtTrabajo de grado.txtExtracted texttext/plain49065https://repositorio.unillanos.edu.co/bitstreams/78e71a4b-e758-446b-8f55-6e278c247896/download4307042448992a32155873ffdaa4f6a9MD54Carta autorización.txtCarta autorización.txtExtracted texttext/plain4042https://repositorio.unillanos.edu.co/bitstreams/be0c9e73-ac07-4b4b-b4c8-9f211edd9f9c/downloadfa52d5b54cfa98fb6263b1e7c0c79451MD56THUMBNAILTrabajo de grado.jpgTrabajo de grado.jpgGenerated Thumbnailimage/jpeg5940https://repositorio.unillanos.edu.co/bitstreams/8f0014e9-68af-4088-9c66-e1efd9aeece7/download2d07e5c8ecc1ff67bcf66f536ac375b6MD55Carta autorización.jpgCarta autorización.jpgGenerated Thumbnailimage/jpeg16529https://repositorio.unillanos.edu.co/bitstreams/41bbea0e-b840-400c-b200-20b4048beb89/download5f88005b1db17b1a45ddaa27e19e55c7MD57001/4973oai:repositorio.unillanos.edu.co:001/49732025-04-10 04:01:47.907https://creativecommons.org/licenses/by-nc-nd/4.0/Derechos reservados- Universidad de los Llanos, 2024open.accesshttps://repositorio.unillanos.edu.coRepositorio Universidad de Los Llanosrepositorio@unillanos.edu.coPGEgcmVsPSJsaWNlbnNlIiBocmVmPSJodHRwOi8vY3JlYXRpdmVjb21tb25zLm9yZy9saWNlbnNlcy9ieS1uYy1zYS80LjAvIj48aW1nIGFsdD0iTGljZW5jaWEgZGUgQ3JlYXRpdmUgQ29tbW9ucyIgc3R5bGU9ImJvcmRlci13aWR0aDowIiBzcmM9Imh0dHBzOi8vaS5jcmVhdGl2ZWNvbW1vbnMub3JnL2wvYnktbmMtc2EvNC4wLzg4eDMxLnBuZyIgLz48L2E+PGJyIC8+RXN0ZSBvYnJhIGVzdMOhIGJham8gdW5hIDxhIHJlbD0ibGljZW5zZSIgaHJlZj0iaHR0cDovL2NyZWF0aXZlY29tbW9ucy5vcmcvbGljZW5zZXMvYnktbmMtc2EvNC4wLyI+bGljZW5jaWEgZGUgQ3JlYXRpdmUgQ29tbW9ucyBSZWNvbm9jaW1pZW50by1Ob0NvbWVyY2lhbC1Db21wYXJ0aXJJZ3VhbCA0LjAgSW50ZXJuYWNpb25hbDwvYT4u |