������������������������������������������������������������������������������������������������������������������������������������������������������������

���������������������������������������������������������������������������������

 

Coloraci�n de Grafos y su aplicaci�n a la Geograf�a

Graph coloring and its application to Geography

Luis Fernando Carrasco-Pilco I f.carrasco@colegiorudolfsteiner.edu.ec https://orcid.org/0000-0002-7389-774X

Colora��o gr�fica e sua aplica��o � Geografia

 

 

 

 

 

 

 

 

 

����������� Correspondencia: f.carrasco@colegiorudolfsteiner.edu.ec

Ciencias de la Educaci�n

Art�culo de revisi�n

*Recibido: 25 de julio de 2021 *Aceptado: 30 de Agosto de 2021 * Publicado: 09 de septiembre de 2021

 

I.                    Ingeniero Mec�nico-Mag�ster en Ense�anza de la Matem�tica MEDMAT, Docente de Matem�ticas An�lisis y Enfoques Colegio Internacional Rudolf Steiner, Examinador de Matem�ticas para el Bachillerato Internacional, Quito, Ecuador.�

II.                  Ingeniero Qu�mico-Magister en Educaci�n, menci�n Pedagog�a en entornos digitales, Coordinador �rea de Ciencias del Colegio Internacional Rudolf Steiner, Examinador de F�sica para el Bachillerato Internacional, Quito, Ecuador.

III.               Licenciada en Ciencias de la Educaci�n, Docente de Social Studies, History and Philosophy del Colegio Letort, Quito, Ecuador.

IV.                Estudiante, Investigadora Independiente, Quito, Ecuador.

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.

 

Abstract

The present investigation on the Coloring of Graphs, establishes that any map can be colored only with four colors. It is developed with four of the known methods in the proof of the Four Colors Theorem. It presents an introduction with the history behind the theorem, describes the parameters and notions with which it will be developed, an explanation of the methodology to be followed for each algorithm is given, allowing to find the coloration on the map of Ecuador, applying the methods of: Basic Sequential Staining, Welsh and Powell, Matula, Marble and Isaacson and Brelaz. Finally, an evaluation is made by means of a matrix that considers as measurement parameters: the final representation of the map, efficiency of the theorem, optimization of the resolution time and the ease of resolution, concluding with the effectiveness of the study algorithms.

Keywords: Graph; coloring algorithms; graph theory; theorem of the four colors; map of Ecuador.

 

 

 

 

Resumo

A presente investiga��o sobre Colora��o Gr�fica estabelece que qualquer mapa pode ser colorido com apenas quatro cores. � desenvolvido com quatro dos m�todos conhecidos na prova do Teorema das Quatro Cores. D� uma introdu��o com a hist�ria por detr�s do teorema, descreve os par�metros e no��es com os quais ser� desenvolvido, � dada uma explica��o da metodologia a seguir para cada algoritmo, permitindo encontrar a colora��o no mapa do Equador, aplicando os m�todos de: Colora��o sequencial b�sica, de Gal�s e Powell, de Matula, M�rmore e Isaacson e a de Brelaz. Finalmente, � feita uma avalia��o atrav�s de uma matriz que considera como par�metros de medi��o: a representa��o final do mapa, a efici�ncia do teorema, a optimiza��o do tempo de resolu��o e a facilidade de resolu��o, concluindo com a efic�cia dos algoritmos de estudo.

Palavras-chave: Gr�fico; algoritmos de colora��o; teoria dos gr�ficos; teorema das quatro cores; mapa do Equador.

 

Introducci�n

La presente investigaci�n establece un estudio comparativo sobre algunos de los algoritmos de Coloraci�n de Grafos, actualmente existen varios estudios y aplicaciones sobre el tema, sin embargo, �c�mo sabemos cu�l es la m�s apropiada para colorear grafos en el �rea de la geograf�a? �cu�l resulta m�s r�pido? �y el m�s eficiente? la propuesta mantiene como objetivo general comparar, evaluar y verificar la efectividad de los algoritmos de coloraci�n secuencial b�sico, de Welsh y Powell, de Matula, Marble e Isaacson y el de Brelaz.

