Download Grafos y redes.

48
Materials
David Pujolar Morales
A5 Introducción a la optimización en redes
 Definición 1. Grafo finito. Sea un V un conjunto no vacío con un número finito
de elementos y E una familia finita de pares (ordenados o no) de elementos de V. En
tal caso, se denomina grafo finito a G = (V, E). Los elementos de V se denominan
nodos o vértices y los de E enlaces o aristas. Cuando los elementos de E son pares
ordenados reciben el nombre de arcos o aristas orientadas; de ser pares no ordenados
se denominan aristas no orientadas1. Los arcos o aristas con origen y destino en el
mismo vértice se conocen como bucles o lazos.
 Definición 2. Grafo orientado o digrafo. Grafo en el que todos los elementos de
E son arcos.
 Definición 3. Grafo no orientado o simétrico. Grafo en el que todos los elementos de E son aristas.
 Definición 4. Grafo mixto. Grafo finito en el que E posee tanto aristas como
arcos.
 Definición 5. Grafo nulo. Dado un grafo finito, se dice que es un grafo nulo si E
no contiene ningún elemento.
 Definición 6. Orden de un grafo. Dado un grafo finito, se denomina orden del
grafo al número de nodos del mismo.
 Definición 7. Subgrafo. Dados los grafos finitos G = (V, E) y G* = (V*, E*) se
dice que G* es un subgrafo de G si:
V*
V
E*
E
(1)
 Definición 8. Grafo parcial. Dados los grafos finitos G = (V, E) y G* = (V*, E*)
se dice que G* es un grafo parcial de G si:
V*
V
*
E
E
(2)
 Proposición 1. Todo grafo parcial es un subgrafo.
 Definición 9. Grafo propio. Grafo finito en el que card(V) ≥ 2 y card(E) ≥ 1.
 Definición 10. Grafo simple. Grafo propio que:
- No posee bucles.
- Entre cada par de nodos hay, a lo sumo, una única arista o un único
arco de una determinada orientación.2
 Definición 11. P-grafo (pseudografo de orden p). Grafo finito en el que el número máximo de arcos o aristas simultáneos entre dos vértices cualesquiera es p.
© Dr. David Pujolar
1 Con objeto de abreviar la notación, en grafos que sólo contienen aristas no orientadas -y, por lo tanto, no se induce a ambigüedad- éstas suelen designarse por el término genérico de aristas.
2 Nótese que la definición es compatible con la presencia de dos arcos entre un mismo par de nodos, siempre que posean
orientaciones contrarias. No lo es con el hecho de que entre dos nodos dados existiera simultáneamente un arco y una arista.
Por otra parte, adviértase que en el caso de un digrafo simple 𝐸 ⊆ 𝑉x𝑉 ; esto es, E es un subconjunto del producto cartesiano y,
por ende, puede definirse el digrafo en términos de G = (V,  ) donde  es una correspondencia de V sobre V.
Fundamentos de programación lineal y optimización en redes
Materials
49
 Definición 12. Multigrafo. P-grafo sin bucles3.
 Definición 13. Matriz de adyacencia.
Dado un grafo finito se denomina matriz de adyacencia a una matriz A de dimensión
nxn (donde n es el orden del grafo) cuyos elementos, denotados por aij, se definen
como4:
aij
k si entre el nodo i y el j existen k arcos o aristas
0 si entre el nodo i y el j no existe ningún arco o arista
(3)
Nótese que en el caso de grafos simples k = 1. La matriz de adyacencia es una de las
formas de representación de un grafo. Existen otros modos de representación; por
ejemplo, por extensión (mediante enumeración de los elementos de V y de E); gráficamente (siempre que el número de nodos y arcos y/o aristas no sea muy elevado);
etc.5
 Definición 14. Nodos adyacentes. En un grafo finito se dice que dos nodos son
adyacentes cuando entre ambos hay un arco o una arista que los une.
 Definición 15. Grafo completo. Dado un grafo finito simple, se dice que es completo si cualquier par de nodos son adyacentes (nótese que ello requiere que el grafo
posea (n2) arcos o aristas.)
 Definición 16. Arcos o aristas adyacentes. En un grafo finito se dice que dos
arcos o aristas son adyacentes si poseen, al menos, un nodo en común.
 Definición 17. Extremos inicial y final de un arco. En un digrafo, dado un arco
cualquiera (vi, vj) el nodo vi se denomina extremo inicial u origen del arco y vj extremo final o destino de dicho arco.
 Definición 18. Nodos sucesores y antecesores. En un digrafo finito en el que
exista un arco (vi, vj) el nodo vj se denomina sucesor del nodo vi y, análogamente, vi
antecesor de vj. (Obsérvese que si existieran los arcos (vi, vj), (vj, vi) entonces vi sería
simultáneamente sucesor y antecesor de vj y viceversa.)
 Definición 19. Arco incidente sobre un nodo. En un digrafo finito se dice que
