Coloracin de Grafos y su aplicacin a la Geografa

Graph coloring and its application to Geography

 
Colorao grfica e sua aplicao Geografia

 

 

 

 

 

 

 

 

 


Correspondencia: f.carrasco@colegiorudolfsteiner.edu.ec

Ciencias de la Educacin

Artculo de revisin

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

 

I.                    Ingeniero Mecnico-Magster en Enseanza de la Matemtica MEDMAT, Docente de Matemticas Anlisis y Enfoques Colegio Internacional Rudolf Steiner, Examinador de Matemticas para el Bachillerato Internacional, Quito, Ecuador.

II.                  Ingeniero Qumico-Magister en Educacin, mencin Pedagoga en entornos digitales, Coordinador rea de Ciencias del Colegio Internacional Rudolf Steiner, Examinador de Fsica para el Bachillerato Internacional, Quito, Ecuador.

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

IV.                Estudiante, Investigadora Independiente, Quito, Ecuador.


Resumen

La presente investigacin sobre la Coloracin de Grafos, establece que cualquier mapa puede ser coloreado nicamente con cuatro colores. Se desarrolla con cuatro de los mtodos conocidos en la demostracin del Teorema de los Cuatro Colores. Expone una introduccin con la historia que hay detrs del teorema, describe los parmetros y nociones con los que se va a desarrollar, se da una explicacin de la metodologa a seguir para cada algoritmo, permitiendo encontrar la coloracin en el mapa del Ecuador, aplicando los mtodos de: Coloracin Secuencial Bsico, de Welsh y Powell, de Matula, Marble e Isaacson y el de Brelaz. Por ltimo, se hace una evaluacin mediante una matriz que considera como parmetros de medicin: la representacin final del mapa, eficacia del teorema, optimizacin del tiempo de resolucin y la facilidad de resolucin, concluyendo con la efectividad de los algoritmos de estudio.

Palabras clave: Grafo; algoritmos de coloracin; teora 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 investigao sobre Colorao Grfica estabelece que qualquer mapa pode ser colorido com apenas quatro cores. desenvolvido com quatro dos mtodos conhecidos na prova do Teorema das Quatro Cores. D uma introduo com a histria por detrs do teorema, descreve os parmetros e noes com os quais ser desenvolvido, dada uma explicao da metodologia a seguir para cada algoritmo, permitindo encontrar a colorao no mapa do Equador, aplicando os mtodos de: Colorao sequencial bsica, de Gals e Powell, de Matula, Mrmore e Isaacson e a de Brelaz. Finalmente, feita uma avaliao atravs de uma matriz que considera como parmetros de medio: a representao final do mapa, a eficincia do teorema, a optimizao do tempo de resoluo e a facilidade de resoluo, concluindo com a eficcia dos algoritmos de estudo.

Palavras-chave: Grfico; algoritmos de colorao; teoria dos grficos; teorema das quatro cores; mapa do Equador.

 

Introduccin

La presente investigacin establece un estudio comparativo sobre algunos de los algoritmos de Coloracin de Grafos, actualmente existen varios estudios y aplicaciones sobre el tema, sin embargo, cmo sabemos cul es la ms apropiada para colorear grafos en el rea de la geografa? cul resulta ms rpido? y el ms eficiente? la propuesta mantiene como objetivo general comparar, evaluar y verificar la efectividad de los algoritmos de coloracin secuencial bsico, de Welsh y Powell, de Matula, Marble e Isaacson y el de Brelaz.

La indagacin parte en el problema del palomar, investigndolo ms a profundidad, se encuentra con los Nmeros de Ramsey, para posteriormente, encontrar informacin sobre la Teora de Grafos, encontrando el Problema de Coloracin de Grafos y el Teorema de los Cuatro Colores.

