MEMORIA DESCRIPTIVA
CONCURSO LIBRETICS.
Proyecto sobre obtención de rutas
eficientes y conectividad optimizada
entre puntos mediante la teoría de
grafos.
Autores:
Sergio Vela Liñán
Alba Mancebo Caberta.
Curso: 2º de Bachillerato.
MEMORIA DESCRIPTIVA
Aplicación de la Teoría de GrafosAplicación de la Teoría de GrafosAplicación de la Teoría de GrafosAplicación de la Teoría de Grafos
(Situación 1)
Imaginemos que somos un técnico de instalación de cableado que tiene que conectar una red
eléctrica entre varios pueblos. Su jefe le obliga a utilizar la menor longitud de cable posible
para ahorrar gastos. Los pueblos están conectados de la manera siguiente:
- Cada arista del grafo representa el camino más corto entre los dos pueblos de los
extremos
- Cada vértice representa cada uno de los pueblos:
Pueblo A: Alcafrán
Pueblo B: Bustarviejo
Pueblo C: Consuegra
Pueblo D: Duruelo
Pueblo E: San Esteban de Gormaz
- Los números representan una distancia ficticia entre cada uno de ellos
Para conectar todos los puntos usando la menor longitud total posible, es decir, para
encontrar el árbol recubridor mínimo en este grafo conexo y no dirigido cuyas aristas tienen
peso; el técnico utilizará un algoritmo.
MEMORIA DESCRIPTIVA
� Algoritmo de Kruskal
1. Se selecciona la arista de menor peso en el grafo
2. Se selecciona la siguiente arista con menor peso que no cree un ciclo (camino
cerrado)
3. Se repite el último paso hasta que todos los puntos estén conectados
En el ejemplo:
1. Tomaría la arista BE con un peso de 1km. Ya que los grafos no están direccionados
daría lo mismo decir BE que EB.
2. La siguiente más corta será la AC con un peso de 3km.
3. Posteriormente elegiría la DA con un peso de 4km (y ya la DC queda descartada por
formar ciclo).
4. Por último, cogería la EA con un peso de 8km.
Así ya tendría todos los puntos conectados con un cable total de 1+3+4+8=16km.
La complejidad del grafo nos relaciona el número de vértices y con el tiempo empleado en
resolver el problema. En concreto este algoritmo tiene una complejidad cúbica.
Para nuestro ejercicio el técnico ha conectado 5 pueblos empleando 5 minutos. Supongamos
que tenemos 15 pueblos, al triplicarse el número de vértices el tiempo empleado aumentará
3�= 27.
� Algoritmo de Prim
Este algoritmo puede hacerse tanto con tabla como sin tabla. Para explicarlo
utilizaremos el segundo método que es el más complejo. De forma genérica el
procedimiento del algoritmo de Prim es el siguiente:
1. Se selecciona cualquier vértice.
2. Se elige la arista de menor peso conectada a ese vértice.
3. Se toma la arista más corta que conecte un vértice ya elegido con uno nuevo.
4. Se repite este último paso hasta que todos los vértices estén conectados.
MEMORIA DESCRIPTIVA
En el ejemplo:
- A B C D E
A - 10 3 4 8
B 10 - 12 9 1
C 3 12 - 6 9
D 4 9 6 - 11
E 8 1 9 11 -
Empezamos en Bustarviejo (vértice B) y se tacha su fila. En su columna se le coloca un
subíndice 1 para indicar que se ha seleccionado. Ahora se elige el número más pequeño en la
columna B (el 1).
- A B1 C D E
A - 10 3 4 8
B 10 - 12 9 1
C 3 12 - 6 9
D 4 9 6 - 11
E 8 1 9 11 -
El número seleccionado corresponde a la conexión BE. Por ello, ahora suprimimos la fila E y
seleccionamos la columna E con el subíndice 2. Buscamos el número más pequeño de las
columnas que ya hemos seleccionado (la B y la E)
- A B1 C D E2
A - 10 3 4 8
B 10 - 12 9 1
C 3 12 - 6 9
D 4 9 6 - 11
E 8 1 9 11 -
MEMORIA DESCRIPTIVA
Esto se repite sucesivas veces hasta que estén todos los vértices conectados, es decir:
- Se suprime la fila A y en la columna A se coloca el subíndice 3, busca el valor más
pequeño en las 3 columnas seleccionadas, que sería el AC= 3.
- Se selecciona la columna C y se busca el valor más pequeño en las columnas
seleccionadas, que sería el AD=4.
- A3 B1 C4 D5 E2
A - 10 3 4 8
B 10 - 12 9 1
C 3 12 - 6 9
D 4 9 6 - 11
E 8 1 9 11 -
Ya estarían todos los pueblos conectados observando que el resultado es el mismo que el de
Kruskal. Los seleccionados serían: BE (1) + AE (8) + AC (3) + AD (4) = 16km
En los pueblos que no tienen conexión directa el técnico ha colocado una raya pero si esto se
hiciese con ordenador, hay ciertos programas que no la reconocen y habría que poner un valor
infinito. Al ser mayor a cualquier número existente en las conexiones el ordenador no lo
seleccionará.
Dada su complejidad de orden cúbico hay muchos problemas en la vida real que a un ser
humano llevaría años hacer suponiendo que se estuviera las 24h del día trabajando en el
problema. Lo cual requiere el uso de computadoras. Esto nos presenta un problema: si se
pudieran elegir dos aristas con la misma longitud, un ser humano seleccionaría uno
arbitrariamente, pero un ordenador no puede hacer esto porque no presenta capacidad de
razonamiento. Esto supone que se tengan que modificar los programas iniciales para permitir
que el ordenador puede elegir entre una de las dos alternativas.
Conclusión: Mediante estos dos sencillos algoritmos el técnico de instalación eléctrica podría
rentabilizar el material empleado en el proceso y así rebajar el coste de producción.
MEMORIA DESCRIPTIVA
Orden en el que se escogen los vértices.
Distancia de A al
Distancias
(Situación 2)
Ahora imaginemos que un conductor de camiones que se mueve por una comarca quiere ir de
A al resto de los pueblos por el camino más corto. Para ello nuestro conductor empleará el
algoritmo de Dijkstra, que permite ir de un punto (pueblo A) a otro reduciendo costes.
� Algoritmo de Dijkstra
Añadimos al grafo unos recuadros para indicar unos valores según el esquema siguiente. Como
empezamos por el vértice A en el hueco del orden será el 1, y la distancia de A a él mismo será
0.
MEMORIA DESCRIPTIVA
Así la distancia de A a los tres puntos conectados (B, D y C) se escribe en el recuadro de abajo.
Se selecciona la menor de ellas, es decir, C, que se elegirá en la segunda reiteración del
proceso algorítmico. Por ello, en el recuadro correspondiente al orden se coloca un 2 y la
distancia de C a A por el camino más corto será de 3, número que se escribe en el recuadro de
la derecha.
Ahora se suman las distancias que hay desde C hasta los dos puntos conectados a C a la
distancia que conecta C y A, para hallar la distancia de estos puntos (D y E) hasta A. En el
vértice C, la nueva distancia será de 6, menor a la conexión directa DA, de 7. Por ello se tacha
el 7 y se reemplaza por el 6. Esto se hará siempre que la nueva distancia sea menor a la
antigua.
MEMORIA DESCRIPTIVA
Ahora el vértice que presenta en número más pequeño (y que no está ya conectado a A es el
B), que se selecciona. Se coloca un 3 en el recuadro correspondiente al orden y un 4 en el de la
derecha, su distancia a A.
Como hemos seleccionado el B, al igual que antes, actualizamos las distancias: ponemos un 8
en el F, y en el D tachamos el 6 y colocamos un 5.
Se repite este proceso hasta que tengamos todos los vértices con su camino correspondiente,
obteniendo el siguiente resultado:
MEMORIA DESCRIPTIVA
La distancia de A a cada punto y su ruta correspondientes son:
• AB: ruta directa (4)
• AC: ruta directa (3)
• AD: ABD (5)
• AE: ABDE (7)
• AF: ABDF (7)
• AG: ABDEG (9)
La complejidad del algoritmo de Dijkstra es de orden cuadrático, lo que significa que si en vez
de 7 pueblos tuviésemos 14 (duplicándose), el tiempo empleado en resolverlo sería 22=4 veces
mayor.
Conclusión: Mediante este sencillo algoritmo el conductor de camiones sería capaz de llegar
a cualquiera de sus destinos desde su ubicación actual de la manera más corta y rápida,
ahorrando combustible y tiempo.
(Combinada)
Ahora bien, imaginemos que en el primer ejemplo que hemos puesto (el del técnico de
cableado) quisiéramos hallar la ruta que recorre un electrón que quisiera ir de un punto a otro
de la red instalada. Suponemos que el electrón “inteligente” elegirá siempre el camino más
corto. Lo que habría que hacer es simple: aplicar el algoritmo de Dijkstra sobre el de Prim. Esto
es lo que haría un ordenador tradicional. Sin embargo, un ser humano, en un grafo tan sencillo
puede ver a simple vista la ruta más corta, sin necesidad de aplicar algoritmo alguno.
MEMORIA DESCRIPTIVA
(Situación 3)
Por último nos imaginamos que un programador de GPS quiere fabricar un modelo avanzado
que sea capaz de encontrar el camino más corto desde todos los puntos hasta cualquiera de
ellos. Para ello nuestro programador utilizará el algoritmo de Floyd
� Algoritmo de Floyd
Se construyen dos tablas: en una de ellas se recogen las distancias entre las ciudades y en la
otra una serie de datos cuya utilidad veremos al final del proceso. En la primera reiteración
seleccionamos la primera fila y la primera columna. Sumamos cada elemento de una fila con su
correspondiente en la columna (en notación matricial el aij con el aji).
1 2 3 4 5 1 2 3 4 5
1 - 6 - 2 3 1 1 2 3 4 5
2 6 - 7 3 - 2 1 2 3 4 5
3 - 7 - 6 9 3 1 2 3 4 5
4 2 3 6 - 7 4 1 2 3 4 5
5 3 - 9 7 - 5 1 2 3 4 5
MEMORIA DESCRIPTIVA
Tras esto se reemplaza el número de la celda ajj por la suma obtenida siempre que sea menor
al antiguo valor (en caso de que sean iguales se escoge arbitrariamente entre reemplazarlo y
no reemplazarlo). En la tabla de la derecha se señalan las casillas correspondientes a los
números cambiados, y se reemplazan por el número que se encuentre en la columna
correspondiente a la reiteración que tiene lugar.
1 2 3 4 5 1 2 3 4 5
1 - 6 - 2 3 1 1 2 3 4 5
2 6 12 7 3 9 2 1 2 3 4 5
3 - 7 - 6 9 3 1 2 3 4 5
4 2 3 6 4 5 4 1 2 3 4 5
5 3 9 9 5 6 5 1 2 3 4 5
1 2 3 4 5 1 2 3 4 5
1 - 6 - 2 3 1 1 2 3 4 5
2 6 12 7 3 9 2 1 1 3 4 1
3 - 7 - 6 9 3 1 2 3 4 5
4 2 3 6 4 5 4 1 2 3 1 1
5 3 9 9 5 6 5 1 1 3 1 1
Ahora se eligen la segunda fila y la segunda columna y se repite el proceso.
1 2 3 4 5 1 2 3 4 5
1 - 6 - 2 3 1 1 2 3 4 5
2 6 12 7 3 9 2 1 1 3 4 1
3 - 7 - 6 9 3 1 2 3 4 5
4 2 3 6 4 5 4 1 2 3 1 1
5 3 9 9 5 6 5 1 1 3 1 1
1 2 3 4 5 1 2 3 4 5
1 12 6 13 2 3 1 2 2 2 4 5
2 6 12 7 3 9 2 1 1 3 4 1
3 13 7 14 6 9 3 2 2 2 4 5
4 2 3 6 4 5 4 1 2 3 1 1
5 3 9 9 5 6 5 1 1 3 1 1
MEMORIA DESCRIPTIVA
Tras la tercera reiteración no se cambia ningún valor, por lo que la tabla tras la tercera
reiteración sería la misma que la obtenida tras la segunda. Aplicamos ahora la cuarta
reiteración:
1 2 3 4 5 1 2 3 4 5
1 12 6 13 2 3 1 2 2 2 4 5
2 6 12 7 3 9 2 1 1 3 4 1
3 13 7 14 6 9 3 2 2 2 4 5
4 2 3 6 4 5 4 1 2 3 1 1
5 3 9 9 5 6 5 1 1 3 1 1
1 2 3 4 5 1 2 3 4 5
1 4 5 8 2 3 1 4 4 4 4 5
2 5 6 7 3 8 2 4 4 3 4 4
3 8 7 12 6 9 3 4 2 4 4 5
4 2 3 6 4 5 4 1 2 3 1 1
5 3 8 9 5 6 5 1 1 3 1 1
Por último realizamos la quinta reiteración y nos sale la tabla final:
1 2 3 4 5 1 2 3 4 5
1 4 5 8 2 3 1 4 4 4 4 5
2 5 6 7 3 8 2 4 4 3 4 4
3 8 7 12 6 9 3 4 2 4 4 5
4 2 3 6 4 5 4 1 2 3 1 1
5 3 8 9 5 6 5 1 1 3 1 1
La tabla de la izquierda indica la distancia que hay de un punto a otro por el mejor camino y la
tabla de la derecha nos indica la ruta que hay que tomar.
MEMORIA DESCRIPTIVA
Por ejemplo para ir del punto 5 al 2: observamos en la fila 5 su intersección con la columna 2.
El número 1 que hay en esa celda nos indica la fila que debemos mirar a continuación. En la
celda intersección entre la fila 1 y la columna 2 es un 4. De ese punto debemos ir a la fila 4
donde ya accedemos al punto 2
La ruta que debemos seguir es: 5-1-4-2, con una distancia de 8.
La complejidad de este algoritmo es cúbica por lo que se aplica de igual manera que la ya
explicada de Prim y Kruskal.
Conclusión: Este algoritmo le permitiría al programador diseñar un sistema GPS que
comunique todos los puntos de la red por las rutas más eficientes.
Conclusiones finales
En cuanto al tema de la complejidad podemos elaborar una función que represente la relación
entre el factor en que se incrementan el número de vértices y el actor en que se incrementa el
tiempo. Tendremos un caso para Dijkstra (en el que será cuadrática) y otro para Prim, Kruskal y
Floyd (en el que será cúbica). Estas funciones se pueden representar en las coordenadas
cartesianas, obteniendo lo siguiente:
MEMORIA DESCRIPTIVA
En el eje x se representa el factor en el que se incrementa el número de vértices y en el eje y el
factor en el que se incrementa el tiempo. En el caso que está representado arriba, el de
Dijkstra, la clásica parábola y=x2. Veamos lo que ocurre con los algoritmos que presentan una
complejidad de orden cúbico:
En este caso, como se puede observar en la gráfica, el factor en que se incrementa el tiempo
aumenta aún más rápidamente.
Como las funciones son polinómicas de grado mayor a 1, el tiempo empleado aumenta muy
rápidamente a partir de un número de vértices muy frecuente en la vida real. Esto quiere decir
que un ser humano tardaría años, e incluso siglos, en resolver estos problemas. Por ello, se
emplean ordenadores capaces de realizar cientos de miles o incluso millones de sumas y
comparaciones por segundo. Debido a esto hay un segundo factor a tener en cuenta: no solo
es necesario saber aplicar los algoritmos sino que también hay que saber programar un
ordenador para que lleve a cabo el proceso.
Estos métodos tienen una gran trascendencia en determinados problemas de la vida real,
como hemos demostrado en algunas situaciones de esta exposición. Pero hay algo que no
hemos mencionado: parece que todos estos métodos están basados en la observación de la
realidad, pero no es así. Como teoremas matemáticos que son no provienen de la experiencia,
estamos suponiendo que las aristas no tienen anchura, lo cual es imposible, que las distancias
son números exactos, lo cual también resulta imposible. Si aplicamos estos conceptos a un
espacio irreal, como el que se estudia en la matemática, los resultados que obtendremos serán
perfectos, el algoritmo representará el camino más corto o el árbol recubridor mínimo en un
espacio imaginario.
En este caso, cuando se nos presenten dos distancias iguales, sí que podremos elegir
arbitrariamente una. Pero esto no será así cuando lo apliquemos en la vida real. Nunca habrá
dos distancias iguales, siempre una será más larga que la otra. En el ejemplo de los cables, si
hubiera una distancia superior en menos de un 1 %, en un caso se consumiría un poco más de
energía eléctrica, puesto que la red es algo mayor. Con ello en un circuito convencional,
teniendo en cuenta los precios energéticos actuales, supondrá una pérdida monetaria de
MEMORIA DESCRIPTIVA
apenas unas fracciones de céntimo. Ahora bien, cuando una empresa construya millones de
terminales con estos circuitos, la fracción de céntimo, se multiplicará por un factor bastante
elevado, perdiendo una cantidad de dinero con la que se podrían comprar varias casas.
Esta misma objeción se puede poner a los otros dos casos, haciendo que se cometa un error si
las situaciones aquí planteadas tuvieran un referente en la realidad.