un arco cualquiera (vi, vj) incide interiormente sobre el nodo vj y que incide exteriormente sobre el nodo vi.
 Definición 20. Grado interior de un nodo. En un digrafo finito el grado interior
de un nodo vi es el número de arcos que inciden interiormente sobre él, denotándose
como 𝐺𝑖− . El concepto puede extenderse fácilmente en el caso de considerar un subconjunto de nodos del digrafo: si   V*  V entonces 𝐺𝑉−∗ es el número de arcos
que inciden interiormente en V* (esto es, el número de arcos cuyo extremo inicial es
un nodo que no pertenece a V* pero cuyo extremo final sí que forma parte de V*).
© Dr. David Pujolar
3 En algunos textos, el término multigrafo se reserva para los p-grafos no orientados sin bucles mientras que el concepto
homólogo en digrafos es denotado por multidigrafo. Siguiendo esa nomenclatura, los p-grafos mixtos sin bucles se denominan
multigrafos mixtos.
4 En el caso de grafos mixtos es preciso considerar dos matrices de adyacencia: una para los arcos y otra para las aristas no
orientadas. Adviértase, por otra parte, como para grafos simétricos la matriz de adyacencia es una matriz simétrica.
5 Véase Ahuja et al. (1993) para una ampliación.
50
Materials
David Pujolar Morales
 Definición 21. Grado exterior de un nodo. En un digrafo finito el grado exterior
de un nodo vi es el número de arcos que inciden exteriormente sobre él, denotándose
como 𝐺𝑖+ . El concepto puede extenderse fácilmente en el caso de considerar un subconjunto de nodos del digrafo: si   V*  V entonces 𝐺𝑉+∗ es el número de arcos
que inciden exteriormente en V* (esto es, el número de arcos cuyo extremo inicial es
un nodo que pertenece a V* pero cuyo extremo final no forma parte de V*).
 Definición 22. Grado de un nodo. En un digrafo finito, el grado 𝐺𝑖 de un nodo vi
se define como 𝐺𝑖 = 𝐺𝑖− + 𝐺𝑖+. En el caso de   V*  V entonces el grado interior
de vendrá dado por 𝐺𝑉∗ = 𝐺𝑉−∗ + 𝐺𝑉+∗ . Los nodos con grado 0 ó 1 reciben el nombre
de nodos terminales.
 Definición 23. Estrella directa (o hacia delante). En un digrafo finito, la estrella
directa del nodo vi se define como el conjunto de vértices del digrafo para los cuales
existe un arco que incide exteriormente sobre vi, denotándose como 𝑆𝑖 . En otros
términos 𝑆𝑖 = {𝑣𝑗 ∈ 𝑉/∃(𝑣𝑖 , 𝑣𝑗 ) ∈ 𝐸}.
 Definición 24. Estrella inversa (o hacia atrás). En un digrafo, la estrella inversa
del nodo vi se define como el conjunto de vértices del digrafo para los cuales existe
un arco que incide interiormente sobre vi, denotándose como 𝑆𝑖−1. En otros términos, 𝑆𝑖−1 = {𝑣𝑗 ∈ 𝑉/∃(𝑣𝑗 , 𝑣𝑖 ) ∈ 𝐸}.
 Definición 25. Camino. Dado un digrafo finito un camino desde el nodo v0 al vp
es una secuencia finita de arcos adyacentes 𝑃 = {(𝑣0 , 𝑣1 ), (𝑣1 , 𝑣2 ), ⋯ , (𝑣𝑝−1 , 𝑣𝑝 )}. Adviértase como el nodo inicial de cada arco es el mismo que el nodo terminal del arco
precedente.
 Definición 26. Camino elemental.6 Camino en el que ningún nodo que forma
parte de él es recorrido más de una vez (todos los nodos 𝑣0 , ⋯ , 𝑣𝑝 que constituyen el
camino deben ser distintos).
 Definición 27. Camino simple. Camino en el que ningún arco es utilizado más de
una vez.
 Proposición 2. Todo camino elemental es un camino simple pero no todo camino
simple es elemental.
 Definición 28. Circuito. Camino cerrado; esto es, que empieza y acaba en el mismo vértice: 𝑃 = {(𝑣0 , 𝑣1 ), (𝑣1 , 𝑣2 ), ⋯ , (𝑣𝑝−1 , 𝑣𝑝 ), (𝑣𝑝 , 𝑣0 ) }.
 Definición 29. Cadena. Dado un grafo finito (ya sea un digrafo ya sea un grafo
simétrico) una cadena entre los nodo v0 y vp es una secuencia finita de arcos (con
independencia de cuál sea su orientación7) o aristas adyacentes. Al igual que en el
caso de los caminos elementales y simples, se definen las cadenas elementales y simples.
 Definición 30. Ciclo. Un ciclo es una cadena cerrada; esto es, que empieza y termina en el mismo vértice.
