2 Redes Valoradas

Instrumentos Estadísticos Avanzados
Facultad Ciencias Económicas y Empresariales

Departamento de Economía Aplicada
Profesor: Santiago de la Fuente Fernández
REDES VALORADAS. ALGORITMOS

Definiciones y teoremas
REDES VALORADAS
Algoritmo de Dijkstra
Algoritmo de Ford‐Fulkerson
Flujo máximo: Programación Lineal
Algoritmo de Prim
Algoritmo de Kruskal
Algoritmo de Boruvka
Algoritmo de Sollin
Otros Algoritmos. Aplicaciones
Portal Estadística Aplicada: Redes Valoradas. Algoritmos 1

ÁRBOLES GENERADORES
Un árbol es toda red (o grafo) G = (V, A) conexa, sin ciclos y con

dos vértices al menos, se designa por T.
La red adjunta representa un árbol, el vértice O recibe el nombre
de raíz del árbol.
A los vértices o nodos se les da el nombre de hojas.
Los demás vértices reciben el nombre de nodos de ramificación.
Si el árbol tiene n nodos el número de aristas es (n − 1).
Excluida la raíz, con los demás vértices se pueden formar subconjuntos disjuntos, cada uno de los
cuales es a su vez un árbol.
Todo par de vértices está unido mediante una sola cadena.
Un grafo es un árbol ⇔ Existe un único camino simple entre todo par de vértices
Un árbol se dice binario si todos sus nodos, excepto las hojas, tienen dos sucesores inmediatos.
Un árbol generador de una red (o grafo) conexa y sin bucles es una red parcial de la inicial que tiene
estructura de árbol.
Si una red conexa y sin bucles está valorada es un árbol mínimo (respectivamente, máximo) a un
árbol generador para el cual la suma de los valores asociados a los arcos seleccionados es mínima
(respectivamente, máxima)
Árbol maximal o generador de un grafo G conexo es un subconjunto máximal de G que también sea
un árbol.
Un árbol maximal de G contiene todos los vértices V de G
Un conjunto de árboles recibe el nombre de bosque. Un árbol formado por un solo vértice y sin
lados, se llama árbol degenerado.
Un dígrafo se denomina árbol dirigido cuando su grafo asociado es un árbol.
Teoremas relativos a la caracterización de Árboles:
Dado un árbol, se verifica que V = A + 1
Todas las aristas de un árbol son puentes.

Si a un árbol se le agrega una arista entre dos de sus vértices, deja de ser un árbol.
En un bosque de k componentes se verifica que V = A + k
Los problemas de redes surgen en una gran variedad de situaciones, redes de transporte, eléctricas
y de comunicaciones predominan en la vida.

La representación de redes se utiliza en casi todos los ámbitos científicos, sociales y económicos, tal
como la producción, distribución, planeación de proyectos, administración de recursos, planeación
financiera, localización de instalaciones, etc.
En la actualidad se dispone de algoritmos y paquetes informáticos (WinQSB) que se utilizan de
forma rutinaria para resolver problemas que no se podrían manejar hace dos décadas.
Muchos de los problemas de optimización de redes son tipos especiales de problemas de
programación lineal, como pueden ser el Problema de Transporte, el Problema de Asignación, o el
problema del Flujo del Coste Mínimo.
ÁRBOL GENERADOR MÍNIMO

Dado un grafo G conexo y etiquetado, recibe el nombre de árbol maximal minimal o generador
mínimo, un árbol generador de G tal que la suma de los pesos de sus lados (aristas) sea mínima.
En un árbol de expansión mínima el número de aristas es la cantidad de vértices o nodos menos 1:
número aristas = número de vértices − 1
Para encontrar un árbol de expansión mínima o árbol recubridor se utilizan varios algoritmos, entre
otros, algoritmo de Prim, algoritmo de Kruskal y algoritmo de Boruvka o Sollin.
Ambos son algoritmos voraces, esto es, cada elemento a considerar se evalúa una única vez, siendo
seleccionado o descartado, de tal forma que si es el elemento seleccionado forma parte de la
solución, y si fuera descartado, no forma parte de la solución ni volverá a ser considerado para la
misma.
El esquema del algoritmo voraz (devorador o greedy) es el que menos dificultades plantea a la hora
de diseñar y comprobar su funcionamiento.
Normalmente se aplica a los problemas de optimización.
ÁRBOL GENERADOR MÁXIMO

Dado un grafo G conexo y etiquetado, recibe el nombre de árbol maximal máximo o generador
máximo, un árbol generador de G tal que la suma de los pesos de sus lados (aristas) sea máxima.
Para encontrar un árbol de expansión máxima puede emplearse el algoritmo de los pesos
decrecientes como si se tratase de encontrar un árbol de generador mínimo, pero con dos
diferencias sobre el algoritmo anterior:
a) Añadir aristas en lugar de suprimirlas.
b) La conexión de una arista no deberá formar un ciclo.
En consecuencia, el árbol maximal máximo tiene tantos vértices como el grafo G de procedencia.

APLICACIONES DEL ALGORITMO DE EXPANSIÓN MÍNIMA
El algoritmo de expansión mínima se aplica en muchos diseños importantes, entre otros:
Redes de telecomunicaciones.
Redes de transporte para minimizar el costo total de proporcionar arcos (aristas) en carreteras,
vías ferroviarias, etc.
Cableados de equipos eléctricos.
Red de líneas de transmisión de energía eléctrica de alto voltaje.
Diseñar una red de tuberías para conectar varias localidades.
TERMINOLOGÍA DE REDES
Una red es un conjunto de puntos y un conjunto de líneas que unen pares de puntos.
Los puntos se llaman nodos (o vértices).
Las líneas se llaman arcos (o ligaduras, aristas o ramas). Los arcos se etiquetan al dar el nombre de
los nodos en sus puntos terminales, en esta línea AB es el arco entre los nodos A y B. Los arcos de
una red pueden tener un flujo de algún tipo que pase por ellos.
Cuando el flujo a través de un arco se permite solo en una dirección (como en una calle de un
sentido) se denomina arco es dirigido, una forma de etiquetarlo es A → B.
Si el flujo a través de un arco se permite en ambas direcciones se dice que es un arco no dirigido,
con frecuencia se les denomina ligadura.
Una red que tiene sol arcos dirigidos se llama red dirigida, si tiene solo arcos no dirigidos se dice que
es una red no dirigida. Una red con mezcla de arcos no dirigidos y dirigidos (incluso con todos sus
arcos no dirigidos) se puede convertir en una red dirigida mediante la sustitución de cada arco no
dirigido por un par de arcos dirigidos en direcciones opuestas. Después, según convenga, se puede
proporcionar un flujo neto en una sola dirección o interpretar los flujos a través de cada para de
arcos dirigidos como flujos simultáneos en direcciones opuestas.
En el proceso de toma de decisiones sobre el flujo de un arco no dirigido se permite hacer una
secuencia de asignaciones de flujos en direcciones opuestas, entendiendo que el flujo real será el
flujo neto, esto es, la diferencia de los flujos asignados en las dos direcciones.
Sea un ejemplo, se asigna un flujo de 10 en una dirección y después un flujo 4 en la dirección
opuesta, el efecto real es la cancelación de 4 unidades de asignación original, lo que reduce el flujo
en la dirección original de 10 a 6.
En arcos dirigidos en ocasiones se utiliza la misma técnica como una forma de reducir un flujo
asignado con anterioridad.
En particular, se puede hacer una asignación ficticia de flujo en la dirección equivocada a través de
un arco dirigido para registrar una reducción en esa cantidad del flujo que va en dirección correcta.

Se conoce como capacidad del arco a la cantidad máxima de flujo (quizá infinito) que puede circular
en un arco dirigido.
Un nodo fuente (nodo de origen) tiene la propiedad de que el flujo que sale del nodo supera al que
entra a él.
En un nodo demanda (o nodo destino) el flujo que llega excede al que sale de él.
Un nodo transbordo (o nodo intermedio) satisface la conservación del flujo, es decir, el flujo que
entra es igual al que sale.
CAMINO DE PESO MÍNIMO

En una red eléctrica o en una red vial no sólo se trata de dar servicio (conexión), es importante
conocer las longitudes de las líneas para establecer cantidad de material, dificultades para su
trazado (coste temporal o monetario), etc.
En el grafo adjunto a cada arista se asigna un valor que representa la magnitud (peso) que se desea
considerar.
El camino 'más corto' entre el vértice v1 y v 3 no es el que tiene

menos aristas, sino aquel que recorre en total menor distancia:
C1 = { v1 , v 3 } recorre solo una arista con una distancia de 9.
C 2 = { v1 , v 2 , v 3 } tiene dos aristas y una distancia total de 6
C 3 = { v1 , v 2 , v 5 , v 3 } tiene tres aristas y una distancia total de 5
El camino más corto entre los vértices v1 y v 3 es C 3 con una distancia total de 5
El conjunto de caminos mínimos desde un vértice v a los restantes vértices de un grafo es un árbol,
llamado árbol de caminos mínimos desde v.
Uno de los algoritmos más utilizados para la búsqueda de caminos de peso mínimo es el de Dijkstra,
que proporciona los pesos mínimos desde un vértice dado al resto de los vértices.

ALGORITMO DE DIJKSTRA: CONSTRUCCIÓN DE ÁRBOL DE CAMINOS MÍNIMOS
El Algoritmo de Dijkstra, descubierto por el físico neerlandés Edsger Dijkstra en 1959, resuelve el
problema de hallar el camino de longitud mínima entre dos vértices de un grafo ponderado.
El algoritmo va explorando los caminos más cortos que parten del vértice origen y que llevan a todos
los demás vértices, el algoritmo finaliza al obtener el camino más corto que lleva a todos los
vértices.
El algoritmo de Dijkstra devuelve en realidad el peso mínimo, no el camino mínimo propiamente
dicho, pero permite obtener fácilmente el camino mínimo recorriendo en sentido inverso de la
construcción.
Es un algoritmo de búsqueda de peso uniforme y, en consecuencia no funciona en grafos con aristas
de peso negativo. Al elegir el nodo (vértice) con menor distancia quedan excluidos de la búsqueda
nodos que en sucesivas iteraciones bajarían el peso general del camino al pasar por una arista con
peso negativo.
El algoritmo de Dijkstra puede producir respuestas incorrectas si tiene pesos

negativos.
La ruta más corta entre A y C no es 3, en realidad es A → B → D → C
Se recurre al algoritmo de Bellman‐Ford
Con el algoritmo de Dijkstra se pueden resolver grafos con muchos vértices, que sería muy
complicado resolver con otros algoritmos, por lo que tiene una aplicación importante en tecnología
y comunicaciones.
El conjunto de caminos mínimos siempre es un árbol generador.
El algoritmo de Dijkstra devuelve el peso mínimo no el camino mínimo. Por lo que en general, el
árbol obtenido no tiene por qué ser mínimo.
A continuación se resuelve el problema de encontrar el camino de longitud mínima entre dos
vértices de un grafo ponderado no dirigido si todos los pesos no son negativos. El Algoritmo puede
adaptarse para resolver problemas de longitud mínima entre grafos dirigidos.

DIJKSTRA: Hallar los caminos de longitud mínima
desde A hasta cada uno de los restantes vértices del
grafo.
Se eligen los nodos adyacentes que tienen menor peso en la

arista. Se elige el nodo B , marcando la arista AB.
Surgen candidatos, el vértice D es el nodo que con 14 tiene
menor peso en la arista. Se marca la arista AD.
Se marca la arista BC porque es el nodo que

con 19 tiene menor peso en la arista.
Cambia el peso de la arista CT a 29.
Se marca la arista DE con peso 20
El árbol de longitud mínima se

muestra en la figura adjunta.
ELABORACIÓN DE LA TABLA DE DIJKSTRA

El algoritmo de Dijkstra construye un árbol de caminos mínimos
desde el vértice A hasta los restantes vértices del grafo.
El algoritmo atribuye a cada vértice v una etiqueta t(v) que es la
longitud del camino ya seleccionado.
Se inicia la tabla con t(A) = 0 , t(v) = ∞ ∀ v ≠ A
A B C D E T Vértice Arista
0• ∞ ∞ ∞ ∞ ∞ A

El vértice es el más pequeño del árbol que se va construyendo, se marca y se incorpora al árbol.
Se toman todas las aristas Av, con el resto de vértices v no pertenecientes al árbol y se actualizan las
etiquetas: mín ⎡⎣ t(v) , t(A) + p(Av) ⎤⎦ .
Aparece una nueva fila en la tabla:
• ∞ ∞ ∞ ∞ ∞ A
0
12• ∞ 14 ∞ ∞ B AB
El vértice con menor etiqueta, en este caso B se marca, se añade al árbol de caminos mínimos y se
incorpora la arista AB .
Se toman todas las aristas Bv, con el resto de vértices v no pertenecientes al árbol y se actualizan las
etiquetas de los vértices adyacentes de B, como antes, mín ⎡⎣ t(v) , t(B) + p(Bv) ⎤⎦ , resultando:
t(D) = 14 < t(B) + p(BD) = 12 + 4 = 16 No cambia

t(C) = ∞ > t(C) + p(BC) = 12 + 7 = 19 Cambia
t(E) = ∞ > t(E) + p(BE) = 12 + 11 = 23 Cambia
t(T) = ∞ > t(T) + p(B T) = 12 + 23 = 35 Cambia
En la tabla aparece una nueva fila con las etiquetas, añadiendo la etiqueta mínima D y la arista AD .
0• ∞ ∞ ∞ ∞ ∞ A
12• ∞ 14 ∞ ∞ B AB
19 14 • 23 35 D AD
Ahora se observan los vértices adyacentes a D que no están en el árbol y se actualizan las etiquetas.
Sólo hay el vértice vecino E: mín ⎣⎡ t(E) , t(D) + p(DE) ⎤⎦
t(E) = 23 > t(D) + p(DE) = 14 + 6 = 20 Cambia
• ∞ ∞ ∞ ∞ ∞ A
0
12• ∞ 14 ∞ ∞ B AB
19 14 • 23 35 D AD
19• 20 35 C BC
De otra parte, para saber cuál es el vértice vecino a C en el árbol, se sube por la columna de C hasta
encontrar la primera variación en las etiquetas.