La indagaci�n parte en el problema del palomar, investig�ndolo m�s a profundidad, se encuentra con los N�meros de Ramsey, para posteriormente, encontrar informaci�n sobre la Teor�a de Grafos, encontrando el Problema de Coloraci�n de Grafos y el Teorema de los Cuatro Colores.

Este estudio se aborda: primero, la historia y el origen del tema propuesto, adem�s de mencionar el marco te�rico, donde se dan nociones b�sicas que son necesarias de entender antes de poder entrar al desarrollo del estudio. Cabe recalcar que dentro del marco te�rico tambi�n se brindan especificaciones breves sobre el Teorema a comprobar y, de igual manera, sobre el mapa seleccionado. Segundo, en la metodolog�a se explica la teor�a de los cuatro algoritmos propuestos, adem�s de dar razones de la manera y los criterios con los que �stos ser�n evaluados. Tercero, se presenta el desarrollo y resultado de cada uno de los algoritmos, con sus respectivas ilustraciones. Cuarto, se encuentra la evaluaci�n y an�lisis de los mismos. Y, sus conclusiones respectivas.

 

Estado del Arte

En el siglo XVIII, Leonhard Euler plantea el Problema de los siete puentes de K�nigsberg, actualmente, Kaliningrado, este consist�a en encontrar una forma de que, cruzando una sola vez por cada uno de los puentes, se pudiera regresar al punto de partida inicial. La respuesta a dicho problema, resuelto en el a�o 1736, por �l mismo, es que no existe ning�n posible recorrido que cumpla dichas caracter�sticas. En su demostraci�n, represent� cada puente como una l�nea uniendo dos puntos, cada uno de los cuales correspond�a a una zona diferente. Considerado �ste como el primer grafo de la historia.

As�, en 1852, Francis Guthrie, quien fue alumno de de Augustus De Morgan en la University College de Londres, le ense�a a su hermano Frederick, sus avances sobre la coloraci�n de mapas, buscando demostrar, coloreando un mapa de los condados de Inglaterra, que s�lo cuatro colores eran necesarios para asegurar que todos aquellos que se encontraban adyacentes tuvieran colores diferentes, para hac�rselo llegar a De Morgan, quien no pudo ofrecer una respuesta concreta a sus dudas.

Han sido varios los matem�ticos de prestigio quienes trataron de dar una demostraci�n l�gica para la Conjetura de los Cuatro Colores, hasta que, en 1879, Alfred Bray Kempe, abogado de Londres que hab�a estudiado matem�ticas en Cambridge, anuncia en Nature, que encontr� dicha demostraci�n. Ese mismo a�o, Cayley, quien hab�a sido profesor suyo, le sugiere presentar el Teorema obtenido en la revista American Journal of Mathematics.

Sin embargo, en 1890, Percy John Heawood publica un contraejemplo a la demostraci�n de Kempe, con lo que el Teorema volv�a a ser considerado Conjetura.

Finalmente, en el a�o 1976, los matem�ticos Kenneth Appel y Wolfgang Haken demostraron que no puede existir ninguna configuraci�n en un contraejemplo m�nimo del Teorema de los Cuatro Colores. Su demostraci�n fue basada en la reducci�n de configuraciones, haciendo uso de las Cadenas de Kempe, lograron reducir el n�mero de configuraciones del conjunto inevitable a 1936, que fueron comprobados individualmente con ayuda del ordenador. Es as� como �ste se convierte en el primer teorema cuya demostraci�n se realiz� con la ayuda de la tecnolog�a sin haber podido ser verificada por otros pensadores matem�ticos.

 

Marco Te�rico

Este tema en particular ha permitido y brindado a la comunidad matem�tica distintos modelos y formas de solucionar varios problemas de una manera eficiente. As� surgen diversas cuestiones, subtemas, ramas de la Teor�a de Grafos, un ejemplo de ello son los N�meros de Ramsey, la Coloraci�n de Grafos, entre otros.