Este estudio se aborda: primero, la historia y el origen del tema propuesto, adems de mencionar el marco terico, donde se dan nociones bsicas que son necesarias de entender antes de poder entrar al desarrollo del estudio. Cabe recalcar que dentro del marco terico tambin se brindan especificaciones breves sobre el Teorema a comprobar y, de igual manera, sobre el mapa seleccionado. Segundo, en la metodologa se explica la teora de los cuatro algoritmos propuestos, adems de dar razones de la manera y los criterios con los que stos sern evaluados. Tercero, se presenta el desarrollo y resultado de cada uno de los algoritmos, con sus respectivas ilustraciones. Cuarto, se encuentra la evaluacin y anlisis de los mismos. Y, sus conclusiones respectivas.

 

Estado del Arte

En el siglo XVIII, Leonhard Euler plantea el Problema de los siete puentes de Knigsberg, actualmente, Kaliningrado, este consista 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 ao 1736, por l mismo, es que no existe ningn posible recorrido que cumpla dichas caractersticas. En su demostracin, represent cada puente como una lnea uniendo dos puntos, cada uno de los cuales corresponda 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 ensea a su hermano Frederick, sus avances sobre la coloracin de mapas, buscando demostrar, coloreando un mapa de los condados de Inglaterra, que slo cuatro colores eran necesarios para asegurar que todos aquellos que se encontraban adyacentes tuvieran colores diferentes, para hacrselo llegar a De Morgan, quien no pudo ofrecer una respuesta concreta a sus dudas.

Han sido varios los matemticos de prestigio quienes trataron de dar una demostracin lgica para la Conjetura de los Cuatro Colores, hasta que, en 1879, Alfred Bray Kempe, abogado de Londres que haba estudiado matemticas en Cambridge, anuncia en Nature, que encontr dicha demostracin. Ese mismo ao, Cayley, quien haba 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 demostracin de Kempe, con lo que el Teorema volva a ser considerado Conjetura.

Finalmente, en el ao 1976, los matemticos Kenneth Appel y Wolfgang Haken demostraron que no puede existir ninguna configuracin en un contraejemplo mnimo del Teorema de los Cuatro Colores. Su demostracin fue basada en la reduccin de configuraciones, haciendo uso de las Cadenas de Kempe, lograron reducir el nmero 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 demostracin se realiz con la ayuda de la tecnologa sin haber podido ser verificada por otros pensadores matemticos.

 

Marco Terico

Este tema en particular ha permitido y brindado a la comunidad matemtica distintos modelos y formas de solucionar varios problemas de una manera eficiente. As surgen diversas cuestiones, subtemas, ramas de la Teora de Grafos, un ejemplo de ello son los Nmeros de Ramsey, la Coloracin de Grafos, entre otros.

En el presente estudio, se trabajar sobre la Coloracin de Grafos, de ste se derivan problemas en todas las reas posibles, en la historia, en la pedagoga, manufactura, transporte y dems. Se desarrollar el tema aplicado al rea de la Geografa, especficamente en la Coloracin de mapas.

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

Nociones Bsicas

Se presentan una serie de definiciones y conceptos relacionados a la Coloracin de Grafos que son necesarios para el entendimiento y la comprensin de este trabajo.

Vrtices: Conocidos tambin como nodos o nudos, son elementos base para la formacin de un grafo. Definidos, en la Teora de Grafos, como unidades indivisibles, y sin propiedades distinguidas, a pesar de que pueden tener estructuras adicionales dependiendo de la utilizacin del grafo del que son parte. Los vrtices tienen grados, que se basan en el nmero de aristas que contienen al vrtice v. Por ende, si el valor del grado equivale a 0, entonces, se trata de un vrtice aislado.

          Un vrtice aislado es aquel que no incide en ningn lado.

          Dos vrtices son adyacentes si existe una arista que los une.

(Iniesto Daz, 2012, pg. 3); (Palacios Somohano, 2003, pg. 5); (lvarez Nez & Parra Muoz, 2013)