El vértice marcado en esa fila será el vecino.
La primera variación que se encuentra es el salto de 19 a ∞ , que se produce en la fila donde está 12• ,
en consecuencia, es el vértice B
• ∞ ∞ ∞ ∞ ∞ A
0
12• ∞ 14 ∞ ∞ B AB
19 14 • 23 35 D AD
19• 20 35 C BC
Los vértices adyacentes al vértice C son los vértices E y T.
Se actualizan las etiquetas de los vértices adyacentes de C: mín ⎡⎣ t(v) , t(C) + p(Cv) ⎤⎦ , resultando:
t(E) = 20 < t(C) + p(CE) = 19 + 2 = 21 No cambia

t(T) = 35 > t(C) + p(C T) = 19 + 10 = 29 Cambia
• ∞ ∞ ∞ ∞ ∞ A
0
12• ∞ 14 ∞ ∞ B AB
19 14 • 23 35 D AD
19• 20 35 C BC
20 • 29 E DE
El vértice con etiqueta mínima es E, se añade al árbol el vértice E y la arista DE .
El vértice vecino a E en el árbol se encuentra al subir por la columna E hasta encontrar la primera
variación en las etiquetas, el vértice marcado es 14 • , con lo que es el vértice D, la ruta DE tiene una
longitud 20 − 14 = 6
Continúa el algoritmo, desde el vértice E sólo queda un vértice adyacente, T. Se actualiza la
etiqueta: mín ⎡⎣ t(T) , t(E) + p(E T) ⎤⎦
t(T) = 29 = t(E) + p(E T) = 20 + 9 = 29 No Cambia
• ∞ ∞ ∞ ∞ ∞ A
0
12• ∞ 14 ∞ ∞ B AB
19 14 • 23 35 D AD
19• 20 35 C BC
20 • 29 E DE
29 • T CT

El vértice vecino a T en el árbol se encuentra al subir por la columna T hasta encontrar la primera
variación en la etiqueta, se encuentra en el vértice C.
La ruta CT tiene una longitud 29 − 19 = 10
Se añade al árbol el vértice T y la arista CT.
Para hallar las rutas más cortas desde el vértice A a los restantes vértices no es necesario
representar el grafo, basta con los datos de la tabla:
A B C D E T
• ∞ ∞ ∞ ∞ ∞
0
12• ∞ 14 ∞ ∞
19 14 • 23 35
19• 20 35
20 • 29
29 •
Vecino B el vértice A: Ruta AB. Longitud 12 Observando los vértices vecinos:

Vecino C el vértice B: Ruta BC. Longitud 7
Vecino D el vértice A: Ruta AD. Longitud 14
Vecino E el vértice D: Ruta DE. Longitud 6
Vecino T el vértice C: Ruta CT. Longitud 10
RUTA MÁS CORTA: WinQSB / Network Modeling ‐ Shortest Path Problem
Encontrar la ruta más corta desde el vértice A hasta cada uno de los restantes vértices del grafo.

DIJKSTRA: Hallar la ruta más corta desde el vértice A hasta cada uno de los restantes vértices del
grafo ponderado. ¿El conjunto de caminos construidos constituye un árbol generador del grafo?
B C D E F G
A 5 6
B 5 6 7
C 2
D 5 9
E 7
F 9
Grafo del planteamiento:
Se eligen los nodos adyacentes que tienen menor

peso en la arista.
Se elige el nodo B
Vértice B ruta AB Longitud: 5
Se elige el nodo D
Vértice D ruta AD Longitud: 6

Se elige el nodo D
Vértice D ruta AD Longitud: 6
Se elige el nodo C
Vértice C ruta ABC Longitud: 10
Se elige el nodo E
Vértice E ruta ABE Longitud: 11
Se elige el nodo F
Vértice F ruta ADF Longitud: 11

Se elige el nodo G
Vértice F ruta ABCG Longitud: 12
El árbol de mínimos caminos desde A es:
El conjunto de caminos mínimos siempre es un árbol generador.

El algoritmo de Dijkstra devuelve el peso mínimo no el camino mínimo. Por lo que en general, el árbol
obtenido no tiene por qué ser mínimo.
En este caso, sí es un árbol generador.
No es necesario representar el grafo. Se puede elaborar la TABLA DE DIJKSTRA
B C D E F G
A 5 6
B 5 6 7
C 2
D 5 9
E 7
F 9
El algoritmo atribuye a cada vértice v una etiqueta t(v) , que es la longitud del camino ya
seleccionado. Se inicia la tabla con t(A) = 0 , t(v) = ∞ ∀ v ≠ A

Tiene dos vértices vecinos B y C que no cambian. Se elige el vértice con menor etiqueta, que es el B
con un peso de 5. Se añade al árbol y se marca la arista AB que se incorpora al árbol de caminos
mínimos.
A B C D E F G Vértice Arista
∞ ∞ ∞ ∞ ∞ ∞ A
•
5 ∞ 6 ∞ ∞ ∞ B AB
•
10 6 11 ∞ 12 D AD
•
10 11 11 12 C BC
•
11 11 12 E BE
•
11 12 F DF
•
12 G CG
Aparece una nueva fila: Se marca el vértice D con menor etiqueta (6) y se marca la arista AD , que
se incorpora al árbol de caminos mínimos.
Se toman todas las aristas B v, con el resto de vértices v no pertenecientes al árbol y se actualizan
etiquetas de los vértices adyacentes a B: mín ⎡⎣ t(v) , t(B) + p(B v) ⎤⎦
t(C) = ∞ > t(B) + p(BC) = 5 + 5 = 10 Cambia

t(E) = ∞ > t(B) + p(BE) = 5 + 6 = 11 Cambia
t(G) = ∞ > t(B) + p(BG) = 5 + 7 = 12 Cambia
Aparece una nueva fila: Se marca el vértice C que tiene menor etiqueta (10) y se marca la arista
BC , que se incorpora al árbol.
Se actualizan las etiquetas de los vértices adyacentes a D: mín ⎡⎣ t(v) , t(D) + p(D v) ⎤⎦
t(F) = ∞ > t(D) + p(DF) = 6 + 5 = 11 Cambia

t(G) = 12 < t(D) + p(DG) = 6 + 9 = 15 No Cambia
Aparece una nueva fila: Se marca el vértice E que tiene menor etiqueta (11) y se marca la arista
BE y se incorpora al árbol.
Se actualiza la etiqueta del vértice adyacente a C: mín ⎡⎣ t(v) , t(C) + p(C v) ⎤⎦
t(G) = 12 = t(C) + p(CG) = 10 + 2 = 12 No Cambia
Aparece una nueva fila: Se marca el vértice E , incorporando la arista DF al árbol.
Se actualiza la etiqueta del vértice adyacente a E: mín ⎡⎣ t(v) , t(E) + p(E v) ⎤⎦

t(G) = 12 < t(E) + p(EG) = 11 + 7 = 18 No Cambia
Vértice Camino Longitud

B AB 5
D AD 6
C ABC 10
E ABE 11
F ADF 11
G ABCG 12
DIJKSTRA ‐ RUTA MÁS CORTA: WinQSB / Network Modeling ‐ Shortest Path Problem

DIJKSTRA: Encontrar el camino de longitud
mínima de unas estaciones de metro entre
A y H.
Se eligen los nodos adyacentes que tienen

menor peso en la arista.
Vértice D
Ruta AD
Longitud: 5
Surgen candidatos, vértices B, C y E.

El camino mínimo resulta el vértice C.
Vértice C
Ruta ADC
Longitud: 9
Vértice B
Ruta ADCB
Longitud: 11
Vértice F
Ruta ADCBF
Longitud: 15

Vértice G
Ruta ADCBG
Longitud: 17
Vértice E
Ruta ADCBFE
Longitud: 18
Vértice H
Ruta ADCBFEH
Longitud: 23
El árbol de caminos mínimos es:
RUTA MÁS CORTA: WinQSB / Network Modeling ‐ Shortest Path Problem
Encontrar el camino de longitud mínima

de unas estaciones de metro entre A y H.

ALGORITMO DE DIJKSTRA EN GRAFOS DIRIGIDOS
Hallar la ruta más corta desde el vértice A hasta

cada uno de los restantes vértices del grafo dirigido.
El algoritmo de Dijkstra se inicia

partiendo del vértice A.
Los vértices adyacentes al vértice A son B y D,

se elige el vértice D por tener menor peso.
Vértice D ruta AD Peso: 2
Entre los posibles vértices no visitados, se

elige B por qué con un peso de 5 es el más
pequeño.
Vértice B ruta ADB Peso: 5
Entre los posibles vértices se elige C,

con peso 6 es el más pequeño.
Vértice C ruta ADBC Peso: 6

Finalmente,
se elige E con un peso de 7
Vértice E ruta ADE Peso: 7
El árbol de caminos mínimos

desde A es:
WinQSB / Network Modeling ‐ Shortest Path Problem
Hallar la ruta más corta desde el vértice A

hasta cada uno de los restantes vértices del
grafo dirigido.

DIJKSTRA: Una empresa de alquiler de automóviles está estudiando el plan de renovación de su
flota de coches para los próximos siete semestres (2020‐2023) de julio de 2020 a finales de 2023.
Al principio de cada semestre, enero a julio, se toma la decisión acerca de si debe mantener durante
ese semestre el coche o por el contrario si se debe remplazar por otro nuevo.
Suponiendo que cada coche se debe mantener al menos un año (dos semestres) y a lo sumo dos
años (cuatro semestres), determinar la política de reemplazo para ese período con el mínimo coste,
considerando los datos de la tabla adjunta que, muestra el coste estimado de reemplazamiento (en
euros) en función del semestre en el cual se adquiere y el número de semestres en servicio, para un
modelo determinado.
Dos semestres Tres semestres Cuatro semestres

Segundo semestre 2020 3.800 4.100 6.800
Primer semestre 2021 4.000 4.800 7.000
Segundo semestre 2021 4.200 5.100 7.200
Primer semestre 2022 4.800 5.700 ‐‐‐‐‐‐‐‐
Segundo semestre 2022 5.700 ‐‐‐‐‐‐‐‐ ‐‐‐‐‐‐‐‐
A = "segundo semestre 2020" D = "primer semestre 2022"

Denotando los sucesos: B = "primer semestre 2021 E = "segundo semestre 2022"
C = "segundo semestre 2021" F = "primer semestre 2023"
Una red que representa la situación descrita sería:
Aplicando el algoritmo de Dijkstra para hallar el camino mínimo desde el vértice A a todos los
demás, excluido B que no conecta con A

4,1 5,7
El camino mínimo es: A ⎯⎯ → D ⎯⎯ → G → Coste mínimo 9.800 euros
Por tanto, el coche comprado en el segundo semestre del año 2020, se cambia en el primer
semestre del año 2022 y se mantiene el segundo semestre del año 2023.
WinQSB / Network Modeling ‐ Shortest Path Problem

FLUJO MÁXIMO EN REDES
En teoría de grafos, un grafo dirigido con pesos es también conocido como una red.
Se determina el Flujo Máximo porque hay innumerables cuestiones prácticas donde lo más importante
es conocer la cantidad de flujo que pasa a través de una red.
El problema del Flujo Máximo consiste: Dado un grafo dirigido con pesos, G = (V, A,W), que representa
las capacidades máximas de los canales, un nodo de inicio S y otro de fin T en V , se trata de encontrar
la cantidad máxima de flujo que puede circular desde S hasta T.
Las aristas representan canales por los que puede circular cierta cosa: transmisión de datos, redes de
corriente eléctrica, líneas de oleoductos, agua, automóviles, etc.
Los pesos de las aristas representan la capacidad máxima de un canal: velocidad de una conexión,
cantidad máxima de tráfico, voltaje de una línea eléctrica, volumen máximo de agua, etc.
Los problemas de Flujo Máximo se pueden resolver mediante programas informáticos, por ejemplo, el
programa WinQSB con un conjunto de herramientas útiles para la investigación de operaciones. Dentro
de WinQSB se encuentra el modulo Network Modeling (Maximal Flow Problem), que permite resolver
problemas de Flujo Máximo con facilidad.
CONCEPTOS BÁSICOS:
Flujo: Circulación de unidades homogéneas de un lugar a otro.
Capacidad de flujo: Capacidad de unidades que pueden entrar por el nodo fuente y salir por el
nodo destino.
Origen o fuente de flujo: Nodo por el que ingresa el flujo.
Destino o Sumidero de flujo: Nodo por que sale el flujo.
Capacidades residuales: Capacidades restantes una vez que el flujo pasa el arco.
MÉTODO DE FORD‐FULKERSON: FLUJO MÁXIMO EN REDES

El método propone buscar caminos en los que se pueda aumentar el flujo hasta que se alcance el flujo
máximo, la idea es encontrar una ruta de penetración con un flujo positivo neto que una los nodos de
origen y destino.
El flujo es siempre positivo y con unidades enteras.
El flujo a través de un arco es menor o igual que la capacidad.
El flujo que entra en un nodo es igual al que sale de él.

PASOS PARA LA RESOLUCIÓN DE UN PROBLEMA DE FLUJO MÁXIMO
1. Identificar el nodo origen y de destino.
2. Partiendo del nodo de origen se elige el arco que posea mayor flujo
3. Identificar los nodos de transbordo.
4. Repetir el proceso como si el nodo intermediario fuera el nodo origen.
5. Calcular 'k' y las nuevas capacidades.
6. Obtenido el resultado se cambian las capacidades y se repite idéntico procedimiento desde el inicio.
⎧ C ≡ Capacidad
⎪ i j ≡ Índices de los nodos
⎪
C i j , ji = (C i − k , C j + k) ⎨
⎪ k ≡ Mínimo flujo que pasa por el nodo
⎪⎩ k = mín(capacidades de la ruta)
El Flujo Máximo que puede pasar del nodo origen hasta el nodo destino es la suma de las capacidades
∑ k de la ruta.
Calcular el flujo máximo del grafo:
MÉTODO DE FORD‐FULKERSON: Flujo máximo desde s, remplazando nuevas capacidades
k = mín(∞ ,30 ,20) = 20