En el presente estudio, se trabajar� sobre la Coloraci�n de Grafos, de �ste se derivan problemas en todas las �reas posibles, en la historia, en la pedagog�a, manufactura, transporte y dem�s. Se desarrollar� el tema aplicado al �rea de la Geograf�a, espec�ficamente en la Coloraci�n de mapas.

Para empezar, �qu� es la Coloraci�n de Grafos? Es una rama de la Teor�a de Grafos, cuyo objetivo principal es asignar colores, n�meros enteros e incluso letras, a los v�rtices de un grafo, tal manera que no se comparta la misma variable entre dos v�rtices adyacentes, se lo puede aplicar de igual manera para las aristas o caras de un grafo plano.

Nociones B�sicas

Se presentan una serie de definiciones y conceptos relacionados a la Coloraci�n de Grafos que son necesarios para el entendimiento y la comprensi�n de este trabajo.

V�rtices: Conocidos tambi�n como nodos o nudos, son elementos base para la formaci�n de un grafo. Definidos, en la Teor�a de Grafos, como unidades indivisibles, y sin propiedades distinguidas, a pesar de que pueden tener estructuras adicionales dependiendo de la utilizaci�n del grafo del que son parte. Los v�rtices tienen grados, que se basan en el n�mero de aristas que contienen al v�rtice v. Por ende, si el valor del grado equivale a 0, entonces, se trata de un v�rtice aislado.

∙          Un v�rtice aislado es aquel que no incide en ning�n lado.

∙          Dos v�rtices son adyacentes si existe una arista que los une.

(Iniesto D�az, 2012, p�g. 3); (Palacios Somohano, 2003, p�g. 5); (�lvarez N��ez & Parra Mu�oz, 2013)

Arista: Las aristas son parte de los elementos fundamentales de un grafo. Son identificadas por un par �nico de v�rtices, est�n definidas como las uniones entre los mismos, dependiendo del uso del grafo, �stas denotan relaciones tales como el orden, la herencia, etc.

Entre sus propiedades est�n que no es obligatoria la existencia de una arista entre dos v�rtices, es decir, que la relaci�n entre un par de v�rtices y aristas no tiene porqu� producirse, dependiendo del tipo y uso del grafo. Adem�s, �stas pueden tener asignado un sentido, seg�n el grafo a analizar. (Iniesto D�az, 2012); (Alvarado, J. 2021)

Grafo: Un grafo es un par de conjuntos, G = (V,A), donde V es un conjunto finito no vac�o de elementos llamados v�rtices y A es un conjunto finito de pares no ordenados de v�rtices de V , llamados aristas, ambos relacionados mediante la aplicaci�n T, donde T = V → A.

Esta definici�n corresponde al tema de Recorridos Eulerianos, debido a que existen otras dos clasificaciones: los Circuitos Hamiltonianos y los �rboles, que contienen a� otras dos clasificaciones: los Circuitos Hamiltonianos y los �rboles, que contienen a otro tipo de grafos y definiciones que no se ajustan al tema de an�lisis.

Existen varios tipos de grafos, a continuaci�n, se expondr�n los m�s importantes.

∙          Grafo dirigido: Tambi�n llamado d�grafo, es aquel grafo en el que la relaci�n entre los elementos considera su direcci�n, la relaci�n T no es sim�trica. Se caracterizan porque cada arista tiene una direcci�n asignada, expresada como: a = u → v. Su relaci�n se expresa de la siguiente manera: (u,v) 6= (v,u).

∙          Grafo no dirigido: Son llamados grafos, �ste no contempla direcci�n de sus aristas, su principal caracter�stica es que sus aristas son pares no ordenados de v�rtices, lo que significa que la relaci�n T entre ellos es sim�trica, es decir, en un grafo G = (V,A) entonces, (u,v) = (v,u).

∙          Grafo completo: Un grafo G es completo si cada v�rtice tiene un grado igual a (n −1), siendo n el n�mero de v�rtices que componen el grafo. Adem�s, presentan una arista entre cada par de v�rtices del grafo, es decir que todos los v�rtices son adyacentes. Esto proporciona un conjunto A de � aristas. Siendo m el n�mero de aristas del conjunto A.