Arista: Las aristas son parte de los elementos fundamentales de un grafo. Son identificadas por un par nico de vrtices, estn 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 estn que no es obligatoria la existencia de una arista entre dos vrtices, es decir, que la relacin entre un par de vrtices y aristas no tiene porqu producirse, dependiendo del tipo y uso del grafo. Adems, stas pueden tener asignado un sentido, segn el grafo a analizar. (Iniesto Daz, 2012); (Alvarado, J. 2021)

Grafo: Un grafo es un par de conjuntos, G = (V,A), donde V es un conjunto finito no vaco de elementos llamados vrtices y A es un conjunto finito de pares no ordenados de vrtices de V , llamados aristas, ambos relacionados mediante la aplicacin T, donde T = V A.

Esta definicin 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 anlisis.

Existen varios tipos de grafos, a continuacin, se expondrn los ms importantes.

          Grafo dirigido: Tambin llamado dgrafo, es aquel grafo en el que la relacin entre los elementos considera su direccin, la relacin T no es simtrica. Se caracterizan porque cada arista tiene una direccin asignada, expresada como: a = u v. Su relacin se expresa de la siguiente manera: (u,v) 6= (v,u).

          Grafo no dirigido: Son llamados grafos, ste no contempla direccin de sus aristas, su principal caracterstica es que sus aristas son pares no ordenados de vrtices, lo que significa que la relacin T entre ellos es simtrica, es decir, en un grafo G = (V,A) entonces, (u,v) = (v,u).

          Grafo completo: Un grafo G es completo si cada vrtice tiene un grado igual a (n −1), siendo n el nmero de vrtices que componen el grafo. Adems, presentan una arista entre cada par de vrtices del grafo, es decir que todos los vrtices son adyacentes. Esto proporciona un conjunto A de aristas. Siendo m el nmero 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 vrtices tienen el mismo grado o valencia.

          Multgrafo: Es aquel grafo en donde dos vrtices se pueden conectar por ms de una arista.

          Grafo simple: Es aquel que no tiene bucles ni lazos, y tampoco es un multgrafo.

          Grafo trivial: Un grafo vaco con un nico vrtice.

          Grafo vaco: Grafo cuyo conjunto de aristas es vaco.

          Grafo plano: Son aquellos que pueden ser representados en el plano, sin que ningn par de aristas se corten o se crucen entre s. (Iniesto Daz, 2012, pgs. 4, 5); (Palacios Somohano, 2003, pgs. 5-7); (lvarez Nez & Parra Muoz, 2013); (Patio Avedao & Guillermo Charry, 2013, pg. 47); (Morales Galindo, 2016); (Lazo, J. & Len, D. 2020)

Teorema de los Cuatro Colores

El teorema establece, que un mapa plano es coloreable como mnimo con cuatro colores de tal manera que dos regiones adyacentes no tengan el mismo color. Tambin que el nmero cromtico 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 Muoz, 2012, p. 26); (lvarez Nez & Parra Muoz, 2013); (Patio Avedao & Guillermo Charry, 2013, p. 53); (Pena Seijas, 2017, p. 7)

Mapa del Ecuador

Se decidi probar el teorema en base al mapa poltico del Ecuador actual, donde se encuentran incluidas las provincias de Santa Elena y Santo Domingo de los Tschilas. En la Ilustracin 1[1], se observa la imagen base seleccionada para el estudio pertinente.

 

 

 

Ilustracin 1: Mapa Poltico 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 vrtices del grafo. Es importante recalcar, que no se va a tomar en cuenta la regin insular, correspondiendo a las Islas Galpagos, por lo que el nmero de vrtices a tratar ser 23.

 

Metodologa

Algoritmos de Coloracin

La coloracin, como se mencion anteriormente se dar en los vrtices del grafo, se le asignar a cada vrtice un color, de tal manera que aquellos que sean adyacentes tengan distintos colores. Toda la informacin sobre los algoritmos que ser presentada a continuacin proviene del Trabajo de fin de carrera de Iniesto Daz y Delgado Nez (2012), tanto de la pgina web, aplicacin y el documento acadmico.