C13 , 31 = (30 − 20 , 0 + 20) = (10 , 20)
C 35 , 53 = (20 − 20 , 0 + 20) = (0 , 20)

Ruta: 1 ‐ 2 ‐ 3 ‐ 4 ‐ 5 / Remplazando nuevas capacidades
k = mín(∞ ,20 ,40 ,10 ,20) = 10

C12 , 21 = (20 − 10 , 0 + 10) = (10 , 10)
C 23 , 32 = (40 − 10 , 0 + 10) = (30 , 10)
C 34 , 43 = (10 − 10 , 5 + 10) = (0 , 15)
C 45 , 54 = (20 − 10 , 0 + 10) = (10 , 10)
Ruta: 1 ‐ 2 ‐ 5 / Remplazando nuevas capacidades
k = mín(∞ ,10 ,20) = 10

C12 , 21 = (10 − 10 , 10 + 10) = (0 , 20)
C 25 , 52 = (20 − 10 , 0 + 10) = (10 , 10)

Ruta: 1 ‐ 3 ‐ 2 ‐ 5 / Remplazando nuevas capacidades
k = mín(∞ ,10 ,10 ,10) = 10

C13 , 31 = (10 − 10 , 20 + 10) = (0 , 30)
C 32 , 23 = (10 − 10 , 30 + 10) = (0 , 40)
C 25 , 52 = (10 − 10 , 10 + 10) = (0 , 20)
Finalmente, Ruta: 1 ‐ 4 ‐ 5 / Remplazando nuevas capacidades
k = mín(∞ ,10 ,10) = 10

C14 , 41 = (10 − 10 , 0 + 10) = (0 , 10)
C 45 , 54 = (10 − 10 , 10 + 10) = (0 , 20)
El Flujo máximo se obtiene al sumar todas las nuevas capacidades:

∑ k = 20 + 10 + 10 + 10 + 10 = 60

Network Modeling / Maximal Flow Problem
Muchos problemas pueden ser modelados mediante una red en donde los arcos limitan la cantidad
de un producto que se puede enviar. En estas situaciones, frecuentemente se transporta la máxima
cantidad de flujo desde un punto de partida llamado fuente hacia un punto final denominado pozo.

RESOLUCIÓN ALGORITMO DE FORD ‐ FULKERSON
La red esta formada por 5 nodos, 7 aristas y una función capacidad. Se comienza poniendo todos los
flujos a 0.
Camino de aumento: Camino sin nodos que une s con t

Cuello de botella: Mínimo de las capacidades residuales de un camino de aumento.

Se busca un camino de aumento: s ‐ 2 ‐ t
Se actualiza la red residual
Se busca otro camino de aumento: s ‐ 4 ‐ 3 ‐ t

Se actualiza la red residual.
Se busca otro camino de aumento: s ‐ 4 ‐ t
Se actualiza la red residual.
El algoritmo de Ford ‐ Fulkerson finaliza porque ya no se pueden encontrar más caminos en

aumento. El flujo máximo es ∑ f(arista) = 9 + 9 = 18


El Flujo máximo de s hasta t es 18.
FORD ‐ FULKERSON: Obtener el máximo

flujo que se puede llevar del nodo 0 al
nodo T

El Flujo máximo de 0 hasta T es 14.

FORD ‐ FULKERSON: Una aerolínea española, con el objetivo de maximizar beneficios, ha contratado a
un estudiante de Gestión Aeronáutica para realizar un estudio sobre el máximo flujo de vuelos que puede
hacer en su ruta Madrid ‐ Nueva York.
Según se refleja en el grafo, la aerolínea tiene vuelos en los siguientes destinos: Madrid ‐ Barcelona ‐ Las
Palmas de Gran Canarias ‐ Londres Heathrow ‐ Miami ‐ Nueva York.
Cada nodo representa el código de

aeropuertos donde hace escala:
1 ‐ Madrid (MAD)
2 ‐ Barcelona (BCN)
3 ‐ Las Palmas de Gran Canaria (LPA)
4 ‐ Londres‐Heathrow (LHR)
5 ‐ Miami (MIA)
6 ‐ Nueva York (JFK)
Calcula el flujo máximo por el Método de Ford‐Fulkerson.
Solución:
Ruta: Madrid ‐ Miami ‐ Nueva York (1 ‐ 5 ‐ 6)
b = mín (10 , 20) = 10

Flujo Máximo = 0 + 10 =10
C15 , 51 = (10 – 10, 5 + 10) = (0, 15)
C56 , 65 = (20 – 10, 5 + 10) = (10,15)
Ruta: Madrid ‐ Barcelona ‐ Nueva York (1 ‐ 2 ‐ 6)
b = mín (15 , 40) = 15

Flujo Máximo = 10 + 15 = 25
C12 , 21 = (15 – 15, 0 + 15) = (0, 15)
C26 , 62 = (40 – 15, 0 + 15) = (25, 15)

Ruta: Madrid ‐ Las Palmas ‐ Miami ‐ Londres ‐ Nueva York (1 ‐ 3 ‐ 5 ‐ 4 ‐ 6)
b = mín (30, 10, 25, 20) = 10

C13 , 31 = (30 – 10, 0 + 10) = (20, 10)
C35 , 53 = (10 – 10, 0 + 10) = (0, 10)
C54 , 45 = (25 – 10, 5 + 10) = (15, 15)
C46 , 64 = (20 – 10, 0 + 10) = (10, 10)
Ruta: Madrid ‐ Las Palmas ‐ Nueva York (1 ‐ 3 ‐ 6)
b = mín (20, 35) = 20

C13 , 31 = (20 – 20, 10 + 20) = (0, 30)
C36 , 63 = (35 – 20, 5 + 20) = (15, 25)
El algoritmo ha finalizado porque desde Madrid todos los aviones salen con capacidad 0.
El Flujo Máximo total de vuelos es 55.
Resultado con WinQSB:


FLUJO MÁXIMO EN REDES: PROBLEMA DE PROGRAMACIÓN LINEAL
El Problema del Flujo Máximo es similar al Problema de Ruta más Corta, ahora se busca determinar el
flujo máximo entre un nodo fuente y un nodo destino, que están enlazados a través de una red, con
arcos de capacidad finita.
Los números asignados a cada uno

de los arcos representan los flujos
máximos o capacidades
correspondientes a cada arco.
xi j ≡ Unidades que fluyen desde

el nodo i al nodo j.
Función Objetivo: Maximizar las unidades que salen del nodo de origen (1) a los nodos que esta
conectada (2, 4 y 5) o alternativamente maximizar las unidades que llegan al nodo de destino (8) desde
los nodos que conectan a él (3, 6 y 7).
Alternativas: Maximizar z = x12 + x14 + x15 o bien Maximizar z = x 38 + x 68 + x 78
Restricciones:
Flujo Máximo: La cantidad de unidades que sale de cada nodo de origen a un nodo de destino no
puede superar la capacidad del arco. Por ejemplo, del nodo 1 al nodo 2 sólo se pueden enviar 7
unidades.
⎧ x12 ≤ 7 x14 ≤ 25 x15 ≤ 5 x23 ≤ 10 x 38 ≤ 18

⎨
⎩ x 43 ≤ 20 x 46 ≤ 9 x 56 ≤ 4 x 57 ≤ 15 x 68 ≤ 40 x 78 ≤ 9
Balance de Flujo en los Nodos: Las unidades que entran a un nodo debe de ser igual a las unidades
que salen. Por ejemplo, el número de unidades que se envían del nodo 1 al nodo 4 debe ser igual a
las que salen del nodo 4 (se envían al nodo 3 y al nodo 6).
⎧ x12 = x23 ⎧ x12 − x23 = 0

⎪x = x + x ⎪x − x − x = 0
⎪ 14 43 46 ⎪ 14 43 46
⎪⎪ x15 = x 56 + x 57 ⎪⎪ x15 − x 56 − x 57 = 0
⎨ → ⎨
⎪ x23 + x 43 = x 38 ⎪ x23 + x 43 − x 38 = 0
⎪ x 46 + x 56 = x 68 ⎪ x 46 + x 56 − x 68 = 0
⎪ ⎪
⎪⎩ x 57 = x 78 ⎪⎩ x 57 − x 78 = 0
No Negatividad e Integralidad: Las variables de decisión tienen la condición de no negatividad

(xi j ≥ 0) , adicionalmente se exige que éstas adopten valores enteros. Si se omite esta condición
podría dar un problema de Programación Lineal.

FLUJO MÁXIMO: PROGRAMACIÓN LINEAL

El Flujo máximo que puede llegar al nodo de destino son 32 unidades. Los valores de las celdas en
color amarillo representan la solución óptima, es decir, la cantidad de unidades que fluyen en cada
combinación de un nodo origen ‐ destino.

PROGRAMACIÓN LINEAL:
Encontrar el Flujo máximo de la
red.
Función Objetivo: Maximizar las unidades que salen del nodo de origen (1) a los nodos que esta
conectada (2 y 3) o alternativamente maximizar las unidades que llegan al nodo de destino (7) desde los
nodos que conectan a él (4, 5 y 6).
Alternativas: Maximizar z = x12 + x13 o bien Maximizar z = x 47 + x 57 + x 67
Restricciones:
Flujo Máximo: La cantidad de unidades que sale de cada nodo de origen a un nodo de destino no
puede superar la capacidad del arco.
⎧ x12 ≤ 10 x13 ≤ 10 x23 ≤ 1 x 32 ≤ 1 x26 ≤ 6 x 36 ≤ 4 x 63 ≤ 4 x24 ≤ 8

⎨
⎩ x 64 ≤ 3 x 46 ≤ 3 x 35 ≤ 12 x 65 ≤ 2 x 56 ≤ 2 x 57 ≤ 8 x 47 ≤ 7 x 67 ≤ 2
Balance de Flujo en los Nodos: Las unidades que entran a un nodo debe de ser igual a las unidades
que salen.
Nodo 2: x12 + x 32 − x23 − x26 − x24 = 0

Nodo 3: x13 + x23 + x 63 − x 32 − x 36 − x 35 = 0
Nodo 4: x24 + x 64 − x 47 − x 46 = 0
Nodo 5: x 35 + x 65 − x 56 − x 57 = 0
Nodo 6: x26 + x 46 + x 36 + x 56 − x 65 − x 63 − x 64 − x 67 = 0
Nodo 7: x 47 + x 67 + x 57 − x12 − x13 = 0
No Negatividad e Integralidad: Las variables de decisión tienen la condición de no negatividad

(xi j ≥ 0) , adicionalmente se exige que éstas adopten valores enteros. Si se omite esta condición
podría dar un problema de Programación Lineal.

FLUJO MÁXIMO: PROGRAMACIÓN LINEAL

El Flujo máximo que puede llegar al nodo de destino son 17 unidades. Los valores de las celdas en
color amarillo representan la solución óptima, es decir, la cantidad de unidades que fluyen en cada
combinación de un n‐odo origen ‐ destino.

ALGORITMO DE PRIM: ÁRBOL DE EXPANSIÓN MÍNIMA
Se utiliza para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y con aristas
etiquetadas.
El algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el
peso total de las aristas en el árbol es el mínimo posible.
Si el grafo no es conexo, el algoritmo encuentra el árbol recubridor mínimo para una de las
componentes conexas (que forman el grafo no conexo).
El algoritmo va incrementando continuamente el tamaño del árbol, comienza con un vértice inicial
(elegido arbitrariamente) al que se van añadiendo sucesivamente vértices cuya distancia a los anteriores
es mínima.
Esto conlleva que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya
pertenecen al árbol.
El algoritmo termina cuando el árbol recubridor mínimo está completamente construido, es decir,
cuando no quedan más vértices que agregar.
Informalmente el algoritmo se puede describir:
y Iniciar un árbol con un único vértice, elegido arbitrariamente del grafo.
y Aumentar el árbol por un lado. Un lado es la unión entre dos vértices: De las posibles uniones que
pueden conectar el árbol a los vértices que no están aún en el árbol, encontrar el lado de menor
distancia y unirlo al árbol.
y Repetir la secuencia (hasta que todos los vértices pertenezcan al árbol)
Calcular el peso que transporta el árbol de expansión mínima del grafo adjunto
Inicialmente el grafo ponderado no es un árbol

(para serlo se requiere que no hubiera ciclos y en
este caso sí hay).
Comienza el proceso eligiendo arbitrariamente al
vértice D como punto de partida.

Los números cerca de las aristas indican el peso.
Se elige arbitrariamente el vértice D como punto de
partida.
El vértice más cercano a D es el vértice A, a una
distancia de 5.
Se marca la arista DA.
El vértice más cercano al vértice D o al vértice A

es el vértice F, a una distancia de 6.
Adviértase que el vértice B esta una distancia
de 7 del vértice A.
Se marca la arista DF.
El algoritmo continúa, el vértice más cercano a

los vértices A y F es el vértice B, a una distancia 7
del vértice A.
Se marca la arista AB.
En esta situación, la arista DB se anula porque
sus dos extremos ya están en el árbol y, en
consecuencia, no podrá ser utilizada.
Los vértices más cercanos a B y F son los vértices

C, E y G.
Se elige el vértice E que se encuentra a una
distancia 7 de B.
Se marca la arista BE.

Desaparecen otras dos aristas, ED y EF porque ambos
vértices que unen fueron agregados al árbol.
Los vértices más cercanos a E y F son C y G.

Se elige el vértice C que se encuentra a una
distancia 5 de del vértice E.
Se marca la arista EC.
Desaparece la arista BC porque los vértices

fueron agregados al árbol.
El único vértice pendiente G se encuentra más

cercano al vértice E, a una distancia de 9.
Se marca la arista EG.

Desaparece la arista FG porque los vértices fueron
agregados al árbol.
El algoritmo termina al estar marcados todos los
vértices.
El árbol de expansión mínima tiene un peso de 39.
PRIM: Network Modeling / Minimal Spanning Tree

PRIM: Construir un árbol generador del grafo
ponderado adjunto utilizando el algoritmo de Prim.
El algoritmo de Prim comienza con un vértice cualquiera, se elige arbitrariamente el vértice A y se