∙          Grafo conexo: Decimos que un grafo es conexo si consiste de una sola pieza.

∙          Grafo inconexo: Si consiste de varios pedazos, a los que se les llama componentes.

∙          Grafo regular: Un grafo cuyos v�rtices tienen el mismo grado o valencia.

∙          Mult�grafo: Es aquel grafo en donde dos v�rtices se pueden conectar por m�s de una arista.

∙          Grafo simple: Es aquel que no tiene bucles ni lazos, y tampoco es un mult�grafo.

∙          Grafo trivial: Un grafo vac�o con un �nico v�rtice.

∙          Grafo vac�o: Grafo cuyo conjunto de aristas es vac�o.

∙          Grafo plano: Son aquellos que pueden ser representados en el plano, sin que ning�n par de aristas se corten o se crucen entre s�. (Iniesto D�az, 2012, p�gs. 4, 5); (Palacios Somohano, 2003, p�gs. 5-7); (�lvarez N��ez & Parra Mu�oz, 2013); (Pati�o Aveda�o & Guillermo Charry, 2013, p�g. 47); (Morales Galindo, 2016); (Lazo, J. & Le�n, D. 2020)

Teorema de los Cuatro Colores

El teorema establece, que un mapa plano es coloreable como m�nimo con cuatro colores de tal manera que dos regiones adyacentes no tengan el mismo color. Tambi�n que el n�mero crom�tico de cualquier grafo planar es menor o igual a cuatro, que es lo que se va a buscar demostrar haciendo uso del mapa del territorio ecuatoriano. (Bombal, Fernando. 2017); (Flores Mu�oz, 2012, p. 26); (�lvarez N��ez & Parra Mu�oz, 2013); (Pati�o Aveda�o & Guillermo Charry, 2013, p. 53); (Pena Seijas, 2017, p. 7)

Mapa del Ecuador

Se decidi� probar el teorema en base al mapa pol�tico del Ecuador actual, donde se encuentran incluidas las provincias de Santa Elena y Santo Domingo de los Ts�chilas. En la Ilustraci�n 1[1], se observa la imagen base seleccionada para el estudio pertinente.

 

 

 

Ilustraci�n 1: Mapa Pol�tico Actual del Ecuador�����

Fuente: Andrade Christian, 2015

Para que el grafo pueda ser exactamente igual, se van a considerar a las capitales de todas las provincias como los v�rtices del grafo. Es importante recalcar, que no se va a tomar en cuenta la regi�n insular, correspondiendo a las Islas Gal�pagos, por lo que el n�mero de v�rtices a tratar ser� 23.

 

Metodolog�a

Algoritmos de Coloraci�n

La coloraci�n, como se mencion� anteriormente se dar� en los v�rtices del grafo, se le asignar� a cada v�rtice un color, de tal manera que aquellos que sean adyacentes tengan distintos colores. Toda la informaci�n sobre los algoritmos que ser� presentada a continuaci�n proviene del Trabajo de fin de carrera de Iniesto D�az y Delgado N��ez (2012), tanto de la p�gina web, aplicaci�n y el documento acad�mico.

Algoritmo de Coloraci�n Secuencial B�sico

Este algoritmo parte de una ordenaci�n de los v�rtices, se asigna el m�nimo color posible a los v�rtices siguientes. Por ende, si se quiere colorear un v�rtice (v), una vez asignado num�ricamente los colores, se asigna a (v) el color que no aparece entre los asignados a los v�rtices adyacentes ya coloreados.

Entrada: Una ordenaci�n de los v�rtices de un grafo G

Salida: Una coloraci�n de los v�rtices

Paso 1: Asignar el color 1 al v�rtice (v₁)

Paso 2: Si hemos coloreado v₁,v₂,...,v_k� con j colores, asignamos a v_k +1 el color t donde�� t ≤ j +1 es el mismo color permitido para v_k +1, seg�n los colores ya asignados a sus vecinos.

