Coloración de Grafos y su aplicación a la Geografía

Luis Fernando Carrasco-Pilco, Vinicio Edmundo Burgos-Cevallos, Gloria Alejandra Flora Jurado-Liberona, Emily Naomi Nymoen-Bonilla

Resumen


La presente investigación sobre la Coloración de Grafos, establece que cualquier mapa puede ser coloreado únicamente con cuatro colores. Se desarrolla con cuatro de los métodos conocidos en la demostración del Teorema de los Cuatro Colores. Expone una introducción con la historia que hay detrás del teorema, describe los parámetros y nociones con los que se va a desarrollar, se da una explicación de la metodología a seguir para cada algoritmo, permitiendo encontrar la coloración en el mapa del Ecuador, aplicando los métodos de: Coloración Secuencial Básico, de Welsh y Powell, de Matula, Marble e Isaacson y el de Brelaz. Por último, se hace una evaluación mediante una matriz que considera como parámetros de medición: la representación final del mapa, eficacia del teorema, optimización del tiempo de resolución y la facilidad de resolución, concluyendo con la efectividad de los algoritmos de estudio.


Palabras clave


Grafo; algoritmos de coloración; teoría de grafos; teorema de los cuatro colores; mapa del Ecuador.

Texto completo:

PDF HTML

Referencias


Alvarado, Jorge. (2021). Comparación con grafos de programas de pregrado de estudio en informática del Perú. Universidad Nacional Mayor de San Marcos. Lima-Perú. https://doi.org/10.1590/SciELOPreprints.1992

Álvarez Núñez, M. y Parra Muñoz, J. (2013). Teoría de Grafos. Chillán, Chile Universidad de Bio-Bio. Obtenido de: http://repobib.ubiobio.cl/jspui/bitstream/12345679/1953/3

Andrade, C. (2015). Provincias y Capitales del Mapa de Ecuador. Ecuador: NOTICIASEC. Obtenido de:

https://noticiasec.com/provincias-y-capitales-del-mapa-de-ecuador/

Blanco, R. y García, M. (2019). Actividades con grafos para estudiantes con altas capacidades. Universidad de Colombia. Edma 0-6: Educación Matemática en la Infancia, 8(2), pp. 92-108. http://www.edma06.es/index.php/edma0-6/issue/arch

Bombal, Fernando. (2017). Matemática, Lógica y Operadores. La Gran Alianza. XIX Programa de Promoción de la Cultura Científica y Tecnológica Rev.R.Acad.Cienc.Exact.Fís.Nat. Vol. 109, No. 1-2, pp 59-72.

Flores Muñoz, K. (2012). Implementación de una heurística para resolver el problema de coloramiento de grafos aplicado a la planificación de horarios de una institución educativa. Escuela Superior Politécnica del Litoral, Instituto de Ciencias Matemáticas. Guayaquil: ESPOL. Obtenido de Tesis: https://www.dspace.espol. edu.ec/retrieve/100843/D-CD102684.pdf

Iniesto Díaz, A. (2012). Aplicación Integral de Grafos: Coloración. (U. P. Madrid, Ed.) Obtenido de Tesis de Fin de Grado: http://www.dma.fi.upm.es/personal/gre- gorio/grafos/web/iagraph/documents/TFC %20Coloracion.pdf

Iniesto Díaz, A., & Delgado Núñez, J. (2012). Aplicación Integral de Grafos. Coloración y Búsqueda. Obtenido de http://www.dma.fi.upm.es/personal/gregorio/grafos/web/iagraph /coloracion.html

Lazo, J. y León, D. (2020). Análisis comparativo entre los procesos de diseño gráfico tradicional y generativo para la creación de elementos de comunicación visual. Universidad del Azuay. http://dspace.uazuay.edu.ec/handle/datos/9972

Morales Galindo, K. (2016). Matemáticas Discretas. Recuperado el 2020, de 6.1.2 Tipos de Grafos: https: //sites.google.com/site/matematicasmoralesgalindo/6-1-elementos-y-caracteristicas-de-los-grafos/6-1-2tipos-de-grafos-simples-completos-bipartidos-planos-conexos.

Palacios Somohano, D. (2003). Híbrido MST-20pt para la Solución del Problema del Agente Viajero. (U. d. Puebla, Ed.) Obtenido de Tesis profesional: http://catarina.udlap.mx/u−dl−a/tales/doc umentos/lis/palacios−s−d/capitulo2.pdf

Patiño Avedaño, B. y Guillermo Charry, Ó. (2013). La enseñanza de la Teoría de Grafos como estrategia para desarrollar procesos de matematización. (U. S. Arboleda, Ed.) Obtenido de Tesis de Maestría: https://repository.usergioarboleda.edu.co/bitstream/handle/11232/844/La%20ense%C3%B1anza

%20de%20la%20teor%C3%ADa%20de%20grafos%20como%20estrategia.%20procesos%20de%20matematizaci%C3%B3n.pdf?sequence = 2& isAllowed=y

Pena Seijas, S. (2017). El Problema de Coloración de Grafos. (U. d. Compostela, Ed.) Obtenido de Tesis de Maestría: http://eamo.usc.es/pub/mte/descargas/ProyectosFinMaster/Proyecto11463.pdf




DOI: https://doi.org/10.23857/pc.v6i9.3125

Enlaces de Referencia

  • Por el momento, no existen enlaces de referencia
';

Bookmark and Share




Polo del Conocimiento              

Revista Científico-Académica Multidisciplinaria

ISSN: 2550-682X

Casa Editora del Polo                                                 

Manta - Ecuador       

Dirección: Ciudadela El Palmar, II Etapa,  Manta - Manabí - Ecuador.

Código Postal: 130801

Teléfonos: 056051775/0991871420

Email: polodelconocimientorevista@gmail.com / director@polodelconocimiento.com

URL: https://www.polodelconocimiento.com/