construye el árbol T con A como único vértice.
En pasos sucesivos, se va añadiendo al árbol parcial T la arista de menor peso que une un vértice de T
con un vértice que todavía no está en T.
Cuando una arista tenga sus dos extremos en el árbol no podrá ser utilizada.
El algoritmo termina cuando todos los vértices se encuentren seleccionados, es decir, cuando se han
añadido (n − 1) aristas.
Finalmente, el árbol de expansión mínimo lleva un peso.
El grafo ponderado de partida no es un árbol, ya que para

serlo requiere que no tuviera ciclos.
Los números cerca de las aristas indican los pesos.
Se ha elegido arbitrariamente el vértice A como punto de
partida. El segundo vértice más cercano al vértice A que se
encuentra a menor distancia es el vértice B.
Se marca la arista AB.
El próximo vértice a elegir que sea más cercano al

vértice A o al vértice B es el vértice C, a una distancia 3.
Se marca la arista BC.

El algoritmo continúa. El vértice F, que está a una distancia
4 de C, es el siguiente marcado.
En este punto la arista BF desaparece porque ambos

vértices fueron agregados al árbol T.
En esta línea, también desaparece la arista AF, al ser los
vértices agregados al árbol.
Aquí hay que elegir entre C (distancia 5 de D), o los vértices
D o E a distancias respectivas del vértice F de 7 o 6.
Se marca el vértice CD.
En este punto la arista DF desaparece porque ambos

vértices fueron agregados al árbol T.
V(T) = {A, B, C, F, D}
Se elige el vértice E que se encuentra a una distancia 4

de D.
Se marca el vértice DE.

La arista EF desaparece porque ambos vértices fueron
agregados al árbol T.
Por el mismo criterio desaparece la arista EA.
El árbol generador de expansión mínima se muestra

en la figura adjunta. En este caso con un peso de 20.
V(T) = {A, B, C, D, E, F}

PRIM: Encontrar el árbol de expansión mínima.
El algoritmo de Prim comienza con un vértice cualquiera, se elige arbitrariamente el vértice O y se

construye el árbol T con O como único vértice.
En pasos sucesivos, se va añadiendo al árbol parcial T la arista de de menor peso que une un vértice de T
con un vértice que todavía no está en T. Cuando una arista tenga sus dos extremos en el árbol no podrá
ser utilizada.
El segundo vértice más cercano a O es el vértice A

(a una distancia de 5), el vértice C está a una
distancia de 7.
Se marca la arista OA.
El siguiente vértice más cercano a elegir entre O

o A es el vértice B, a una distancia 5.
Se marca la arista AB, mientras que la arista OB
desaparece porque formaría el ciclo OAB.
El siguiente vértice más cercano a elegir entre O

o B es el vértice C, a una distancia 3.
Se marca la arista BC, desaparece la arista OC
porque formaría el ciclo OABC.

El vértice más cercano a B o C es el vértice E
(distancia 6) del vértice B.
Se marca la arista BE.
Desaparece la arista CE porque formaría el ciclo BCE.
El siguiente vértice más cercano a elegir entre A y E

es el vértice D, a una distancia 3 del vértice E.
Se marca la arista ED, desaparece la arista BD porque
formaría el ciclo BED.
También desaparece la arista AD porque formaría

el ciclo ABED.
El siguiente vértice más cercano a elegir entre D y E

es el vértice D, a una distancia 8 del vértice T.
Desaparece la arista ET porque formaría el ciclo
DET.
El algoritmo termina, todos los vértices están

marcados, y se obtiene el árbol de expansión
mínima con un peso de 30.

PRIM (ÁRBOL EXPANSIÓN MÍNIMA)
Una empresa aeronáutica decide instalar un
sistema de distribución que permita enviar
contenedores a ocho provincias españolas,
considerando la posibilidad de envío no directo.
Los costes en cientos de euros se reflejan en la
tabla adjunta. Calcular el mínimo coste.
El algoritmo de Prim comienza eligiendo

un vértice cualquiera.
Se elige arbitrariamente el vértice 5 y se
construye el árbol con 5 como único
vértice.
A continuación, se añade la arista de
menor peso que une el vértice.
El segundo vértice más cercano a 5 es el
vértice 6 (a una distancia de 10). Se marca
la arista 5‐6.
El siguiente vértice más cercano a elegir

entre 5 y 6 es el vértice 2, a una distancia
de 11 del vértice 6.
Se marca la arista 6‐2, mientras que la
arista 2‐5 desaparece porque formaría un
ciclo.

Grafo resultante:
El siguiente vértice más cercano a

elegir entre 6 o 2 es el vértice 4, a
una distancia de 9 del vértice 2.
Se marca la arista 2‐4 y
desaparecen las aristas 4‐6 y 4‐5
porque formarían un ciclo
Grafo resultante:

El vértice más cercano a 2 o 4 es el vértice 3,
a una distancia de 8 del vértice 4.
Se marca la arista 4‐3 a una distancia de 8 y
desaparece las aristas 3‐2 , 3‐6 y 3‐5 para no
formar ciclos.
Grafo resultante:
El siguiente vértice más cercano a elegir entre

2 o 3 es el vértice 7, a una distancia de 10 del
vértice 2.
Se marca la arista 2‐7 y desaparecen las

aristas 7‐3 , 7‐6 , 7‐5 y 7‐4 para no formar
ciclos.

Grafo resultante:
El siguiente vértice más cercano es el 1, a

una distancia de 14 del vértice 4.
aristas 1‐7, 1‐3 , 1‐2 , 1‐5 y 1‐6 para no
formar ciclos.
Finalmente, se elige el vértice 8, a una

distancia de 13 del vértice 1.
aristas 8‐2 , 8‐5 , 8‐6 , 8‐3 , 8‐4 y 8‐7 para
no formar ciclos

El algoritmo finaliza, todos los vértices están
marcados.
Longitud o peso mínimo de la distribución:
8 + 9 + 10 + 10 + 11 + 13 + 14 = 75
Coste mínimo de la distribución:
75 x 100 = 7.500 euros.

ALGORITMO DE KRUSKAL: ÁRBOL DE EXPANSIÓN MÍNIMA
Algoritmo para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un
subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de
todas las aristas del árbol es mínimo.
Si el grafo fuera no conexo busca un bosque expandido mínimo (árbol expandido mínimo para cada
componente conexa).
Informalmente el algoritmo se puede describir:
y Se crea un bosque (un conjunto de árboles) donde cada vértice del grafo es un árbol separado.
y Se crea un conjunto C que contenga a todas las aristas del grafo.
y Mientras el conjunto C sea no vacío:
♦ Se elimina la arista de peso mínimo de C
♦ Si la arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un
solo árbol. En caso contrario, se desecha la arista.
♦ El algoritmo finaliza cuando el bosque tiene un solo componente, que forma un árbol de expansión
mínima del grafo.
KRUSKAL: Calcular el peso que transporta el

árbol de expansión mínima del grafo.
Inicialmente el grafo ponderado no es un árbol (para serlo se requiere que no hubiera ciclos y en este caso
sí hay).
Comienza el proceso eligiendo las aristas con menor peso. En este caso, las aristas más cortas, con un
peso de 5 , son AD y CE.
Se elige arbitrariamente la arista AD y se marca.
Ahora es CE la arista más pequeña que no forma

ciclos, con un peso de 5.
Se marca la arista CE como segunda arista.

La siguiente arista con menor peso que no forma
ciclos es DF con un peso de 6
Se marca la arista DF como tercera arista.

ç
Las siguientes aristas más pequeñas que no

forman ciclos, con un peso de 7, son AB y BE.
Se elige arbitrariamente AB y se marca.
Se elimina la arista BD porque formaría un ciclo

ABD si fuera elegida.
El algoritmo continua, se marca la arista más
pequeña BE, que no forma ciclos, con un peso
de 7.

Se elimina la arista BC porque formaría un ciclo
con BCE.
Por el mismo criterio se eliminan otras dos
aristas:
La arista DE porque formaría ciclo con DEBA.
La arista FE porque formaría ciclo con FEBAD.
El algoritmo finaliza eligiendo la arista más

pequeña que no forma ciclo.
Se elige la arista EG con un peso de 9.
Se elimina la arista FG porque formaría ciclo.
El árbol de expansión mínima tiene un peso

de 39.

KRUSKAL: Construir un árbol generador del
grafo ponderado adjunto utilizando el
algoritmo de Kruskal.
El algoritmo de Kruskal comienza ordenando las aristas por su peso de menor a mayor. Posteriormente,
en ese orden, se van añadiendo aristas al árbol si no forman ciclo con las previamente añadidas.
El grafo ponderado de partida no es un árbol, ya que para

serlo requiere que no tuviera ciclos.
BC es la arista más corta, con peso 3.
Se marca la arista BC.
Las aristas AB, CF y DE son las aristas más cortas, con peso
4. Se elige arbitrariamente la arista AB.
En el siguiente paso, quedan como aristas más cortas CF
y DE.
Se elige arbitrariamente la arista CF.

El proceso continúa, la arista FB debe eliminarse porque
formaría el ciclo BCF.

Antes de continuar con el algoritmo se tiene que eliminar
la arista AF porque formaría el ciclo ABCF.
La siguiente arista más corta es DE, con peso 4.

Se marca DE.
La siguiente arista más corta es CD, con peso 5.

Se marca DE.
Al marcar la arista DE desaparece la arista DF y la

arista EF.
La arista DF formaría el ciclo CDF.
La arista EF formaría el ciclo CDEF.

Finalmente, queda la arista AE que tiene que desaparecer
porque formaría el ciclo del grafo.
Se ha encontrado el árbol de expansión mínima o árbol

generador mínimo, que transporta un peso de 20.
V(T) = {A, B, C, D, E, F}
KRUSKAL: Network Modeling / Minimal Spanning Tree

KRUSKAL: Una empresa decide instalar un sistema de
distribución que permita enviar sus artículos a diez
provincias españolas, considerando la posibilidad de envío
no directo. Los costes en cientos de euros se adjuntan en el
grafo adjunto, ¿entre qué lugares debe instalar el canal de
suministro para minimizar el coste total?.
Si el coste de cada conexión se incrementase 50 euros, ¿varía
la respuesta anterior?
Se van eligiendo las aristas más cortas (con menor peso) y se van resaltando, cuidando que al seleccionar
las aristas no formen un ciclo. Una posible secuencia sería:

El coste mínimo de la distribución es de
67 x 100 = 6700 euros.
De otra parte, si el coste de la conexión se incrementa 50 euros, el trazado no varía, aunque el coste
se incrementaría 9 x 50 = 450 euros.
El coste mínimo de la distribución sería 6700 + 450 = 7150 euros.
Se advierte que empleando el algoritmo de Kruskal el proceso hasta encontrar el árbol expandido
mínimo es tedioso, que va haciéndose más complejo a medida que aumentan los vértices del Grafo.

DIJKSTRA‐KRUSKAL: La red de
comunicaciones de un aeropuerto
responde a la red adjunta.
a) Encontrar la ruta más corta (peso
mínimo) desde el vértice A hasta el
vértice G. ¿Es única la ruta?
b) Encontrar un árbol generador de peso mínimo utilizando el algoritmo de Kruskal. ¿es euleriano del
grafo?. En caso afirmativo, encontrar un circuito euleriano del grafo.
a) Aplicando el algoritmo de Dijkstra se

eligen los nodos adyacentes que tienen
menor peso en la arista, resultando la red
que figura.
El conjunto de caminos mínimos siempre
es un árbol generador.
El camino más corto entre los nodos A y G tiene una longitud de 7: A ‐ B ‐ E ‐ G

Hay otro camino de longitud 7: A ‐ H ‐ G
b) Utilizando el algoritmo de Kruskal se comienza eligiendo las aristas que tienen menor peso, es decir,
las aristas más cortas, no formando ciclos, formando un conjunto que contenga a todas las aristas del
grafo (el algoritmo termina cuando todos los vértices están marcados).
8 nodos → 7aristas
El árbol generador mínimo tiene un peso de 13: 1 + 2 + 1 + 3 + 1 + 3 + 2 = 13

Un grafo euleriano es un camino que contiene todas las aristas y recorre cada arista una sola vez. Un
grado euleriano debe ser conexo y todos los vértices deben tener grado par, a lo sumo dos vértices con
grado impar.

El grafo es euleriano porque todos sus vértices son de grado par.
El ciclo euleriano (circuito euleriano) es un camino euleriano que comienza y termina en el mismo
vértice. Todos los vértices deben ser de grado par.
⎧B − C − D − B
⎪
Para obtener un circuito euleriano se forman ciclos cerrados: ⎨ A − B − E − F − H − A
⎪
⎩A − E − G − H − E − D − A
B−C −D −B
A −B−E−F−H− A
A −E−G−H−E−D− A
Uniendo los ciclos, se obtiene el circuito cerrado: A − E − G − H − E − D − A − B − C − D − B − E − F − H − A

DIJKSTRA ‐ RUTA MÁS CORTA: WinQSB / Network Modeling ‐ Shortest Path Problem

b) Para aplicar el algoritmo de Kruskal: WinQSB / Network Modeling (NET) / Minimal Spanning Tree

El árbol generador mínimo tiene un peso de 13:
1 + 2 + 1 + 3 + 1 + 3 + 2 = 13

KRUSKAL (ÁRBOL EXPANSIÓN MÍNIMA)
Una empresa aeronáutica decide instalar un
sistema de distribución que permita enviar
contenedores a ocho provincias españolas,
considerando la posibilidad de envío no directo.
Los costes en cientos de euros se reflejan en la
tabla adjunta. Calcular el mínimo coste.
Se van seleccionando las aristas mas

cortas (con menor peso), ya que hay que
calcular el mínimo coste. Se presta
atención a las aristas marcadas para no
formar un ciclo.
Se comienza seleccionando el menor
valor, en este caso el 8, que une el nodo
3 y 4.
A continuación, se selecciona la arista

que une los nodos 2 y 4.

Se selecciona la arista que une los nodos
5 y 6.
Se unen los nodos 2 y 6.
Se unen los nodos 1 y 8.

