Coloracin de Grafos y su aplicacin a la
Geografa
Graph coloring and its application to
Geography
Luis Fernando Carrasco-Pilco I
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/u−dl−a/tales/doc umentos/lis/palacios−s−d/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/