Algoritmo de Coloraci�n de Welsh y Powell

Algoritmo tambi�n conocido como ��primero el de mayor grado��. Por lo que, en este algoritmo los v�rtices se ordenan de acuerdo a sus grados, de mayor a menor.

Se ordena de forma que d(v₁) ≥ d(v₂)... ≥ d(v_n), donde d(v) representa el grado del v�rtice.

Algoritmo de Coloraci�n de Matula, Marble, Isaacson

Es una variable del algoritmo secuencial b�sico, que tambi�n se la conoce como �� El de menor grado el �ltimo��. En este algoritmo los v�rtices se ordenan en orden inverso. Se elige a (v_n) como el v�rtice de menor grado, luego se elige a v_n−1 como el v�rtice de menor grado en G−{v_n} y as� contin�a, se examinan los v�rtices de menor grado, elimin�ndolos del grafo.

Algoritmo de Coloraci�n de Brelaz

Para este algoritmo se tendr� en consideraci�n, aparte del grado del v�rtice, la suma de los grados de los vecinos de cada v�rtice y los colores que ya han sido asignados a esos v�rtices adyacentes.

Se definir� al grado de color de un v�rtice v como el n�mero de colores usados en los vecinos de (v). El orden depender� del grado y del grado de color.

Entrada: Un grafo G.

Salida: Una coloraci�n de los v�rtices de G.

Paso 1: Ordenar los v�rtices en orden decreciente de grados.

Paso 2: Coloreamos un v�rtice de grado m�ximo con el color 1.

Paso 3: Seleccionamos un v�rtice, a�n sin colorear, con grado de color m�ximo. Si hay varios, elegimos el de grado m�ximo.

Paso 4: Colorear el v�rtice seleccionado en el paso 3 con el menor color posible.

Paso 5: Si todos los v�rtices se han coloreado, FIN. En caso contrario, volver al paso 3. (Iniesto D�az & Delgado N��ez, Aplicaci�n Integral de Grafos: Coloraci�n y B�squeda, 2012); (Iniesto D�az, Aplicaci�n Integral de Grafos: Coloraci�n, 2012).

Criterios a evaluar

Se exponen los criterios esenciales en la efectividad de los algoritmos en base a la informaci�n anterior basados en la presentaci�n final del mapa siendo los siguientes: Eficacia del teorema, Optimizaci�n de tiempo de resoluci�n, Facilidad de resoluci�n.

 

Resultados

Graficaci�n del Mapa

Primeramente, se edit� la Ilustraci�n 1, a�adiendo un 40% de transparencia, un 58% de contraste y se rest� un 7% de brillo con el fin de poder realizar m�s f�cil el grafo manualmente. En la Ilustraci�n 2, se observa el grafo sin digitalizar. Para ello, se imprimi� la imagen base, y se fueron conectando las capitales de cada provincia, que servir�n como v�rtices, con cada una de las provincias vecinas, si exist�a un borde en com�n por m�s min�sculo y m�nimo que fuera, se a�ad�a una arista entre dichas provincias.

Ilustraci�n 2: Graficaci�n Digital del Mapa

 

 

 

 

Fuente: Autores, 2021

La digitalizaci�n del grafo obtenido de manera manual, denominado como Ilustraci�n 3. Con la aplicaci�n de Visio, se trabaj� en la imagen para, con ayuda de la herramienta Elipse, colocar los puntos que representar�an a los v�rtices, y con la herramienta de L�neas, conectando los puntos, teniendo como gu�a la graficaci�n manual realizada previamente.

Ilustraci�n 3: Graficaci�n Manual del Mapa

 

 

 

 

 

Fuente: Autores, 2021

Se puede observar, en la Ilustraci�n 4, el grafo digital obtenido que servir� como base para trabajar, en donde ya se encuentran establecidos los colores a utilizar.

Ilustraci�n 3: Grafo Base

 

 

 

 

Fuente: Autores, 2021

Aplicaci�n de los Algoritmos

Una vez establecido el grafo y los colores a utilizar, se realizar� la aplicaci�n de los distintos m�todos de coloraci�n de v�rtices previamente expuestos.

 