Algoritmo de Coloracin Secuencial Bsico

Este algoritmo parte de una ordenacin de los vrtices, se asigna el mnimo color posible a los vrtices siguientes. Por ende, si se quiere colorear un vrtice (v), una vez asignado numricamente los colores, se asigna a (v) el color que no aparece entre los asignados a los vrtices adyacentes ya coloreados.

Entrada: Una ordenacin de los vrtices de un grafo G

Salida: Una coloracin de los vrtices

Paso 1: Asignar el color 1 al vrtice (v1)

Paso 2: Si hemos coloreado v1,v2,...,vk con j colores, asignamos a vk +1 el color t donde t j +1 es el mismo color permitido para vk +1, segn los colores ya asignados a sus vecinos.

Algoritmo de Coloracin de Welsh y Powell

Algoritmo tambin conocido como primero el de mayor grado. Por lo que, en este algoritmo los vrtices se ordenan de acuerdo a sus grados, de mayor a menor.

Se ordena de forma que d(v1) ≥ d(v2)... ≥ d(vn), donde d(v) representa el grado del vrtice.

Algoritmo de Coloracin de Matula, Marble, Isaacson

Es una variable del algoritmo secuencial bsico, que tambin se la conoce como El de menor grado el ltimo. En este algoritmo los vrtices se ordenan en orden inverso. Se elige a (vn) como el vrtice de menor grado, luego se elige a vn−1 como el vrtice de menor grado en G−{vn} y as contina, se examinan los vrtices de menor grado, eliminndolos del grafo.

Algoritmo de Coloracin de Brelaz

Para este algoritmo se tendr en consideracin, aparte del grado del vrtice, la suma de los grados de los vecinos de cada vrtice y los colores que ya han sido asignados a esos vrtices adyacentes.

Se definir al grado de color de un vrtice v como el nmero de colores usados en los vecinos de (v). El orden depender del grado y del grado de color.

Entrada: Un grafo G.

Salida: Una coloracin de los vrtices de G.

Paso 1: Ordenar los vrtices en orden decreciente de grados.

Paso 2: Coloreamos un vrtice de grado mximo con el color 1.

Paso 3: Seleccionamos un vrtice, an sin colorear, con grado de color mximo. Si hay varios, elegimos el de grado mximo.

Paso 4: Colorear el vrtice seleccionado en el paso 3 con el menor color posible.

Paso 5: Si todos los vrtices se han coloreado, FIN. En caso contrario, volver al paso 3. (Iniesto Daz & Delgado Nez, Aplicacin Integral de Grafos: Coloracin y Bsqueda, 2012); (Iniesto Daz, Aplicacin Integral de Grafos: Coloracin, 2012).

Criterios a evaluar

Se exponen los criterios esenciales en la efectividad de los algoritmos en base a la informacin anterior basados en la presentacin final del mapa siendo los siguientes: Eficacia del teorema, Optimizacin de tiempo de resolucin, Facilidad de resolucin.

 

Resultados

Graficacin del Mapa

Primeramente, se edit la Ilustracin 1, aadiendo un 40% de transparencia, un 58% de contraste y se rest un 7% de brillo con el fin de poder realizar ms fcil el grafo manualmente. En la Ilustracin 2, se observa el grafo sin digitalizar. Para ello, se imprimi la imagen base, y se fueron conectando las capitales de cada provincia, que servirn como vrtices, con cada una de las provincias vecinas, si exista un borde en comn por ms minsculo y mnimo que fuera, se aada una arista entre dichas provincias.

Ilustracin 2: Graficacin Digital del Mapa

 

 

 

 

Fuente: Autores, 2021