Finalmente, se selecciona la
arista que une los nodos 3 y 8.
Longitud o peso mínimo de la distribución:

8 + 9 + 14 + 10 + 11 + 13 + 10 = 75
Coste mínimo de la distribución:
75 x 100 = 7.500 euros.

1 2 3 4 5 6 7 8
KRUSKAL (ÁRBOL EXPANSIÓN MÍNIMA) 1 ⎡− 20 18 14 19 15 16 13 ⎤
2 ⎢ 20 − 16 9 12 11 10 16 ⎥⎥
Una empresa aeronáutica decide instalar un ⎢
3 ⎢18 16 − 8 22 12 13 14 ⎥
sistema de distribución que permita enviar ⎢ ⎥
contenedores a ocho provincias españolas, 4 ⎢14 9 8 − 13 16 21 17 ⎥
considerando la posibilidad de envío no directo. 5 ⎢ 19 12 22 13 − 10 17 24 ⎥
⎢ ⎥
Los costes en cientos de euros se reflejan en la 6 ⎢ 15 11 12 16 10 − 13 18 ⎥
tabla adjunta. Calcular el coste mínimo. 7 ⎢16 10 13 21 17 13 − 14 ⎥
⎢ ⎥
8 ⎣⎢ 13 16 14 17 24 18 14 − ⎦⎥
GRAFO ADJUNTO
1 2 3 4 5 6 7 8
1 ⎡− 20 18 14 19 15 16 13 ⎤
Para obtener el árbol de expansión mínima se ⎢20 − 16 9 12 11 10 16 ⎥⎥
2 ⎢
selecciona el menor elemento de la red. 3 ⎢18 16 − 8 22 12 13 14 ⎥
⎢ ⎥
En este caso es el 8, al existir dos casillas con 4 ⎢14 9 8 − 13 16 21 17 ⎥
ese número, se selecciona uno cualquiera. ⎢ ⎥
5
⎢19 12 22 13 − 10 17 24 ⎥
distancia menor = d1 = 8 6 ⎢15 11 12 16 10 − 13 18 ⎥
⎢ ⎥
7 ⎢16 10 13 21 17 13 − 14 ⎥
8 ⎢13 16 14 17 24 18 14 − ⎥⎦
⎣

1 2 3 4 5 6 7 8
Se tachan las casillas (3, 4) y (4, 3) que es 1 ⎡− 20 18 14 19 15 16 13 ⎤
donde se encuentra ese mínimo. 2 ⎢⎢20 − 16 9 12 11 10 16 ⎥⎥
Marcando las columnas 3 y 4, donde se han 3 ⎢18 16 − 22 12 13 14 ⎥
⎢ ⎥
eliminado esas casillas. 4 ⎢14 9 − 13 16 21 17 ⎥
5 ⎢19 12 22 13 − 10 17 24 ⎥
Al no estar marcadas todas las columnas, el ⎢ ⎥
proceso sigue. 6 ⎢15 11 12 16 10 − 13 18 ⎥
7 ⎢16 10 13 21 17 13 − 14 ⎥
⎢ ⎥
8 ⎢⎣13 16 14 17 24 18 14 − ⎥⎦
1º 2º
1 2 3 4 5 6 7 8
1 ⎡− 20 18 14 19 15 16 13 ⎤ Se selecciona el menor elemento de las columnas no
⎢ ⎥
2 ⎢20 − 16
JJG 9 12 11 10 16 ⎥ marcadas, el elemento 9 de la casilla (2, 4).
⎢ ⎥
3 ⎢18 16G
JJJ − 22 12 13 14 ⎥ Se tachan las casillas (2, 4) y (4, 2) que es donde se
4 ⎢14 9 − 13 16 21 17 ⎥ encuentra ese mínimo.
⎢ ⎥
5 ⎢19 12 22 13 − 10 17 24 ⎥ Asimismo, se tachan las casillas (3, 2) y (2, 3) para
6 ⎢15 11 12 16 10 − 13 18 ⎥⎥ evitar ciclos (elemento 16).
⎢
7 ⎢16 10 13 21 17 13 − 14 ⎥
⎢ ⎥ distancia menor = d2 = 9
8 ⎣13 16 14 17 24 18 14 −⎦
1º 2º
1 2 3 4 5 6 7 8
1 ⎡− 20 18 14 19 15 16 13 ⎤
2 ⎢20 − 12 11 10 16 ⎥⎥
⎢
3 ⎢18 − 22 12 13 14 ⎥
⎢ ⎥
Marcando la columna 2 que es donde se ha 4 ⎢14 − 13 16 21 17 ⎥
eliminado la casilla (2, 3). 5 ⎢19 12 22 13 − 10 17 24 ⎥
⎢ ⎥
6 ⎢15 11 12 16 10 − 13 18 ⎥
7 ⎢16 10 13 21 17 13 − 14 ⎥
⎢ ⎥
8 ⎣⎢13 16 14 17 24 18 14 − ⎦⎥
3º 1º 2º

1 2 3 4 5 6 7 8
Se selecciona el menor elemento de las 1 ⎡− 20 18 14 19 15 16 13 ⎤

⎢ ⎥
columnas no marcadas, que es el elemento 2 ⎢20 − 12 11 10 16 ⎥
⎢ ⎥
10 de la casilla (7, 2). 3 ⎢18 − 22 12 13 14 ⎥
⎢ − 17 ⎥
Se tachan las casillas (7, 2), (7, 3) y (7, 4), así 4 ⎢14 13 16 21
⎥
como sus casillas simétricas: 5 ⎢19 12 22 13 − 10 17 24 ⎥
⎢ − 18 ⎥⎥
(2, 7), (3, 7) y (4, 7) para evitar ciclos. 6 ⎢15 11 12 16 10 13
7 ⎢16 10 13 21 17 13 − 14 ⎥
distancia menor = d3 = 10 ⎢ ⎥
8 ⎢⎣13 16 14 17 24 18 14 − ⎥⎦
3º 1º 2º
1 2 3 4 5 6 7 8
1 ⎡− 20 18 14 19 15 16 13 ⎤
2 ⎢20 − 12 11 16 ⎥⎥
⎢
3 ⎢18 − 22 12 14 ⎥
⎢ ⎥
Marcando la columna 7 que es donde se ha 4 ⎢14 − 13 16 17 ⎥
eliminado la casilla (7, 2). 5 ⎢19 12 22 13 − 10 17 24 ⎥
⎢ ⎥
6 ⎢15 11 12 16 10 − 13 18 ⎥
7 ⎢16 17 13 − 14 ⎥
⎢ ⎥
8 ⎣⎢13 16 14 17 24 18 14 − ⎦⎥
3º 1º 2º 4º
1 2 3 4 5 6 7 8
1 ⎡− 20 18 14 19 15 16 13 ⎤
Se selecciona el menor elemento de las ⎢ ⎥
columnas no marcadas, que es el elemento 10 2 ⎢20 − 12 11 16 ⎥
⎢ − 14 ⎥
de la casilla (5, 6). 3 ⎢18 22 12
⎥
4 ⎢14 − 13 16 17 ⎥
Se tachan las casillas (5, 6), (5, 2), (5, 3), (5, 4) y ⎢ ⎥
(5, 7), así como sus casillas simétricas: (6, 5), 5 ⎢19 12 22 13 − 10 17 24 ⎥
⎢ ⎥
(2, 5), (3, 5), (4, 5) y (7, 5) para evitar ciclos. 6 ⎢15 11 12 16 10 − 13 18 ⎥
⎢ ⎥
distancia menor = d4 = 10 7 ⎢16 17 13 − 14 ⎥
⎢ − ⎥⎦
8 ⎣13 16 14 17 24 18 14
3º 1º 2º 4º

1 2 3 4 5 6 7 8
1 ⎡− 20 18 14 19 15 16 13 ⎤
2 ⎢20 − 11 16 ⎥⎥
⎢
3 ⎢18 − 12 14 ⎥
⎢ ⎥
Marcando la columna 5 que es donde se 4 ⎢14 − 16 17 ⎥
ha seleccionado la casilla (5, 6). 5 ⎢19 − 24 ⎥
⎢ ⎥
6 ⎢15 11 12 16 − 13 18 ⎥
7 ⎢16 13 − 14 ⎥
⎢ ⎥
8 ⎣⎢13 16 14 17 24 18 14 − ⎦⎥
3º 1º 2º 5º 4º
1 2 3 4 5 6 7 8
1 ⎡− 20 18 14 19 15 16 13 ⎤
Se selecciona el menor elemento de las ⎢ ⎥
2 ⎢20 − 11 16 ⎥
columnas no marcadas, que es el elemento 11
⎢ − 14 ⎥
de la casilla (6, 2). 3 ⎢18 12
⎥
⎢ − 17 ⎥
Se tachan las casillas (6, 2), (6, 3), (6, 4) y (6, 7), 4 ⎢14 16
⎥
5 ⎢19 − 24 ⎥
así como sus casillas simétricas: (2, 6), (3, 6),
⎢ ⎥
(4, 6) y (7, 6) para evitar ciclos. 6 ⎢15 11 12 16 − 13 18 ⎥
distancia menor = d5 = 11 7 ⎢16 13 − 14 ⎥
⎢ ⎥
8 ⎢⎣13 16 14 17 24 18 14 − ⎥⎦
3º 1º 2º 5º 4º
1 2 3 4 5 6 7 8
1 ⎡− 20 18 14 19 15 16 13 ⎤
2 ⎢20 − 16 ⎥⎥
⎢
3 ⎢18 − 14 ⎥
⎢ ⎥
Marcando la columna 6 que es donde se 4 ⎢14 − 17 ⎥
ha seleccionado la casilla (6, 2). 5 ⎢19 − 24 ⎥
⎢ ⎥
6 ⎢15 − 18 ⎥
7 ⎢16 − 14 ⎥
⎢ ⎥
8 ⎣⎢13 16 14 17 24 18 14 − ⎦⎥
3º 1º 2º 5º 6º 4º

1 2 3 4 5 6 7 8
Se selecciona el menor elemento de las 1 ⎡ − 20 18 14 19 15 16 13 ⎤

⎢ ⎥
columnas no marcadas, que es el elemento 13 2 ⎢ 20 − 16 ⎥
de la casilla (8, 1). ⎢ ⎥
3 ⎢ 18 − 14 ⎥
Se tachan las casillas (8, 1), (8, 2), (8, 3), (8, 4), 4 ⎢⎢ 14 − 17 ⎥
⎥
(8, 5), (8, 6) y (8, 7), así como sus casillas
5 ⎢ 19 − 24 ⎥
simétricas: (1, 8), (2, 8), (3, 8), (4, 8), (5, 8), ⎢ ⎥
(6, 8) y (7, 8) para evitar ciclos. 6 ⎢ 15 − 18 ⎥
⎢ ⎥
7 ⎢ 16 − 14 ⎥
distancia menor = d6 = 13
⎢ − ⎥⎦
8 ⎣ 13 16 14 17 24 18 14
3º 1º 2º 5º 6º 4º
1 2 3 4 5 6 7 8
1 ⎡− 20 18 14 19 15 16 ⎤
2 ⎢20 − ⎥
⎢ ⎥
3 ⎢18 − ⎥
⎢ ⎥
Marcando la columna 8 que es donde 4 ⎢14 − ⎥
se ha seleccionado la casilla (8, 1). 5 ⎢19 − ⎥
⎢ ⎥
6 ⎢15 − ⎥
7 ⎢16 − ⎥
⎢ ⎥
8 ⎢⎣ − ⎥⎦
3º 1º 2º 5º 6º 4º 7º
1 2 3 4 5 6 7 8
Se selecciona el menor elemento de las ⎡ ⎤
1 ⎢ − 20 18 14 19 15 16
⎥
columnas no marcadas, que es el elemento 14
2 ⎢ 20 − ⎥
de la casilla (1, 4). ⎢ ⎥
3 ⎢ 18 − ⎥
Se tachan todas las casillas de la columna 1, al 4 ⎢ 14 −
⎥
igual que sus simétricas. ⎢ ⎥
5 ⎢ 19 − ⎥
El algoritmo de Kruskal ha finalizado al tener 6 ⎢⎢ ⎥
⎥
15 −
todas las columnas marcadas. 7 ⎢ ⎥
⎢ 16 − ⎥
8 ⎢
− ⎥⎦
distancia menor = d7 = 14
⎣
3º 1º 2º 5º 6º 4º 7º

1 2 3 4 5 6 7 8
1 ⎡− ⎤
2 ⎢⎢ − ⎥
⎥
3 ⎢ − ⎥
Marcando la columna 1 como la última, ⎢ ⎥
4 ⎢ − ⎥
que es donde se ha seleccionado la
casilla (1, 4). 5 ⎢ − ⎥
⎢ ⎥
6 ⎢ − ⎥
7 ⎢ − ⎥
⎢ ⎥
8 ⎣⎢ − ⎦⎥
8º 3º 1º 2º 5º 6º 4º 7º
Longitud o peso mínimo de la distribución: 8 + 9 + 10 + 10 + 11 + 13 + 14 = 75

Coste mínimo de la distribución: 75 x 100 = 7.500 euros

ALGORTIMO DE SOLLIN: ÁRBOL DE EXPANSIÓN MÍNIMA
El algoritmo de Boruvka en la década de 1960 fue descubierto por Sollin, científico en computación, y
frecuentemente es conocido como el algoritmo de SOLLIN, especialmente en computación paralela
donde muchas instrucciones se ejecutan simultáneamente, operando sobre el principio de que
problemas grandes, a menudo se pueden dividir en problemas más pequeños, que luego son resueltos
simultáneamente.
El algoritmo de Sollin procede de la siguiente forma:
1. Se elige el elemento de menor valor, en caso de que existan varios se elige uno cualquiera. Se marca
el elemento y se elimina la columna donde se encuentre el valor marcado y se marca la fila como
primera fila marcada.
2. Del conjunto de elementos de las filas marcadas y que no han sido eliminados, se elige el valor
mínimo y se marca. Se elimina la columna donde se encuentre el valor marcado y se marca la fila
como segunda fila marcada.
3. Se reitera el proceso desde el punto (2) hasta que no se puedan seleccionar más elementos.
SOLLIN: Mediante un proceso sistemático, desde el