Algoritmo de Coloraci�n Secuencial B�sico

Para este algoritmo, se numeraron los v�rtices sin ning�n orden en espec�fico, como se observa en la Ilustraci�n 5.

Ilustraci�n 5: Grafo en Blanco de Algoritmo de Coloraci�n Secuencial B�sico

 

 

 

 

Fuente: Autores, 2021

Se proceder� a colorear los v�rtices en el orden de los colores a utilizar, planteado en cada una de las ilustraciones. Primero el amarillo, luego el azul, siguiendo con el rojo y finalizando con el color lila.

Teniendo en cuenta que el orden de coloraci�n de los v�rtices es el siguiente:

5; 12; 4; 7; 3; 20; 10; 9; 15; 1; 18; 6; 11; 2; 8; 13; 17; 14; 16; 22; 21; 23; 19

Por ello se puede observar como el v�rtice 5, se pinta de amarillo, debido al orden de colores establecido, el v�rtice 12, que sigue en el orden, al no ser adyacente al v�rtice 5, se lo pinta de amarillo igual. Mientras que, el cuatro, al ser adyacente al 5, debe ser pintado del color que sigue, en este caso, el azul.

El grafo coloreado obtenido, en la Ilustraci�n 6. Muestra los v�rtices 14 y 22 no fueron coloreados, debido a que no se pod�an colorear con los colores propuestos, ya que eran adyacentes a todos ellos, por ello se los mantiene con el color base. Dando por resultado una 5-coloraci�n.

 

 

 

Ilustraci�n 6: Coloraci�n Secuencial B�sico

 

 

 

 

 

Fuente: Autores, 2021

Algoritmo de Coloraci�n de Welsh y Powell

Para este algoritmo, primero se analiza el grado de los v�rtices. En la Ilustraci�n 7, se observa el n�mero de los v�rtices establecido anteriormente.

Por ejemplo, observando la Ilustraci�n 8, est� centrado el v�rtice 1. Se puede observar que �ste tiene 5 aristas, es decir, 5 conexiones con otros v�rtices, por lo que el grado del v�rtice 1, resultar�a en ser 5. Dadas las uniones que comparte con los v�rtices 2, 11, 12, 13 y 14.

Ilustraci�n 7: Grafo para la Coloraci�n Welsh y Powell

Ilustraci�n 8: Explicaci�n Grado de V�rtice

Fuente: Autores, 2021

En la Tabla 1, se evidencian cada uno de los v�rtices y su respectivo grado, mismo que se obtiene al contabilizar las aristas o conexiones que tienen.

 

 

 

Tabla 1: Grados de los v�rtices de la Coloraci�n Welsh y Powell

Fuente: Autores, 2021

Se proceder� a ordenar los v�rtices de mayor a menor con relaci�n al grado, dado a que existen varios v�rtices que contienen el mismo valor del grado, �stos se mantendr�n en orden secuencial, como se muestra, en la Tabla 2. Esto, para determinar el orden en que tendr� la coloraci�n.

Tabla 2: Grados de los v�rtices de la Coloraci�n Welsh y Powell

Fuente: Autores, 2021

Por lo que el orden a colorear corresponder�a al siguiente:

19; 6; 13; 15; 17; 22; 23; 1; 3; 11; 12; 16; 20; 5; 14; 18; 21; 2; 4; 7; 8; 9; 10

En la Ilustraci�n 9, se muestra la 4-coloraci�n obtenida.���

Ilustraci�n 9: Coloraci�n Welsh y Powell.

 

 

 

Fuente: Autores, 2021

Algoritmo de Coloraci�n de Matula, Marble, Isaacson

Para este algoritmo, se utiliz� la misma tabla de grados, expuesta previamente en la Tabla 1. Adem�s, como se evidencia en la Ilustraci�n 10, se mantiene la misma numeraci�n de v�rtices.

Ilustraci�n 10: Grafo para la Coloraci�n Matula, Marble e Isaacson

 

 

 