La digitalizacin del grafo obtenido de manera manual, denominado como Ilustracin 3. Con la aplicacin de Visio, se trabaj en la imagen para, con ayuda de la herramienta Elipse, colocar los puntos que representaran a los vrtices, y con la herramienta de Lneas, conectando los puntos, teniendo como gua la graficacin manual realizada previamente.

Ilustracin 3: Graficacin Manual del Mapa

 

 

 

 

 

Fuente: Autores, 2021

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

Ilustracin 3: Grafo Base

 

 

 

 

Fuente: Autores, 2021

Aplicacin de los Algoritmos

Una vez establecido el grafo y los colores a utilizar, se realizar la aplicacin de los distintos mtodos de coloracin de vrtices previamente expuestos.

 

Algoritmo de Coloracin Secuencial Bsico

Para este algoritmo, se numeraron los vrtices sin ningn orden en especfico, como se observa en la Ilustracin 5.

Ilustracin 5: Grafo en Blanco de Algoritmo de Coloracin Secuencial Bsico

 

 

 

 

Fuente: Autores, 2021

Se proceder a colorear los vrtices 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 coloracin de los vrtices 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 vrtice 5, se pinta de amarillo, debido al orden de colores establecido, el vrtice 12, que sigue en el orden, al no ser adyacente al vrtice 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 Ilustracin 6. Muestra los vrtices 14 y 22 no fueron coloreados, debido a que no se podan 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-coloracin.

 

 

 

Ilustracin 6: Coloracin Secuencial Bsico

 

 

 

 

 

Fuente: Autores, 2021

Algoritmo de Coloracin de Welsh y Powell

Para este algoritmo, primero se analiza el grado de los vrtices. En la Ilustracin 7, se observa el nmero de los vrtices establecido anteriormente.

Por ejemplo, observando la Ilustracin 8, est centrado el vrtice 1. Se puede observar que ste tiene 5 aristas, es decir, 5 conexiones con otros vrtices, por lo que el grado del vrtice 1, resultara en ser 5. Dadas las uniones que comparte con los vrtices 2, 11, 12, 13 y 14.

Ilustracin 7: Grafo para la Coloracin Welsh y Powell

Ilustracin 8: Explicacin Grado de Vrtice

Fuente: Autores, 2021

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

 

 

 


Tabla 1: Grados de los vrtices de la Coloracin Welsh y Powell

No de vrtices

Grado del Vrtices

1

5

2

3

3

5

4

3

5

4

6

6

7

3

8

3

9

3

10

2

11

5

12

5

13

6

14

4

15

6

16

5

17

6

18

4

19

7

20

5

21

4

22

6

23

6

Fuente: Autores, 2021

Se proceder a ordenar los vrtices de mayor a menor con relacin al grado, dado a que existen varios vrtices que contienen el mismo valor del grado, stos se mantendrn en orden secuencial, como se muestra, en la Tabla 2. Esto, para determinar el orden en que tendr la coloracin.

Tabla 2: Grados de los vrtices de la Coloracin Welsh y Powell

No de vrtices

Grado del Vrtices

19

7

6

6

13

6

15

6

17

6

22

6

23

6

1

5

3

5

11

5

12

5

16

5

20

5

5

4

14

4

18

4

21

4

2

3

4

3

7

3

8

3

9

3

10

2

Fuente: Autores, 2021


Por lo que el orden a colorear correspondera 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 Ilustracin 9, se muestra la 4-coloracin obtenida.

Ilustracin 9: Coloracin Welsh y Powell.

 

 

 

Fuente: Autores, 2021

Algoritmo de Coloracin de Matula, Marble, Isaacson

Para este algoritmo, se utiliz la misma tabla de grados, expuesta previamente en la Tabla 1. Adems, como se evidencia en la Ilustracin 10, se mantiene la misma numeracin de vrtices.

Ilustracin 10: Grafo para la Coloracin Matula, Marble e Isaacson

 

 

 

Fuente: Autores, 2021

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