© Dr. David Pujolar
6 En algunos textos, el término camino simple es utilizado para definir el concepto de camino elemental.
7 Así pues, en un digrafo una cadena puede contener arcos recorridos en sentido contrario a su orientación.
Fundamentos de programación lineal y optimización en redes
Materials
51
 Proposición 3. Todo camino es una cadena y, por ende, todo circuito es un ciclo,
pero no toda cadena es un camino ni todo ciclo un circuito.
 Definición 31. Grafo débilmente conexo. Un grafo finito es débilmente conexo
cuando entre cualquier par de vértices existe al menos una cadena que los une.
 Definición 32. Grafo fuertemente conexo. Un digrafo finito se dice que es fuertemente conexo cuando entre cualquier par de vértices existe al menos un camino
que los une. Adviértase que el concepto de grafo fuertemente conexo requiere trabajar con digrafos, a diferencia de la conectividad débil, que se puede aplicar tanto a
grafos orientados como no orientados.
 Proposición 4. Un digrafo fuertemente conexo también es débilmente conexo.
 Definición 33. Árbol. Dado un grafo finito, se denomina árbol a todo grafo débilmente conexo sin ciclos. (Nótese que, en consecuencia, entre cada par de vértices
de un árbol sólo existirá una única cadena que los una y, por lo tanto, entre cada par
de vértices de un árbol a lo sumo podrá haber un arco o arista que los vincule. Asimismo, se colige que todo árbol que posea dos o más nodos es un grafo simple.)
 Proposición 5. Un árbol con n nodos posee n ˗ 1 arcos o aristas8.
 Definición 34. Árbol generador (árbol de expansión). Dado un grafo finito se
denomina árbol generador de dicho grafo a cualquier grafo parcial del mismo que
posea estructura de árbol.
 Definición 35. Bosque. Se denomina bosque a todo grafo finito sin ciclos9. (Adviértase que, como consecuencia de la definición, un bosque es un grafo simple no
necesariamente conexo.)
 Proposición 6. Todo bosque está formado por uno o más árboles.
 Definición 36. Red o grafo valuado. Se denomina red a todo grafo finito débilmente conexo sin bucles, en el que todo arco o arista posee asociada una o más magnitudes. En particular, tienen especial interés las redes definidas a partir de grafos
simples débilmente conexos10. Si el grafo asociado es un digrafo, la red se denomina
red dirigida, mientras que si el grafo vinculado es no orientado la red se conoce como
red no dirigida11. Un modo de representar una red12 es mediante matrices de adyacencia: una para describir su estructura de arcos o aristas y otras adicionales (tantas
como tipos de magnitudes figuren en arcos o aristas) para codificar los valores asociados a arcos o aristas. En los casos más simples se pueden representar también
gráficamente, de modo análogo a cómo se hace con los grafos, pero añadiendo a
cada arista sus magnitudes asociadas.
© Dr. David Pujolar
8 Obsérvese como el árbol más sencillo es el formado por un único nodo.
9 De acuerdo con la definición de bosque, un árbol puede concebirse como un bosque débilmente conexo.
10 Si no se indica lo contrario, todas las redes con las que se va a trabajar se presuponen que se corresponden con un grafo
simple débilmente conexo.
11 Bajo determinadas condiciones (problemas expresables como redes de flujo máximo o redes de flujo máximo a coste mínimo con coeficientes de coste no negativos) una red simétrica se puede reformular como una red orientada sustituyendo las
aristas [vi, vj] por dos arcos de sentido opuesto (vi, vj) y (vj, vi) e iguales magnitudes asociadas que las de la arista. Véase Ahuja et al.
(1993) para una ampliación. En las redes asociadas a ese tipo de problemas -conocidas como redes de transporte- siempre es
posible identificar un nodo origen o fuente (con grado interior nulo) y un nodo destino o sumidero (con grado exterior nulo), ya
sea porque se encuentran definidos explícitamente ya sea creándolos de forma ficticia; véase Wilson (2010).
12 Véase Ahuja et al. (1993) para una ampliación.
52
Materials
David Pujolar Morales
Formalmente, dado el grafo G = (V, E) y una función 𝑤: 𝐸 ⟶ ℝ una red con una
única magnitud en cada arista puede concebirse como el par (G, w)13.
 Definición 37. Árboles generadores óptimos14.
En redes simétricas en las que cada arista posea asociada una única magnitud, puede
resultar de interés hallar cuál es el árbol generador óptimo (esto es, con magnitud
total mínima o máxima15). Para ello se han desarrollado distintos algoritmos, como el
de Kruskal, el de Prim o el de Borůvka (también denominado algoritmo de Sollin).16
 Algoritmo de Kruskal.