principio de que a menudo problemas complejos se pueden
dividir en problemas más pequeños, ejecutándolos después
simultáneamente, posibilita el cálculo del árbol expandido
mínimo de una forma más sencilla.

Al iniciar el algoritmo se elige el elemento de menor valor.
En este caso hay dos elementos con valor 5, se selecciona
arbitrariamente uno de ellos, por ejemplo el 5 de la columna
F y se marca.
Se elimina la columna F y se marca la fila F como la primera.
A B C D E F G H I J
A 10 11 14
B 10 15 8
C 15 9 7 8
D 9 6
E 11 9
1 F 14 8 9 9 5 11
⎯⎯→
G 7 9 14 8
H 8 6 14
I 51 6
J 11 8 6
1
De los elementos de la fila ⎯⎯→ F marcada se elige el elemento de menor valor que es 5 y se
marca. Se elimina la columna I y se marca la fila I como la segunda.

A B C D E F G H I J
A 10 11 14
B 10 15 8
C 15 9 7 8
D 9 6
E 11 9
1
⎯⎯→ F 14 8 9 9 52 11
G 7 9 14 8
H 8 6 14
2
⎯⎯→ I 51 6
J 11 8 6
De las filas marcadas hasta este momento (F, I) se elige el elemento con menor valor y no marcado
anteriormente. En la fila I está el elemento 6 y se marca, eliminando la columna J donde se encuentra,
marcando la fila J como la tercera.
A B C D E F G H I J
A 10 11 14
B 10 15 8
C 15 9 7 8
D 9 6
E 11 9
1
⎯⎯→ F 14 8 9 9 52 11
G 7 9 14 8
H 8 6 14
2
⎯⎯→ I 51 63
3 J 11 8 6
⎯⎯→
De las filas marcadas hasta ahora (F, I, J) se elige el elemento con menor valor y no marcado
anteriormente, que es un 8. Se elige arbitrariamente el 8 de la columna G, elimiando la columna G y
marcando la fila G como la cuarta.

A B C D E F G H I J
A 10 11 14
B 10 15 8
C 15 9 7 8
D 9 6
E 11 9
1
⎯⎯→ F 14 8 9 9 52 11
4 G 7 9 14 8
⎯⎯→
H 8 6 14
2
⎯⎯→ I 51 63
3
⎯⎯→ J 11 84 6
Sigue el proceso, de las filas marcadas (F, I, J, G) se elige el elemento con menor valor y no marcado
anteriormente. En la fila G está el elemento 7 y se marca, eliminando la columna C y marcando la fila C
como la quinta.
A B C D E F G H I J
A 10 11 14
B 10 15 8
5 C 15 9 7 8
⎯⎯→
D 9 6
E 11 9
1
⎯⎯→ F 14 8 9 9 52 11
4
⎯⎯→ G 75 9 14 8
H 8 6 14
2
⎯⎯→ I 51 63
3
⎯⎯→ J 11 84 6
De las filas marcadas (F, I, J, G, C) se elige el elemento con menor valor y no marcado anteriormente. El
elemento con menor valor es el 8, que se encuentra en la fila C y en la fila F, se elige arbitrariamente el 8
de la columna B, eliminando la columna y marcando la fila B como la sexta.

A B C D E F G H I J
A 10 11 14
6 B 10 15 8
⎯⎯→
5 C 15 9 7 8
⎯⎯→
D 9 6
E 11 9
1
⎯⎯→ F 14 86 9 9 52 11
4
⎯⎯→ G 75 9 14 8
H 8 6 14
2
⎯⎯→ I 51 63
3
⎯⎯→ J 11 84 6
De las filas marcadas (F, I, J, G, C) se elige el elemento con menor valor y no marcado anteriormente. El
elemento con menor valor es el 8 que se encuentra en la columna H, se elimina la columna y se marca la
fila H como la séptima.
A B C D E F G H I J
A 10 11 14
6 B 10 15 8
⎯⎯→
5
⎯⎯→ C 15 9 7 87
D 9 6
E 11 9
1
⎯⎯→ F 14 86 9 9 52 11
4
⎯⎯→ G 75 9 14 8
7 H 8 6 14
⎯⎯→
2
⎯⎯→ I 51 63
3
⎯⎯→ J 11 84 6
De las filas marcadas (F, I, J, G, C, H) se elige el elemento con menor valor y no marcado anteriormente.
El elemento con menor valor es el 6 que se encuentra en la columna D, se elimina la columna y se marca
la fila D como la octava.

A B C D E F G H I J
A 10 11 14
6 B 10 15 8
⎯⎯→
5
⎯⎯→ C 15 9 7 87
8 D 9 6
⎯⎯→
E 11 9
1
⎯⎯→ F 14 86 9 9 52 11
4
⎯⎯→ G 75 9 14 8
7
⎯⎯→ H 8 68 14
2
⎯⎯→ I 51 63
3
⎯⎯→ J 11 84 6
De las filas marcadas (F, I, J, G, C, H, D) se elige el elemento con menor valor y no marcado
anteriormente. El elemento con menor valor es el 9 que se encuentra en la columna E, se elimina la
columna y se marca la fila E como la novena.
A B C D E F G H I J
A 10 11 14
6 B 10 15 8
⎯⎯→
5
⎯⎯→ C 15 9 7 87
8 D 9 6
⎯⎯→
9 E 11 9
⎯⎯→
1
⎯⎯→ F 14 86 99 9 52 11
4
⎯⎯→ G 75 9 14 8
7
⎯⎯→ H 8 68 14
2
⎯⎯→ I 51 63
3
⎯⎯→ J 11 84 6
Finalmente, el proceso finaliza marcando el menor valor de la columna A que es el 10, se elimina la
columna y se marca la fila A como la décima.

A B C D E F G H I J
10 A 10 11 14
⎯⎯ →
⎯⎯6
→ B 1010 15 8
⎯⎯5
→ C 15 9 7 87
8 D 9 6
⎯⎯ →
9 E 11 9
⎯⎯ →
1
⎯⎯ → F 14 86 99 9 52 11
⎯⎯4
→ G 75 9 14 8
⎯⎯7
→ H 8 68 14
⎯⎯2
→ I 51 63
⎯⎯3
→ J 11 84 6
En un diagrama:
Coste mínimo de la distribución: 67 x 100 = 6700 euros.
De otra parte, si el coste de la conexión se incrementa 50

euros, el trazado no varía, aunque el coste se incrementaría
9 x 50 = 450 euros. El coste mínimo de la distribución sería
6700 + 450 = 7150 euros.
SOLLIN: Network Modeling / Minimal Spanning Tree

SOLLIN: Encontrar un árbol generador mínimo
del grafo ponderado.
Se elige inicialmente el elemento de menor valor. En este caso hay tres con valor 1, se selecciona uno de
ellos, por ejemplo el 1 de la columna F y se marca, se elimina la columna donde se encuentra y se marca
la fila F como la primera.
A B C D E F G
A 3 1
B 3 8 7 5
C 1 8
D 7 6 9
E 5 6 1 2
1 F 1 4
⎯⎯→
G 9 2 4
En la fila F se marca el 1, se elimina la columna E y se marca la fila E como segunda.
A B C D E F G
A 3 1
B 3 8 7 5
C 1 8
D 7 6 9
2 E 5 6 2
⎯⎯→ 1
1 F 4
⎯⎯→ 1
G 9 2 4
De filas marcadas (E, F) se elige el elemento con menor valor, no marcado anteriormente. En la fila E
está el elemento 2, se marca y se elimina la columna G donde se encuentra, quedando la fila G como
tercera.

A B C D E F G
A 3 1
B 3 8 7 5
C 1 8
D 7 6 9
2 E 5 6
⎯⎯→ 1 2
1 F 4
⎯⎯→ 1
3 G 9 2 4
⎯⎯→
De filas marcadas (E, F, G) se elige el elemento con menor valor, no marcado anteriormente. En la fila E
está el elemento 5, se marca y se elimina la columna B donde se encuentra, quedando la fila B como
cuarta.
A B C D E F G
A 3 1
4 B 3 8 7 5
⎯⎯→
C 1 8
D 7 6 9
2 E 6
⎯⎯→ 5 1 2
1 F 4
⎯⎯→ 1
3 G 9 2 4
⎯⎯→
De filas marcadas (B, E, F, G) se elige el elemento con menor valor, no marcado anteriormente. En la fila
B está el elemento 3, se marca y se elimina la columna A donde se encuentra, quedando la fila A como
quinta.
A B C D E F G
5 A 3 1
⎯⎯→
4 B 8 7 5
⎯⎯→ 3
C 1 8
D 7 6 9
2 E 6
⎯⎯→ 5 1 2
1 F 4
⎯⎯→ 1
3
⎯⎯→ G 9 2 4
De filas marcadas (A, B, E, F, G) se elige el elemento con menor valor, no marcado anteriormente. En la
fila A está el elemento 1, se marca y se elimina la columna C donde se encuentra, quedando la fila C
como sexta.

A B C D E F G
5 A 3
⎯⎯→ 1
4 B 8 7 5
⎯⎯→ 3
6 C 1 8
⎯⎯→
D 7 6 9
2 E 6
⎯⎯→ 5 1 2
1 F 4
⎯⎯→ 1
3 G 9 2 4
⎯⎯→
Finalmente, el elemento con menor valor de la columna D es el 6 (fila E) se marca y se elimina la
columna D, queda la fila D como séptima.
A B C D E F G
5 A 3
⎯⎯→ 1
4 B 8 7 5
⎯⎯→ 3
6 C 1 8
⎯⎯→
7 D 7 6 9
⎯⎯→
2 E
⎯⎯→ 5 6 1 2
1 F 4
⎯⎯→ 1
3 G 9 2 4
⎯⎯→
En un diagrama:
El árbol generador mínimo es 18

SOLLIN: El grafo adjunto muestra una
ruta aérea donde la distancia entre cada par
de ciudades se expresa en cientos de millas.
Obtener una red que conecte todas las
ciudades y sea de mínima distancia.
Al iniciar el algoritmo se elige el elemento de menor valor. En este caso hay tres elementos con valor 2, se
selecciona arbitrariamente uno de ellos, por ejemplo el 2 de la columna D y se marca. Se elimina la
columna D y se marca la fila D como la primera.
A B C D E F G H I T
9 A 7 8
⎯⎯→
7 B 79 7 8 6
⎯⎯→
5 C 8 7 6 46
⎯⎯→
1 D 8 22 3 34
⎯⎯→
2 E 67 65 21 7 23 6
⎯⎯→
6 F 4 7 9 68
⎯⎯→
3 G 3 2 5 9
⎯⎯→
4 H 3 6 9 5 8 8
⎯⎯→
8 I 6 8 810
⎯⎯→
⎯⎯
10
→ T 9 8 8
Una ruta aérea que conecte

todas las ciudades y minimice
la distancia tiene un valor de
44 millas.
Otra posibilidad sería
intercambiar la ruta IT por HT.

SOLLIN: Siete estaciones ferroviarias se conectan a través de una red provincial para intercambiar
información. Por diversas circunstancias, las líneas no son iguales en cuanto a velocidad ni a coste de
transmisión, variando la distancia de unos puestos a otros.
En el grafo adjunto se muestra la distribución
actual de las líneas de comunicaciones, donde
los nodos reflejan cada uno de los puestos de
cada estación y las etiquetas de cada arista
representan tres factores (longitud de las líneas,
velocidad de transmisión y coste de envió de
información por línea).
Para obtener una optimización de la línea, suponiendo que las líneas fueran bidireccionales y no fuera
deseable que se formasen ciclos, la empresa ferroviaria contrata a una consultoría de comunicaciones
para que dé respuestas a las preguntas siguientes:
a) ¿Qué tendido mínimo de cable es necesario para unir todas las estaciones?
b) ¿Con qué configuración se lograría conectar todas las estaciones a la mayor velocidad posible?
a) Para obtener el mínimo tendido de cable (mínima longitud) se elabora la siguiente matriz de Sollin:
A B C D E F G
6 A 6 6 5 6
⎯⎯→
7 B 6 8 7
⎯⎯→
3 C 8 34 3
⎯⎯→
4 D 66 77 3 3 4
⎯⎯→
1 E 5 3 45 22
⎯⎯→
5 F 6 4 4
⎯⎯→
2 G 33 4 21 4
⎯⎯→
Una red de mínima

longitud sería de 23
b) Para configurar todas las estaciones a la mayor velocidad posible hay que encontrar el "árbol
generador de máxima velocidad de transmisión", esto es, que la suma de los pesos de sus aristas sea
máxima.

Para construir el árbol generador máximo puede emplearse de algoritmo de los pesos decrecientes
como si se tratase de un árbol generador mínimo, con dos diferencias sustanciales:
) Añadir aristas en lugar de suprimirlas
) La conexión de una arista no debe formar un ciclo.
Es decir, el árbol generador máximo tendrá tantos vértices como el grafo.
Se construye la matriz de Sollin:
A B C D E F G
1 A 95 102 5 94
⎯⎯→
5 B 9 7 4
⎯⎯→
7 C 7 8 96
⎯⎯→
2 D 101 4 8 93 7
⎯⎯→
3 E 10 9 9 5
⎯⎯→
4 F 9 9 9
⎯⎯→
6 G 97 7 5 9
⎯⎯→
Una red de máxima

velocidad es de 55