Tabla 3: Grados de los vrtices de coloracin Matula, Marble, Isaacson

No de vrtices

Grado del Vrtices

19

7

23

6

22

6

17

6

15

6

13

6

6

6

20

5

16

5

12

5

11

5

3

5

1

5

21

4

18

4

14

4

5

4

9

3

8

3

7

3

4

3

2

3

10

2

Fuente: Autores, 2021

Por lo que el orden correspondiente para esta Coloracin 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 Ilustracin 11, se muestra la 4-coloracin obtenida.

Ilustracin 11: Grafo para la Coloracin Matula, Marble e Isaacson

 

 

 

Fuente: Autores, 2021

 

Algoritmo de Coloracin de Brelaz

Para este algoritmo no va a haber un orden especificado con anterioridad, sino que se ir ordenando segn se vaya desarrollando el grado de color de los vrtices, sin embargo, como se observa en la Ilustracin 12, la numeracin de los vrtices se mantiene.

Como la investigacin previa lo plantea, primeramente, se selecciona uno de los vrtices con grado ms alto, en este caso se utiliz el vrtice 19, y a partir de ello se buscaba los vrtices que tenan mayor grado de color, en caso de haber varios, se seleccionaba el que tena mayor grado de vrtice, y en caso de tener el mismo tambin, se usaba aquel que tena mayor nmero de vrtice.

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

En la Ilustracin 13, se muestra de manera general el procedimiento mencionado, con el fin de entender mejor el desarrollo del algoritmo, observando adems el orden de coloracin en la Tabla 4.

Ilustracin 12: Grafo para la Coloracin Brelaz

Ilustracin 13: Coloracin 4 Primeros Vrtices

Fuente: Autores, 2021

 

Tabla 4: Datos utilizados y recolectados para la Coloracin Brelaz

No de vrtices

Grado del Vrtices

Grado de color

Orden

19

7

0

1

6

6

2

5

13

6

2

13

15

6

2

9

17

6

1

2

22

6

2

10

23

6

2

7

1

5

3

16

3

5

3

18

11

5

3

15

12

5

3

14

16

5

3

6

20

5

3

12

5

4

2

8

14

4

2

17

18

4

2

3

21

4

3

11

2

3

3

19

4

3

3

20

7

3

2

21

8

3

3

22

9

3

2

4

10

2

2

23

Fuente: Autores, 2021

Se puede observar, en la Ilustracin 14 que, con este algoritmo, se obtuvo, de igual manera, una 4-coloracin.

Ilustracin 14: Coloracin Brelaz

 

 

 

Fuente: Autores, 2021

En la Ilustracin 15[2] , se observa el mapa poltico del Ecuador, en blanco para poder colorearlo y en la Ilustracin 16, se muestra el mapa del territorio ecuatoriano, coloreado como se obtuvo en la Ilustracin 14, previamente visualizada aplicando el algoritmo de coloracin de Brelaz.

Ilustracin 15: Mapa Poltico en Blanco

Ilustracin 13: Mapa Coloreado del Ecuador

Fuente: Autores, 2021

Anlisis de resultados

Se realizar la evaluacin de todos los grafos tanto individualmente como en conjunto, para tener una visin completa de los resultados del presente estudio. Considerando los criterios establecidos: La presentacin final del mapa (C1), Eficacia del teorema (C2), Optimizacin de tiempo de resolucin (C3) y Facilidad de resolucin (C4).

La manera en que sern evaluados los grafos ser mediante una especie de calificacin, donde los criterios se evaluarn con el porcentaje de importancia dentro de la investigacin para poder finalizar con un 100% de recomendacin de uso del algoritmo, en caso de cumplir todos los parmetros. Cabe recalcar, nuevamente, que estos se plantearon en funcin a la informacin expuesta en el marco terico de la presente investigacin.

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

 

 

 

Tabla 5: Matriz de Evaluacin

Descriptores

