FORMULACION DEL PROBLEMA
Se le ha comunicado a Hidrandina
que ha habido un robo de cableado
en unos pueblos rurales, este
inmediatamente desde su
industria, manda una movilidad
para que recogan a sus
representantes que se encuentran
en una ciudad capital para que cada uno vaya a un pueblo a solucionar el
problema pero lo mas rapido posible, donde A, es su industria y B es la ciudad
capital y todo lo demas son los pueblos, cabe resaltar que los numeros vendrian a
ser la distancia entre un lugar a otro. Esto se soluciona con la teoria de grafos.
SOLUCIN
Antes de poder dar una solucin al problema,
primero debemos enfocarnos en cosas
fundamentales sobre la teora de grafos para que se
pueda entender en su totalidad el desarrollo o mejor
dicho la solucin, comencemos con la definicin, un
grafo es un conjunto de puntos (NODOS o
VRTICES) unidos por lneas (ARCOS o ARISTAS),
y se representa como G(V,E), V de vertice y E, de
aristas solo que esta en ingles, edges. Con la ayuda de la teoria de grafos se
pueden hacer muchas cosas entre las cuales tenemos:
Recorrer cada pueblo de un ciudad, una vez, y regresar al pueblo de origen
y todo al menor costo posible
Encontrar el camino ms corto entre 2 cuidades cualesquiera, etc.
Entre lo importante para destacar tambin est como hallar el grado de uno de los
nodos o vrtices:
Y los tipos de grafos:
Ya visto lo fundamental de la teora de grafos, se ve los algoritmos, que nos
ayudan a minimizar el costo del recorrido y a su vez el tiempo del recorrido, que es
lo que nos pide el problema, se puede usar 3 algoritmos en este caso, el primero
es el algoritmo de Prim, el segundo, el algoritmo de Kruskal y por ltimo el
algoritmo de Dijsktra, este ltimo no lo vamos a usar porque mayormente se usa
para grafos dirigidos.
ALGORITMO DE PRIM:
Este algoritmo consiste en tomar
cualquier vrtice y ver las aristas
adyacentes a l, y tomar la arista
con menor peso o distancia, hasta
que se tomen todos los vrtices
pero no todas las aristas.
Cuando se pasa por un vrtice que no sea A o B, es importante mencionar que se
deja a un representante. El problema empieza por A, que es la industria, y se toma
la arista adyacente, pero en este caso hay una sola arista que se dirige hacia la
ciudad capital, luego la movilidad est en el vrtice B, ah se tiene las aristas de
peso 4 y 10, se toma la de 4, ahora estamos en el vrtice E, tiene dos aristas
adyacentes pero se toma la de peso 2, en este vrtice o pueblo se dejara a 4
representantes, ms adelante se explicara porque, luego es de F a I, en el vrtice
F se dejara a dos representantes, luego de I a J, pero si continuamos de J hasta F,
el camino ya se terminara y no se tomara todos los vrtices, osea todos los
pueblos; lo que dice el algoritmo ante esto, es que como solucin se toma la arista
menor adyacente al camino ya formado, en esta caso la arista de peso 7; pero la
movilidad no va a hacer todo el camino de vuelta hasta el vrtice E y luego irse
hasta el D, por esto en el vrtice E bajaron 4 representantes, uno para que
solucione el problema en el vrtice E y los otros 3 para que se vayan al vrtice D.
Siguiendo la lgica de ejercicio, de D seria a C, pero se resalta que en el vrtice D
se quedan dos representantes, luego de C seria a B, ah terminara pero faltaran
ms pueblos por socorrer todava, por lo que estara mal.
La lgica del algoritmo te dice que cojas la arista con menor peso, que sera la 11,
entonces ira de D a G, el representante que quedo en D se mueve a G y ah se
queda, ahora por ultimo solo fala el vrtice o pueblo H, utilizando la misma la
lgica que de D a G, se toma la arista de F a H, y en el vrtice F, se recuerda que
se bajaron 2 representantes, por lo que, el que sobra se ira al H, las aristas que
no se tomaron se borran para una mejor vista del camino ya formado.
ALGORITMO DE KRUSKAL:
Este algoritmo es otra manera de hallar o
minimizar el recorrido, lo que se hace en este
caso, es ubicar solo los vrtices y luego
empezar buscando el 1 en el peso de las
aristas, si entre dos vrtices hay un 1, se traza
esa arista, y as se sigue, en este algoritmo
hay que tener cuidado de los ciclos, que es
cuando las aristas se cierran, de acuerdo al problema primero se comenzara con
los vrtices de E a F, luego de I a J y as sucesivamente, cuando se llega a 10, ya
se tiene las aristas 4,7 y 5 formadas, y si se pone la arista BC, se forma un ciclo
por lo que no se pone. Al fin y al cabo es el mismo resultado solo que diferente
procedimiento.
DISCUSION DE RESULTADOS
GARCIA SANCHEZ Gerson:
Esta es una de las tantas maneras de emplear las matemticas que se nos
ensea para poder resolver cualquier enigma que se nos presente; a travs de las
simples matemticas se puede resolver cualquier problema al instante, en este
caso debido a estos algoritmos se pudo resolver al instante el robo del cableado, y
Hidrandina se evit un montn de llamadas de mantenimiento o servicio al cliente,
como por ejemplo, de que no tengo luz y aun me siguen cobrando, etc.
MENDOZA VASQUEZ David:
Un problema puede aquejar a cualquier empresa, empresas en la actualidad hay
muchas, pero verdaderas empresas hay pocas y estas son, las que a pesar de los
problemas siempre logran solucionar lo ms rpido posible su inconveniente y
todava con mucha eficiencia, por lo que la diferencia de una empresa a otra es la
manera en como resuelven un problema que les surgen de improviso, as como
HIDRANDINA
QUIROZ MENDOZA lvaro:
La solucin logr sus objetivos, se dio la minimizacin del recorrido y un rpida
respuesta al problema, pero cabe resaltar que no solo basto la capacidad de saber
el tema de los grafos o saber sus aspectos bsicos, cualquiera habra intentado
hacer lo mismo, resolver el problema con los algoritmos pero puede que se haya
atascado porque no saba qu hacer, por ejemplo en el vrtice de F a J, por lo que
en este caso tambin intervino el ingenio, la capacidad de pensar ms all de lo
que te explicaban, eso hizo la diferencia.
ULLOA TOMAS Wilson:
Es muy importante conocer los fundamentos tericos para poder resolver un
problema, como se pudo ver, si los de Hidrandina no hubieran conocido el tema de
los grafos y sus algoritmos, no hubieran logrado resolver al instante este
problema, seguro lo hubieran podido resolver pero tardndose ms de lo inusual.
REFERENCIAS BIBLIOGRAFICAS:
Barrero, A. C., de Garca, G. W., & Parra, R. M. M. (2010). Introduccin a la Teora de
Grafos. ELIZCOM SAS.
Mendez, A. (1998). Una breve introduccin a la teora de grafos. Suma, 28, 11-26.