Fuente: Autores, 2021

Se tabula el orden de los n�meros, como se indica en la Tabla 3, todos aquellos con el mismo grado de v�rtice eran seleccionados, y los n�meros de los v�rtices eran ordenados de manera decreciente. De esta manera, se mantiene el algoritmo del v�rtice con menor grado va al �ltimo, y se hace un seguimiento al algoritmo planteado ordenando de esta manera los v�rtices.

Tabla 3: Grados de los v�rtices de coloraci�n Matula, Marble, Isaacson

Fuente: Autores, 2021

Por lo que el orden correspondiente para esta Coloraci�n es el siguiente:

19; 23; 22; 17; 15; 13; 6; 20; 16; 12; 11; 3; 1; 21; 18; 14; 5; 9; 8; 7; 4; 2; 10

En la Ilustraci�n 11, se muestra la 4-coloraci�n obtenida.

Ilustraci�n 11: Grafo para la Coloraci�n Matula, Marble e Isaacson

 

 

 

Fuente: Autores, 2021

 

Algoritmo de Coloraci�n de Brelaz

Para este algoritmo no va a haber un orden especificado con anterioridad, sino que se ir� ordenando seg�n se vaya desarrollando el grado de color de los v�rtices, sin embargo, como se observa en la Ilustraci�n 12, la numeraci�n de los v�rtices se mantiene.

Como la investigaci�n previa lo plantea, primeramente, se selecciona uno de los v�rtices con grado m�s alto, en este caso se utiliz� el v�rtice 19, y a partir de ello se buscaba los v�rtices que ten�an mayor grado de color, en caso de haber varios, se seleccionaba el que ten�a mayor grado de v�rtice, y en caso de tener el mismo tambi�n, se usaba aquel que ten�a mayor n�mero de v�rtice.

Una vez coloreado el v�rtice 19, se busca el v�rtice que tiene mayor grado de color, al ser el comienzo, todos los v�rtices adyacentes a 19, tienen grado de color 1, mientras que el resto, 0. El grado de color se refiere al n�mero de v�rtices adyacentes a �ste que se encuentren coloreados. Por ello, recurrimos a colorear aquel que tenga mayor grado de v�rtice, en este caso, el v�rtice n�mero 17. Ahora, se buscan aquellos v�rtices cuyo grado de color sea 2, en este caso, los v�rtices 9 y 18, como ambos tienen el mismo grado de color, se analiza el grado del v�rtice, como 18 tiene mayor grado, ese es el siguiente en ser coloreado, despu�s del v�rtice 18, se colorea el v�rtice 9. Y se sigue el mismo procedimiento expuesto anteriormente.

En la Ilustraci�n 13, se muestra de manera general el procedimiento mencionado, con el fin de entender mejor el desarrollo del algoritmo, observando adem�s el orden de coloraci�n en la Tabla 4.

Ilustraci�n 12: Grafo para la Coloraci�n Brelaz

Ilustraci�n 13: Coloraci�n 4 Primeros V�rtices

Fuente: Autores, 2021

 

Tabla 4: Datos utilizados y recolectados para la Coloraci�n Brelaz

Fuente: Autores, 2021

Se puede observar, en la Ilustraci�n 14 que, con este algoritmo, se obtuvo, de igual manera, una 4-coloraci�n.

Ilustraci�n 14: Coloraci�n Brelaz

 

 

 

Fuente: Autores, 2021

En la Ilustraci�n 15[2] , se observa el mapa pol�tico del Ecuador, en blanco para poder colorearlo y en la Ilustraci�n 16, se muestra el mapa del territorio ecuatoriano, coloreado como se obtuvo en la Ilustraci�n 14, previamente visualizada aplicando el algoritmo de coloraci�n de Brelaz.

Fuente: Autores, 2021

An�lisis de resultados

Se realizar� la evaluaci�n de todos los grafos tanto individualmente como en conjunto, para tener una visi�n completa de los resultados del presente estudio. Considerando los criterios establecidos: La presentaci�n final del mapa (C1), Eficacia del teorema (C2), Optimizaci�n de tiempo de resoluci�n (C3) y Facilidad de resoluci�n (C4).