- Ámbito de aplicación: obtención del árbol generador óptimo en redes simétricas.
- Orden de complejidad:17 𝑂(𝑚 log 𝑚).
- Pasos del algoritmo:
1.- Considerar el grafo parcial Gk = (V, Ek) vinculado a la red que define al problema. Establecer k = 0. Fijar E0 =  y ℓ0 = 0; donde ℓ𝑘 denota la longitud total de Gk (entendida como la suma de las magnitudes
asociadas a las aristas que forman parte de Ek).
2.- Si el objetivo es de minimización, ordenar las aristas de E (esto es,
del grafo original) en orden creciente a la magnitud que tienen asociada.
Si se pretende hallar el árbol de expansión máximo, ordenar las aristas
en orden decreciente.
3.- Hacer k = k + 1. Elegir la primera arista de la lista ordenada del paso
anterior, con la condición de que no haya sido usada previamente y que
no forme un ciclo en Gk-1.
4.- Establecer Gk = (V, Ek) con 𝐸𝑘 = 𝐸𝑘−1 ∪ {𝑒𝑘 } (donde 𝑒𝑘 es la arista elegida en el paso 3) y ℓ𝑘 = ℓ𝑘−1 + ℓ𝑒𝑘 (donde ℓ𝑒𝑘 denota la longitud de la arista 𝑒𝑘 ).
5.- Si k < n ˗ 1 volver al paso 3. Si k = n ˗ 1 finalizar; la solución viene
dada por Gn-1 = (V, En-1) con longitud total ℓ𝑛−1 .
Nótese como el algoritmo parte de una arista y va construyendo bosques que van
expandiéndose progresivamente hasta fusionarse en un único árbol. Adviértase, por
© Dr. David Pujolar
13 La extensión para redes con d magnitudes asociadas a cada arco o arista es inmediata: baste para ello tratar w como una
función vectorial con dominio en ℝ𝑑 .
14 También denominados árboles de expansión óptimos.
15 Adviértase como la obtención del árbol de expansión máximo en una red (G, w) equivale a hallar el árbol de expansión
mínimo en la red (G, ˗ w).
16 Para una ampliación, véase Ahuja et al. (1993).
17 La complejidad de un algoritmo viene dada por el número de pasos que hay que efectuar para pasar de los datos iniciales del
problema al resultado final. Para un algoritmo cualquiera, se dice que su tiempo de ejecución es de orden 𝑂(𝑓(𝑁)) (donde N
denota una medida de las operaciones que debe efectuar el algoritmo en relación con el volumen de datos de entrada del problema genérico sobre el que se aplica) si ∀ 𝑁 ≥ 𝑁0 el tiempo de cómputo del algoritmo no es superior a 𝑐𝑓(𝑁) siendo c y N0
constantes no negativas cualesquiera. Así pues, el orden de complejidad de un algoritmo establece la cota superior del tiempo de
cómputo de dicho algoritmo. Nótese que el orden de complejidad sólo recoge los términos influyentes en el tiempo de cómputo
para N suficientemente grande. En el caso del algoritmo de Kruskal, se demuestra que el factor determinante en el tiempo de
cómputo está acotado superiormente por 𝑂(𝑚 log 𝑚) siendo m el número de aristas.
Fundamentos de programación lineal y optimización en redes
Materials
53
otra parte, que la existencia de solución (que puede ser única o múltiple) está asegurada por el hecho de ser G conexo (recuérdese la nota 10).
 Árboles generadores óptimos y programación lineal. La determinación del
árbol de expansión óptimo de una red admite la siguiente formulación en términos
de un problema lineal binario:
OPT
xij
cij xij
vi ,v j
E
s. a
xij card S
vi ,v j
E(S)
vi ,v j
E(S)
xij
n 1
xij
0 i, j
1, , n
xij
i, j
1, , n
1 S
V
(4)
donde:
- n es el orden del grafo asociado a la red.
- cij es la magnitud asociada a la arista [vi, vj].
- xij es una variable binaria con valor 1 si entre los vértices vi, vj existe una arista que
los une y valor nulo en caso contrario.
- S es cualquier subconjunto no vacío de V.
- E(S) es un subconjunto de aristas de E cuyos ambos extremos pertenecen a S.
© Dr. David Pujolar
Adviértase como el primer conjunto de restricciones garantiza la ausencia de ciclos.
Asimismo, adviértase que cuando card(S) = 2, la primera restricción implica que xij ≤ 1
 i, j. A su vez, este hecho combinado con las restricciones de no negatividad y de
pertenecía a los enteros asegura que las variables sean binarias. Finalmente, el segundo bloque de restricciones es consecuencia del hecho de que todo árbol de expansión
debe poseer n – 1 aristas.