SOLLIN: El grafo adjunto presenta el diseño
de un metro para Valladolid, indicando las
estaciones (nodos) y las distancias que las separan
en centenares de metros.
Suponiendo que el coste de la construcción es
proporcional a la distancia y que cuando dos
estaciones no se encuentran unidas es debido a
imposibilidades técnicas por el río Pisuerga o a un
coste excesivo.
a) Diseñar la red de metro de forma que las estaciones queden conectadas a coste mínimo. ¿Cuál será
la red a construir y cuál su longitud?
b) El Ayuntamiento de Valladolid impone la condición de que entre dos estaciones de metro no tiene
que haber más de cuatro estaciones intermedias, ¿Cuál sería la red de metro?
a) Se trata de construir un árbol generador mínimo para la red conexa de la figura. Para ello, se aplica
el algoritmo de Sollin, comenzando por establecer la matriz de incidencia asociada al grafo.
A B C D E F G H I J
3 A 4 54 8 5 7 6
⎯⎯→
2 B 43 7 10 9 6 21 5
⎯⎯→
4 C 5 7 8 3 6
⎯⎯→
D 10 8 6 9 13 5
E 8 9 9 7 16
F 5 6 3 6
1 G 22 9 6 11
⎯⎯→
H 7 6 13 9 12 13
I 6 5 7 6 12
J 5 16 11 13
a a a a
3 2 4 1

A B C D E F G H I J
3 A 4 54 8 5 7 6
⎯⎯→
2 B 43 7 10 9 6 21 56
⎯⎯→
4 C 5 7 8 35 6
⎯⎯→
D 10 8 6 9 13 5
E 8 9 9 7 16
5 F 5 6 3 6
⎯⎯→
1 G 22 9 6 11
⎯⎯→
H 7 6 13 9 12 13
6 I 6 5 7 6 12
⎯⎯→
J 5 16 11 13
a a a a a
3 2 4 5 1 6a
A B C D E F G H I J
3 A 4 54 8 5 7 6
⎯⎯ →
2 B 43 7 10 9 6 21 56
⎯⎯ →
4 C 5 7 8 35 67
⎯⎯ →
8 D 10 8 6 9 13 59
⎯⎯ →
10 E 8 9 9 7 16
⎯⎯→
5 F 5 6 3 68
⎯⎯ →
1 G 22 9 6 11
⎯⎯ →
7 H 7 6 13 9 12 13
⎯⎯ →
6 I 6 5 710 6 12
⎯⎯ →
9 J 5 16 11 13
⎯⎯ →
3a 2a 4a 8a 10a 5a 1a 7a 6a 9a
El árbol generador mínimo indica la red de

metro a construir, con una longitud de
43 x 100 = 4300 metros
Analizando el árbol generador mínimo, la

cadena JDFCABIE no cumple la condición,
la estación E se encuentra separado de la
estación J por más de cuatro estaciones.

b) La red de metro diseñada no cumple las condiciones del Ayuntamiento de Valladolid de que entre
dos estaciones de metro no tiene que haber más de cuatro estaciones intermedias.
En la red de metro construida, la arista de mayor valor es IE con un peso de 700 metros.
Una vez eliminada la arista IE, al intentar substituirla, no se encuentra otra estación que siga
conservando la estructura del árbol.
En caso de no ser posible, se elige otra arista de un valor inmediatamente superior que no pertenezca al
árbol. Se elige la arista AE con peso 800 metros.
La cadena JDFCAEBI tampoco cumple la
condición, la arista de mayor valor es DF.
Al eliminarla y querer susbstituirla no se
encuentra otra arista de ese valor que conserve
la estructura del árbol.
Se elige otra arista de un valor inmediatamente
superior que no pertenezca al árbol.
Se selecciona la arista DC.
En cualquier caso, la arista elegida no se añade directamente al árbol hasta verificar que proporciona
una posible cadena. Una vez que ha sido obtenida, la arista no se elimina del árbol en posteriores
iteraciones del proceso
.Con las exigencias del Ayuntamiento, la red de

metro será la de la figura adjunta, con una
longitud de 46 x 100 = 4600 metros

1 2 3 4 5 6 7 8
SOLLIN (ÁRBOL EXPANSIÓN MÍNIMA) 1 ⎡− 20 18 14 19 15 16 13 ⎤
2 ⎢ 20 − 16 9 12 11 10 16 ⎥⎥
3 ⎢18 16 − 8 22 12 13 14 ⎥
⎢ ⎥
tabla adjunta. Calcular el coste mínimo. 7 ⎢16 10 13 21 17 13 − 14 ⎥
⎢ ⎥
8 ⎣⎢ 13 16 14 17 24 18 14 − ⎦⎥
GRAFO ADJUNTO:
Se selecciona el mínimo elemento de la tabla
(elemento 8) que se encuentra en la casilla
(3, 4). En caso de existir varios, se selecciona
uno cualquiera.
Se eliminan las columnas 3 y 4 , marcando las
filas 3 y 4.
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
1 ⎡− 20 18 14 19 15 16 13 ⎤ 1 ⎡− 20 19 15 16 13 ⎤
⎢20 16 ⎥⎥
2 ⎢ − 16 9 12 11 10 2 ⎢⎢20 − 12 11 10 16 ⎥⎥
3 ⎢18 16 − 8 22 12 13 14 ⎥ 1• 3 ⎢18 16 22 12 13 14 ⎥
⎢ ⎥ • ⎢ ⎥
4 ⎢14 9 8 − 13 16 21 17 ⎥ 2 4 ⎢14 9 13 16 21 17 ⎥
⎢ ⎥ 5 ⎢19 − 24 ⎥
5
⎢19 12 22 13 − 10 17 24 ⎥ 12 10 17
⎢ ⎥
6 ⎢15 11 12 16 10 − 13 18 ⎥ 6 ⎢15 11 10 − 13 18 ⎥
⎢ ⎥
7 ⎢16 10 13 21 17 13 − 14 ⎥ 7 ⎢16 10 17 13 − 14 ⎥
⎢ ⎥
8 ⎢ − ⎦⎥ 8 ⎢⎣13 16 24 18 14 − ⎥⎦
⎣13 16 14 17 24 18 14
Como no están marcadas todas las filas, el algoritmo sigue. Se selecciona el mínimo elemento que
pertenece a las filas marcadas y no pertenecen a las columnas eliminadas.

El mínimo elemento es el 9, que se encuentra en la casilla (4, 2), se elimina la columna 2 y se marca la fila 2.
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
1 ⎡− 20 19 15 16 13 ⎤ 1 ⎡− 19 15 16 13 ⎤
⎢ ⎥
16 ⎥ 3• 2 ⎢20
2 ⎢20 − 12 11 10
⎢ 12 11 10 16 ⎥⎥
•
1 3 ⎢18 16 22 12 13 14 ⎥ 1• 3 ⎢18 22 12 13 14 ⎥
⎢ ⎥ • ⎢ ⎥
2• 4 ⎢14 9 13 16 21 17 ⎥ 2 4 ⎢14 13 16 21 17 ⎥
5 ⎢19 12 − 10 17 24 ⎥ 5 ⎢19 − 10 17 24 ⎥
⎢ ⎥ ⎢ ⎥
6 ⎢15 11 10 − 13 18 ⎥ 6 ⎢15 10 − 13 18 ⎥
7 ⎢16 10 17 13 − 14 ⎥
⎥ 7 ⎢16 17 13 − 14 ⎥
⎢ ⎢ ⎥
8 ⎣⎢13 16 24 18 14 − ⎦⎥ 8 ⎢⎣13 24 18 14 − ⎥⎦
Se selecciona el mínimo elemento que pertenece a las filas marcadas y no pertenecen a las columnas
eliminadas.
El mínimo elemento es el 10, que se encuentra en la casilla (2, 7), se elimina la columna 7 y se marca la
fila 7.
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
⎡− 19 15 16 13 ⎤ 1 ⎡− 19 15 13 ⎤
⎢ ⎥ ⎢20
3• ⎢20 12 11 10 16 ⎥ 3• 2 ⎢ 12 11 16 ⎥⎥
1• ⎢18 22 12 13 14 ⎥ 1• 3 ⎢18 22 12 14 ⎥
⎢ ⎥ ⎢ ⎥
2• ⎢14 13 16 21 17 ⎥ 2• 4 ⎢14 13 16 17 ⎥
⎢19 − 10 17 24 ⎥ 5 ⎢19 − 10 24 ⎥
⎢ ⎥ ⎢ ⎥
⎢15 10 − 13 18 ⎥ 6 ⎢15 10 − 18 ⎥
⎢ ⎥ • ⎢16 14 ⎥
⎢16 17 13 − 14 ⎥ 4 7 17 13
⎢ ⎥
⎣⎢13 24 18 14 − ⎦⎥ 8 ⎢⎣13 24 18 − ⎥⎦
eliminadas.
fila 6.
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
1 ⎡− 19 15 13 ⎤ 1 ⎡− 19 13 ⎤
⎢ ⎥ ⎢20
3• 2 ⎢20 12 11 16 ⎥ 3• 2 ⎢ 12 16 ⎥⎥
1• 3 ⎢18 22 12 14 ⎥ 1• 3 ⎢18 22 14 ⎥
⎢ ⎥ ⎢ ⎥
2• 4 ⎢14 13 16 17 ⎥ 2• 4 ⎢14 13 17 ⎥
5 ⎢19 − 10 24 ⎥ 5 ⎢19 − 24 ⎥
⎢ ⎥ ⎢ ⎥
6 ⎢15 10 − 18 ⎥ 5• 6 ⎢15 10 18 ⎥
4 7 ⎢16
•
17 13 14 ⎥
⎥ 4• 7 ⎢16 17 14 ⎥
⎢ ⎢ ⎥
8 ⎣⎢13 24 18 − ⎦⎥ 8 ⎢⎣13 24 − ⎥⎦

eliminadas.
fila 6.
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
1 ⎡− 19 13 ⎤ 1 ⎡− 13 ⎤
⎢20 16 ⎥⎥ ⎢20
•
3 2 ⎢ 12 •
3 2 ⎢ 16 ⎥⎥
1• 3 ⎢18 22 14 ⎥ 1• 3 ⎢18 14 ⎥
⎢ ⎥ ⎢ ⎥
2• 4 ⎢14 13 17 ⎥ 2• 4 ⎢14 17 ⎥
5 ⎢19 − 24 ⎥ 6• 5 ⎢19 24 ⎥
•
⎢ ⎥ ⎢ ⎥
5 6 ⎢15 10 18 ⎥ 5• 6 ⎢15 18 ⎥
4 7 ⎢16
•
17 14 ⎥
⎥ 4• 7 ⎢16 14 ⎥
⎢ ⎢ ⎥
8 ⎣⎢13 24 − ⎦⎥ 8 ⎣⎢13 − ⎦⎥
eliminadas.
fila 8.
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
1 ⎡− 13 ⎤ 1 ⎡− ⎤
• ⎢20 ⎥ •
16 ⎥ 3 2 20 ⎢ ⎥
3 2 ⎢ ⎢ ⎥
1• 3 ⎢18 14 ⎥ 1• 3 ⎢18 ⎥
• ⎢ ⎥ • ⎢ ⎥
2 4 ⎢14 17 ⎥ 2 4 ⎢14 ⎥
6• 5 ⎢19 24 ⎥ 6• 5 ⎢19 ⎥
•
⎢ ⎥ • ⎢ ⎥
5 6 ⎢15 18 ⎥ 5 6 ⎢15 ⎥
4 • 7 ⎢16 14 ⎥
⎥ 4 • 7 ⎢16 ⎥
⎢ •
⎢ ⎥
8 ⎣⎢13 − ⎦⎥ 7 8 ⎢⎣13 ⎥⎦
fila 1.
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
1 ⎡ − ⎤ 8• 1 ⎡ ⎤
• ⎢ 20 ⎥ • ⎢ ⎥
3 2 ⎢ ⎥ 3 2 ⎢ ⎥
1• 3 ⎢ 18 ⎥ 1• 3 ⎢ ⎥
• ⎢ ⎥ • ⎢ ⎥
2 4 ⎢ 14 ⎥ 2 4 ⎢ ⎥
•
6 5 19 ⎢ ⎥ •
6 5 ⎢ ⎥
⎢ ⎥ ⎢ ⎥
5• 6 ⎢ 15 •
⎥ 5 6 ⎢ ⎥
•
4 7 16 ⎢ ⎥ •
4 7 ⎢ ⎥
⎢ ⎥ ⎢ ⎥
7• 8 ⎢⎣ 13 ⎥⎦ 7• 8 ⎣⎢ ⎦⎥

1 2 3 4 5 6 7 8
⎡ − 20 18 14 19 15 16 13 ⎤
8• 1 ⎢ ⎥
3• 2 ⎢ 20 − 16 9 12 11 10 16 ⎥
⎢ − 14 ⎥⎥
1• 3 ⎢ 18 16 8 22 12 13
2• 4 ⎢ 14 9 8 − 13 16 21 17 ⎥
⎢ ⎥
6• 5 ⎢ 19 12 22 13 − 10 17 24 ⎥
5• 6 ⎢⎢ 15 11 12 16 10 − 13 18 ⎥
⎥
4 • 7 ⎢ 16 10 13 21 17 13 − 14 ⎥
⎢ ⎥
7• 8 ⎢
⎣ 13 16 14 17 24 18 14 − ⎥⎦
Longitud o peso mínimo de la distribución: 8 + 9 + 11 + 10 + 10 + 14 + 13 = 75
Coste mínimo de la distribución: 75 x 100 = 7.500 euros
WinQSB / Network Modeling ‐ Minimal Spanning Tree

1 2 3 4 5 6 7 8
SOLLIN (ÁRBOL EXPANSIÓN MÁXIMA) 1 ⎡− 20 18 14 19 15 16 13 ⎤
2 ⎢ 20 − 16 9 12 11 10 16 ⎥⎥
3 ⎢18 16 − 8 22 12 13 14 ⎥
⎢ ⎥
tabla adjunta. Calcular el máximo coste. 7 ⎢16 10 13 21 17 13 − 14 ⎥
⎢ ⎥
8 ⎣⎢ 13 16 14 17 24 18 14 − ⎦⎥
GRAFO ADJUNTO:
Se selecciona el máximo elemento de la tabla
(elemento 24) que se encuentra en la casilla
(8, 5).
Se eliminan las columnas 5 y 8, y se marcan las
filas 5 y 8.
En caso de existir varios, se selecciona uno
cualquiera.
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
1 ⎡− 20 18 14 19 15 16 13 ⎤ 1 ⎡− 20 18 14 15 16 ⎤
⎢ 16 ⎥⎥
2 ⎢20 − 16 9 12 11 10 2 ⎢⎢20 − 16 9 11 10 ⎥
⎥
3 ⎢18 16 − 8 22 12 13 14 ⎥ 3 ⎢18 16 − 8 12 13 ⎥
⎢ ⎥ ⎢ ⎥
4 ⎢14 9 8 − 13 16 21 17 ⎥ 4 ⎢14 9 8 − 16 21 ⎥
5 ⎢19 12 22 13 − 10 17 24 ⎥ 1a 5 ⎢19 12 22 13 − 10 17 ⎥
⎢ ⎥ ⎢ ⎥
6 ⎢15 11 12 16 10 − 13 18 ⎥ 6 ⎢15 11 12 16 − 13 ⎥
⎢ ⎥
7 ⎢16 10 13 21 17 13 − 14 ⎥ 7 ⎢16 10 13 21 13 − ⎥
⎢ ⎥
8 ⎢⎣13 16 14 17 24 18 14 − ⎥⎦ 2 8 ⎢⎣13
a
16 14 17 18 14 − ⎥⎦
Como no están marcadas todas las filas, el algoritmo continúa.