La manera en que ser�n evaluados los grafos ser� mediante una especie de calificaci�n, donde los criterios se evaluar�n con el porcentaje de importancia dentro de la investigaci�n para poder finalizar con un 100% de recomendaci�n de uso del algoritmo, en caso de cumplir todos los par�metros. Cabe recalcar, nuevamente, que estos se plantearon en funci�n a la informaci�n expuesta en el marco te�rico de la presente investigaci�n.

En la Tabla 5, se muestra la matriz de evaluaci�n desarrollada, donde se exponen el resultado esperado, el obtenido y el valor asignado a cada criterio correspondiendo a la evaluaci�n individual. Adem�s, se incluye el promedio de eficacia total de los algoritmos, que corresponde a la evaluaci�n general de los mismos.

 

 

 

Tabla 5: Matriz de Evaluaci�n

Fuente: Autores, 2021

Considerando la evaluaci�n expuesta, los mejores algoritmos resultan ser: el propuesto por De Welsh y Powell y el propuesto por De Matula, Marble sin embargo, todas resultan en un buen promedio de recomendaci�n.

 

 

 

Conclusiones

Se puede concluir indicando que, dentro de la presente investigaci�n la mayor�a de los algoritmos presentados cumplen con los criterios, par�metros y expectativas propuestas.

Se ha podido demostrar la veracidad del Teorema de los Cuatro Colores, debido a que es un tema sumamente interesante y todav�a investigado por las mentes m�s brillantes. Lo que pudo afectar para que no se cumpliera el teorema en el algoritmo Secuencial B�sico pudo haber sido el orden, debido a que no existe un orden espec�fico y puede variar infinitamente.

Sin embargo, mientras disminuye la posibilidad de variabilidad y se sigue un patr�n o conceptos bases, es m�s f�cil que se cumpla el teorema, como es el caso del algoritmo de Brelaz. Debido a la evaluaci�n realizada, se podr�a decir que los mejores algoritmos corresponden al de Walsh y Powell, y la de Matula, Marble e Isaacson por el equilibrio existente entre las variables y criterios.

A pesar de ello, la que considerar�a m�s eficiente, es la Brelaz, debido a que existe un mayor control sobre las variables y, por tanto, se asegura con mayor probabilidad de que la coloraci�n se cumpla a cabalidad.

Para el presente trabajo se determin� que el n�mero crom�tico ser�a 4, debido al objetivo de demostrar el Teorema de los Cuatro Colores. Sin embargo, no se niega el que la coloraci�n pueda ser menor, como m�nimo se alcanzar�a una 3-coloraci�n debido a la cantidad de v�rtices, al estar hablando de 23 v�rtices, resulta complejo determinar que el n�mero crom�tico pueda ser menor. Por lo que, se deja abierto el espacio para un an�lisis pertinente sobre el menor n�mero crom�tico alcanzable con 23 v�rtices. Cabe recalcar que, se necesita de la ayuda tecnol�gica, principalmente debido a las posibles maneras de ordenar los v�rtices, ya que �stas pueden resultar en n�meros infinitos.

Sin embargo, cabe tener en cuenta que se considera este punto, dado a que, dentro de los resultados, se obtuvo una 5-coloraci�n.

 

 

 

 

Referencias Bibliogr�ficas

1.                  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

 

2.                  �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

 

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

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

 

5.                  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

 

6.                  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, N^o. 1-2, pp 59-72.

 

7.                  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

 

8.                  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

 

9.                  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

 

10.              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

 

11.              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.

 

12.              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

 

13.              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

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

 

15.              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/Proyecto₁1463.pdf

 

 

 

����������� � 2021 por los autores. Este art�culo es de acceso abierto y distribuido seg�n los t�rminos y condiciones de la licencia Creative Commons Atribuci�n-NoComercial-CompartirIgual 4.0 Internacional (CC BY-NC-SA 4.0)

(https://creativecommons.org/licenses/by-nc-sa/4.0/).