(C1)

Es visualmente atractivo, los colores tienen relacin con el origen del grafo.

0-10

(C2)

Una 4-coloracin que demuestra el teorema de los 4 colores.

0 50

(C3)

Tiempo de resolucin corto.

0 25

(C4)

Nivel de resolucin fcil, tanto de realizar como de entender.

0 - 15

Total

Secuencial Bsico

Cumple con el descriptor.

10

No se cumpli el teorema, debido a que hubo dos puntos que no podan ser coloreados con los colores establecidos.

0

Cumple con el descriptor.

25

No existe exigencia alguna en cuestin a la comprensin y aplicacin del algoritmo.

15

50/100

De Walsh y Powell

Existe un equilibrio con la cantidad de vrtices coloreados con cada uno de los colores especificados.

10

Se cumple a cabalidad el teorema.

50

Se demora nicamente en ordenar los datos, en caso de saber usar herramientas o aplicaciones como Excel, no tomar demasiado tiempo.

23

Existe cierta complicacin debido a que para facilitar el procesamiento de datos se requiere de una aplicacin adicional.

13

96/100

De Matula, Marble, Isaacson

Existe un equilibrio con la cantidad de vrtices coloreados con cada uno de los colores especificados.

10

 

Se cumple a cabalidad el teorema.

50

Se demora nicamente en ordenar los datos, en caso de saber usar herramientas o aplicaciones como Excel, no tomar demasiado tiempo.

23

Existe cierta complicacin debido a que para facilitar el procesamiento de datos se requiere de una aplicacin extra, en caso de saber manejar las herramientas, no existe ninguna dificultad aadida. Inclusive, al trabajar con los datos del algoritmo anterior, se facilita el proceso an ms.

13

96/100

De Brelaz

No existe un equilibrio entre la cantidad de vrtices coloreados como en los algoritmos anteriores.

8

Se cumple a cabalidad el teorema.

50

El tiempo de resolucin fue mayor, debido a que no existe un orden de coloracin establecido previamente, sino que se colorea segn como se avance y se analice en el grafo los grados de color, los grados de los vrtices y dems.

20

La facilidad de resolucin de este algoritmo es levemente ms complicada, debido a que es necesario el uso de Excel para la organizacin de datos y el de la coloracin en general. Puede resultar confuso el cmo se resuelve y se colorea, requiere de una lectura comprensiva y de un conocimiento ligeramente ms complejo del tema tratado.

10

88/100

Promedio de eficacia total (%)

82,50

Fuente: Autores, 2021

Considerando la evaluacin 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 recomendacin.

 

 

 

Conclusiones

Se puede concluir indicando que, dentro de la presente investigacin la mayora de los algoritmos presentados cumplen con los criterios, parmetros y expectativas propuestas.

Se ha podido demostrar la veracidad del Teorema de los Cuatro Colores, debido a que es un tema sumamente interesante y todava investigado por las mentes ms brillantes. Lo que pudo afectar para que no se cumpliera el teorema en el algoritmo Secuencial Bsico pudo haber sido el orden, debido a que no existe un orden especfico y puede variar infinitamente.

Sin embargo, mientras disminuye la posibilidad de variabilidad y se sigue un patrn o conceptos bases, es ms fcil que se cumpla el teorema, como es el caso del algoritmo de Brelaz. Debido a la evaluacin realizada, se podra 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 considerara ms 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 coloracin se cumpla a cabalidad.

Para el presente trabajo se determin que el nmero cromtico sera 4, debido al objetivo de demostrar el Teorema de los Cuatro Colores. Sin embargo, no se niega el que la coloracin pueda ser menor, como mnimo se alcanzara una 3-coloracin debido a la cantidad de vrtices, al estar hablando de 23 vrtices, resulta complejo determinar que el nmero cromtico pueda ser menor. Por lo que, se deja abierto el espacio para un anlisis pertinente sobre el menor nmero cromtico alcanzable con 23 vrtices. Cabe recalcar que, se necesita de la ayuda tecnolgica, principalmente debido a las posibles maneras de ordenar los vrtices, ya que stas pueden resultar en nmeros infinitos.

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

 

 

 

 