Se selecciona el máximo elemento que pertenece a las filas marcadas y no pertenecen a las columnas
eliminadas.
El máximo elemento es el 22, que se encuentra en la casilla (5, 3), se elimina la columna 3 y se marca la
fila 3.

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
1 ⎡− 20 18 14 15 16 ⎤ 1 ⎡− 20 14 15 16 ⎤
⎢ ⎥
2 ⎢20 − 16 9 11 10 ⎥ 2 ⎢⎢20 − 9 11 10 ⎥
⎥
3 ⎢18 16 − 8 12 13 ⎥ 3a 3 ⎢18 16 − 8 12 13 ⎥
⎢ ⎥ ⎢ ⎥
4 ⎢14 9 8 − 16 21 ⎥ 4 ⎢14 9 − 16 21 ⎥
1a 5 ⎢19 12 22 13 − 10 17 ⎥ 1a 5 ⎢19 12 13 − 10 17 ⎥
⎢ ⎥ ⎢ ⎥
6 ⎢15 11 12 16 − 13 ⎥ 6 ⎢15 11 16 − 13 ⎥
7 ⎢16 10 13 21 13 −
⎥ 7 ⎢16 10 21 13 − ⎥
⎢ ⎥ ⎢ ⎥
2a 8 ⎣⎢13 16 14 17 18 14 − ⎦⎥ 2 8 ⎣⎢13
a
16 17 18 14 − ⎦⎥
eliminadas.
fila 1.
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
1 ⎡ − 20 14 15 16 ⎤ 4a 1 ⎡− 20 14 15 16 ⎤
⎢ ⎥
2 ⎢ 20 − 9 11 10 ⎥ 2 ⎢⎢ − 9 11 10 ⎥
⎥
3a 3 ⎢ 18 16 − 8 12 13 ⎥ 3a 3 ⎢ 16 − 8 12 13 ⎥
⎢ ⎥ ⎢ ⎥
4 ⎢ 14 9 − 16 21 ⎥ 4 ⎢ 9 − 16 21 ⎥
1a 5 ⎢ 19 12 13 − 10 17 ⎥ 1a 5 ⎢ 12 13 − 10 17 ⎥
⎢ ⎥ ⎢ ⎥
6 ⎢ 15 11 16 − 13 ⎥ 6 ⎢ 11 16 − 13 ⎥
7 ⎢ 16 10 21 13 −
⎥ 7 ⎢ 10 21 13 − ⎥
⎢ ⎥ ⎢ ⎥
2a 8 ⎢⎣ 13 16 17 18 14 − ⎥⎦ 2a 8 ⎣⎢ 16 17 18 14 − ⎦⎥
eliminadas.
fila 2.
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
a
4 1 ⎡− 20 14 15 16 ⎤ 4 1 ⎡−
a
14 15 16 ⎤
⎢ ⎥ ⎢ ⎥
2 ⎢ − 9 11 10 ⎥ 5a 2 ⎢ − 9 11 10 ⎥
a
3 3 ⎢ 16 − 8 12 13 ⎥ 3a 3 ⎢ − 8 12 13 ⎥
⎢ ⎥ ⎢ ⎥
4 ⎢ 9 − 16 21 ⎥ 4 ⎢ − 16 21 ⎥
a
1 5 ⎢ 12 13 − 10 17 ⎥ 1a 5 ⎢ 13 − 10 17 ⎥
⎢ ⎥ ⎢ ⎥
6 ⎢ 11 16 − 13 ⎥ 6 ⎢ 16 − 13 ⎥
⎢ ⎥ 7 ⎢ − ⎥
7
⎢ 10 21 13 − ⎥
21 13
⎢ ⎥
a
2 8 ⎢⎣ 16 17 18 14 − ⎥⎦ 2a 8 ⎢⎣ 17 18 14 − ⎥⎦
eliminadas.

fila 6.
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
a
4 1 ⎡− 14 15 16 ⎤ 4 1 ⎡−
a
14 16 ⎤
⎢ − ⎥ ⎢ ⎥
5a 2 ⎢ 9 11 10 ⎥ 5a 2 ⎢ − 9 10 ⎥
3a 3 ⎢ − 8 12 13 ⎥ 3a 3 ⎢ − 8 13 ⎥
⎢ ⎥ ⎢ ⎥
4 ⎢ − 16 21 ⎥ 4 ⎢ − 21 ⎥
a
1 5 ⎢ 13 − 10 17 ⎥ 1a 5 ⎢ 13 − 17 ⎥
⎢ ⎥ ⎢ ⎥
6 ⎢ 16 − 13 ⎥ 6a 6 ⎢ 16 13 ⎥
7 ⎢ 21 13 − ⎥ 7 ⎢ 21 − ⎥
⎢ ⎥ ⎢ ⎥
a
2 8 ⎢⎣ 17 18 14 − ⎥⎦ 2a 8 ⎢⎣ 17 14 − ⎥⎦
eliminadas.
fila 4.
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
a
4 1 ⎡− 14 16 ⎤ 4 1 ⎡−
a
16 ⎤
⎢ − ⎥ ⎢ ⎥
5a 2 ⎢ 9 10 ⎥ 5a 2 ⎢ − 10 ⎥
3a 3 ⎢ − 8 13 ⎥ 3a 3 ⎢ − 13 ⎥
⎢ ⎥ ⎢ ⎥
4 ⎢ − 21 ⎥ 7a 4 ⎢ − 21 ⎥
a
1 5 ⎢ 13 − 17 ⎥ 1a 5 ⎢ − 17 ⎥
⎢ ⎥ ⎢ ⎥
6a 6 ⎢ 16 13 ⎥ 6a 6 ⎢ 13 ⎥
7 ⎢ 21 − ⎥ 7 ⎢ − ⎥
⎢ ⎥ ⎢ ⎥
2a 8 ⎢⎣ 17 14 − ⎥⎦ 2a 8 ⎢⎣ 14 − ⎥⎦
eliminadas.
fila 7.

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
4a 1 ⎡− 16 ⎤ 4a 1 ⎡− ⎤
⎢ − ⎥ ⎢ ⎥
5a 2 ⎢ 10 ⎥ 5a 2 ⎢ − ⎥
3a 3 ⎢ − 13 ⎥ 3a 3 ⎢ − ⎥
⎢ ⎥ ⎢ ⎥
a
7 4 ⎢ − 21 ⎥ 7a 4 ⎢ − ⎥
1a 5 ⎢ − 17 ⎥ 1a 5 ⎢ − ⎥
⎢ ⎥ ⎢ ⎥
6a 6 ⎢ 13 ⎥ 6a 6 ⎢ ⎥
⎢ ⎥ 8a 7 ⎢ − ⎥
7
⎢ − ⎥ ⎢ ⎥
a
2 8 ⎢⎣ 14 − ⎥⎦ 2a 8 ⎣⎢ − ⎦⎥
El algoritmo ha finalizado al marcar todas las filas.

1 2 3 4 5 6 7 8
1 ⎡ − 20 18 14 19 15 16 13 ⎤
⎢ ⎥
Longitud máxima del árbol: 2 ⎢ 20 − 16 9 12 11 10 16 ⎥
19 + 20 + 22 + 17 + 18 + 21 + 24 = 141 3 ⎢⎢ 18 16 − 8 22 12 13 14 ⎥
⎥
4 ⎢ 14 9 8 − 13 16 21 17 ⎥
El coste máximo de la distribución: ⎢ ⎥
5 ⎢ 19 12 22 13 − 10 17 24 ⎥
141 x 100 = 14.100 euros. 6 ⎢ 15 11 12 16 10 − 13 18 ⎥
⎢ ⎥
7 ⎢ 16 10 13 21 17 13 − 14 ⎥
8 ⎢ 13 ⎥
− ⎥⎦
⎢⎣ 16 14 17 24 18 14

Instrumentos Estadísticos Avanzados
Facultad Ciencias Económicas y Empresariales
Departamento de Economía Aplicada
Profesor: Santiago de la Fuente Fernández

2 Redes Valoradas

Cargado por

Copyright:

Formatos disponibles

2 Redes Valoradas

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

2 Redes Valoradas

Cargado por

Copyright:

Formatos disponibles

Instrumentos Estadísticos Avanzados

Facultad Ciencias Económicas y Empresariales

REDES VALORADAS. ALGORITMOS

Portal Estadística Aplicada: Redes Valoradas. Algoritmos 1

Un árbol es toda red (o grafo) G = (V, A) conexa, sin ciclos y con

 Dado un árbol, se verifica que V = A + 1

 Todas las aristas de un árbol son puentes.

 En un bosque de k componentes se verifica que V = A + k

Portal Estadística Aplicada: Redes Valoradas. Algoritmos 2

ÁRBOL GENERADOR MÍNIMO

ÁRBOL GENERADOR MÁXIMO

Portal Estadística Aplicada: Redes Valoradas. Algoritmos 3

Portal Estadística Aplicada: Redes Valoradas. Algoritmos 4

CAMINO DE PESO MÍNIMO

El camino 'más corto' entre el vértice v1 y v 3 no es el que tiene

C 2 = { v1 , v 2 , v 3 } tiene dos aristas y una distancia total de 6

C 3 = { v1 , v 2 , v 5 , v 3 } tiene tres aristas y una distancia total de 5

Portal Estadística Aplicada: Redes Valoradas. Algoritmos 5

El algoritmo de Dijkstra puede producir respuestas incorrectas si tiene pesos

Portal Estadística Aplicada: Redes Valoradas. Algoritmos 6

Se eligen los nodos adyacentes que tienen menor peso en la

Se marca la arista BC porque es el nodo que

Se marca la arista DE con peso 20

El árbol de longitud mínima se

ELABORACIÓN DE LA TABLA DE DIJKSTRA

Portal Estadística Aplicada: Redes Valoradas. Algoritmos 7

Aparece una nueva fila en la tabla:

t(D) = 14 < t(B) + p(BD) = 12 + 4 = 16 No cambia

Sólo hay el vértice vecino E: mín ⎣⎡ t(E) , t(D) + p(DE) ⎤⎦

t(E) = 23 > t(D) + p(DE) = 14 + 6 = 20 Cambia

Portal Estadística Aplicada: Redes Valoradas. Algoritmos 8

t(E) = 20 < t(C) + p(CE) = 19 + 2 = 21 No cambia

El vértice con etiqueta mínima es E, se añade al árbol el vértice E y la arista DE .

t(T) = 29 = t(E) + p(E T) = 20 + 9 = 29 No Cambia

Portal Estadística Aplicada: Redes Valoradas. Algoritmos 9

Vecino B el vértice A: Ruta AB. Longitud 12 Observando los vértices vecinos:

RUTA MÁS CORTA: WinQSB / Network Modeling ‐ Shortest Path Problem

Portal Estadística Aplicada: Redes Valoradas. Algoritmos 10

Grafo del planteamiento:

Se eligen los nodos adyacentes que tienen menor

Portal Estadística Aplicada: Redes Valoradas. Algoritmos 12

Portal Estadística Aplicada: Redes Valoradas. Algoritmos 13

El árbol de mínimos caminos desde A es:

El conjunto de caminos mínimos siempre es un árbol generador.

Portal Estadística Aplicada: Redes Valoradas. Algoritmos 14

t(C) = ∞ > t(B) + p(BC) = 5 + 5 = 10 Cambia

t(F) = ∞ > t(D) + p(DF) = 6 + 5 = 11 Cambia

Se actualiza la etiqueta del vértice adyacente a C: mín ⎡⎣ t(v) , t(C) + p(C v) ⎤⎦

t(G) = 12 = t(C) + p(CG) = 10 + 2 = 12 No Cambia

 Aparece una nueva fila: Se marca el vértice E , incorporando la arista DF al árbol.

Se actualiza la etiqueta del vértice adyacente a E: mín ⎡⎣ t(v) , t(E) + p(E v) ⎤⎦

Portal Estadística Aplicada: Redes Valoradas. Algoritmos 15

Vértice Camino Longitud

Portal Estadística Aplicada: Redes Valoradas. Algoritmos 16

Se eligen los nodos adyacentes que tienen

Surgen candidatos, vértices B, C y E.

Portal Estadística Aplicada: Redes Valoradas. Algoritmos 18

El árbol de caminos mínimos es:

RUTA MÁS CORTA: WinQSB / Network Modeling ‐ Shortest Path Problem

Encontrar el camino de longitud mínima

Dado un árbol, se verifica que V = A + 1

Todas las aristas de un árbol son puentes.

En un bosque de k componentes se verifica que V = A + k

Aparece una nueva fila: Se marca el vértice E , incorporando la arista DF al árbol.

Hallar la ruta más corta desde el vértice A hasta

Ruta: Madrid ‐ Miami ‐ Nueva York (1 ‐ 5 ‐ 6)

Ruta: Madrid ‐ Barcelona ‐ Nueva York (1 ‐ 2 ‐ 6)

Ruta: Madrid ‐ Las Palmas ‐ Nueva York (1 ‐ 3 ‐ 6)

No Negatividad e Integralidad: Las variables de decisión tienen la condición de no negatividad