Referencias Bibliogrficas

1.                  Alvarado, Jorge. (2021). Comparacin con grafos de programas de pregrado de estudio en informtica del Per. Universidad Nacional Mayor de San Marcos. Lima-Per. https://doi.org/10.1590/SciELOPreprints.1992

 

2.                  lvarez Nez, M. y Parra Muoz, J. (2013). Teora de Grafos. Chilln, 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 Garca, M. (2019). Actividades con grafos para estudiantes con altas capacidades. Universidad de Colombia. Edma 0-6: Educacin Matemtica en la Infancia, 8(2), pp. 92-108. http://www.edma06.es/index.php/edma0-6/issue/arch

 

6.                  Bombal, Fernando. (2017). Matemtica, Lgica y Operadores. La Gran Alianza. XIX Programa de Promocin de la Cultura Cientfica y Tecnolgica Rev.R.Acad.Cienc.Exact.Fs.Nat. Vol. 109, No. 1-2, pp 59-72.

 

7.                  Flores Muoz, K. (2012). Implementacin de una heurstica para resolver el problema de coloramiento de grafos aplicado a la planificacin de horarios de una institucin educativa. Escuela Superior Politcnica del Litoral, Instituto de Ciencias Matemticas. Guayaquil: ESPOL. Obtenido de Tesis: https://www.dspace.espol. edu.ec/retrieve/100843/D-CD102684.pdf

 

8.                  Iniesto Daz, A. (2012). Aplicacin Integral de Grafos: Coloracin. (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 Daz, A., & Delgado Nez, J. (2012). Aplicacin Integral de Grafos. Coloracin y Bsqueda. Obtenido de http://www.dma.fi.upm.es/personal/gregorio/grafos/web/iagraph /coloracion.html

 

10.              Lazo, J. y Len, D. (2020). Anlisis comparativo entre los procesos de diseo grfico tradicional y generativo para la creacin de elementos de comunicacin visual. Universidad del Azuay. http://dspace.uazuay.edu.ec/handle/datos/9972

 

11.              Morales Galindo, K. (2016). Matemticas 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). Hbrido MST-20pt para la Solucin del Problema del Agente Viajero. (U. d. Puebla, Ed.) Obtenido de Tesis profesional: http://catarina.udlap.mx/udla/tales/doc umentos/lis/palaciossd/capitulo2.pdf

 

13.              Patio Avedao, B. y Guillermo Charry, . (2013). La enseanza de la Teora de Grafos como estrategia para desarrollar procesos de matematizacin. (U. S. Arboleda, Ed.) Obtenido de Tesis de Maestra: 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 Coloracin de Grafos. (U. d. Compostela, Ed.) Obtenido de Tesis de Maestra: http://eamo.usc.es/pub/mte/descargas/ProyectosFinMaster/Proyecto11463.pdf

 

 

 

2021 por los autores. Este artculo es de acceso abierto y distribuido segn los trminos y condiciones de la licencia Creative Commons Atribucin-NoComercial-CompartirIgual 4.0 Internacional (CC BY-NC-SA 4.0)

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

 

 



[1] Nota. Adaptado de Mapa del Ecuador-Provincias y Capitales [Fotografa], por Christian Andrade, 2015, NOTICIASEC (https://noticiasec.com/provincias-y-capitales-del-mapa-de-ecuador/) Copyright 2018.

[2] Nota. Adaptado de Mapa de Ecuador para Colorear (IMPRIMIR). [Fotografa], 2016, Informacin Ecuador. (https://informacionecuador.com/mapa-politico-de-ecuador-para-colorear-pintar/)

Enlaces de Referencia

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





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/