Localización en redes complejas

FACULTAD DE MATEMÁTICAS Doble Máster en Profesorado de Educación Secundaria Obligatoria y Bachillerato, Formación Profesional y Enseñanzas de Idiomas y Máster Universitario en Matemáticas TRABAJO DE FIN DE MÁSTER: Localización en redes complejas Presentado por: María Calvo González Dirigido por: Juan Antonio Mesa López-Colmenar Febrero 2020 Agradecimientos Me gustaría dar las gracias en primer lugar a mi tutor, Juan Antonio Mesa, por su atención constante desde el primer día, su implicación en mi trabajo, su profesionalidad y su cercanía. Quiero también agradecer mis padres su sacrificio, apoyo y preocupación hacia mi carrera, mis másteres y mis estudios en general. Pero sobre todo, me gustaría darles las gracias por ser todo un modelo a seguir, enseñando con el ejemplo el significado de la constancia, el trabajo y el tesón. Me gustaría dar las gracias a mi familia, en especial a mi tía Isabel, mi segunda madre. Debo agradecer su mera presencia en mis días, porque simplemente hace de cualquier día, un día mejor. Y finalmente dar las gracias a Carlos, por ser una pieza clave en todos los años universitarios, y por ofrecerme una ayuda desinteresada e infinita. Abstract During last decades, it has been taken an interest in the modeling of complex systems that could not be represented by classical graph theory. Such systems are characterized by a structure that cannot be reduced or simplified to a simple network, even by projection, without loss of information. This would be the case, for example, of the transportation network that is established in a certain city, where different means of transport (metro, bus, tram, ...) can coexist with different natures. There are many complex representation models, but in this paper we are going to focus on multilayer graphs. A multilayer graph is a pair M= (G,C)where G={Gα;α∈M}(with M={1, . . . , m}being the layer’s index subset of M) is a family of (directed or undirected, weighted or unweighted) graphs Gα= (Vα,Eα), called layers of M, and C={Eαβ ⊆Vα×Vβ;α,β∈M,α6=β} is the set of interconnections between nodes of different layers GαyGβwith α6=β. In this structure we will study two types of location problems. On the one hand, we will see the network design problems where we have origin-destination demand pairs we must satisfy according to different imposed and objective conditions. We will provide a formulation of the three possibly most studied location problems: the Median Problem, the Center Problem and the Coverage Problem. On the other hand, we will see the point location problems, where we are not going to have origin-destination pairs to satisfy, but we will consider different objectives taking into account the nodes of the network, without distinguishing whether a node is the origin or the destination of a pair or not. In both types, we will see how beyond the most basic cases of the problem, the multilayer struc- ture is required. Thus, it is not possible to make a projection of the multilayer network to transform it into a graph with the classic topology where to solve it, but a different topology of the problem is required. Resumen Durante las últimas décadas, se ha puesto un especial interés en el modelado de sistemas complejos que no han podido ser representados mediante la teoría de grafos clásica. Dichos sistemas se caracterizan por tener una estructura que no puede ser reducida o simplificada a un grafo simple, ni siquiera mediante una proyección, sin que eso conlleve pérdida de información. Éste sería el caso, por ejemplo, de la red de transporte que está establecida en una cierta ciudad, donde pueden coexistir distintos medios de transporte (metro, autobús, tranvía, ...) con distintas naturalezas. Existen multitud de sistemas complejos, pero en el presente trabajo vamos a centrarnos en los grafos multicapa. Una red multicapa es un par M= (G,C) donde G={Gα;α∈M}(con M={1, . . . , m}el conjunto de indices de las capas de M) es una familia de grafos (dirigidos o no, ponderados o no) Gα= (Vα,Eα), llamados las capas de M, siendo C={Eαβ ⊆Vα×Vβ;α,β∈M,α6=β} el conjunto de interconexiones entre nodos de diferentes capas GαyGβcon α6=β. En esta estructura estudiaremos dos tipo de problemas de localización. Por un lado, veremos los problemas de diseño de redes en los que tenemos pares origen-destino que debemos satisfacer atendiendo a diferentes condiciones impuestas y objetivos. Proporcionaremos una formulación de los tres problemas de localización posiblemente más estudiados: el Problema de la mediana, el del centro y el de cobertura. Por otro lado, veremos los problemas puntuales de localización, en los que ya no habra pares origen-destino que satisfacer, sino que consideraremos diferentes objetivos teniendo en cuenta los nodos del grafo, sin distinguir si un nodo es origen o destino de algún par. Tanto de un tipo como de otro, veremos como más allá de los casos más básicos del problema, se requiere de la estructura multicapa, no pudiéndose realizar una proyección del grafo multicapa para transformarlo en un grafo unicapa, donde resolverlo, sino requeriendo una topología del problema diferente. Índice general 1. Introducción 1 2. Conceptos previos 7 2.1. Definición de una red multicapa ................... 7 2.2. Tipos de grafos multicapa ....................... 11 3. Problemas origen-destino 17 3.1. Problema de diseño de redes ..................... 17 3.2. Problemas de localización tipo origen-destino en grafos multicapa 19 3.2.1. Problema de la mediana .................... 19 3.2.2. Problema del centro ...................... 22 3.2.3. Problema de cobertura ..................... 24 3.2.4. Problema restringido ...................... 26 4. Problemas puntuales 29 4.1. Problema puntual del centro ...................... 29 4.2. Problema puntual de la mediana ................... 38 4.3. Problema puntual del p-centro .................... 42 4.4. Problema puntual de la p-mediana .................. 45 4.4.1. Problema restringido ...................... 51 4.5. Problema puntual de máxima cobertura con k vértices ....... 53 4.5.1. Generalización del problema puntual de máxima cobertura con k vértices ....................... 54 4.5.2. Problema restringido ...................... 56 4.6. Problema puntual con varios pesos para cada arista ........ 57 Capítulo 2 Conceptos previos 2.1. Definición de una red multicapa Comenzaremos definiendo qué es una red o grafo multicapa, y exponiendo qué notación vamos a usar. Una red multicapa es un par M= (G,C)donde G={Gα;α∈M}(con M={1, . . . , m}el conjunto de indices de las capas de M) es una familia de grafos (dirigidos o no, ponderados o no) Gα= (Vα,Eα), llamados las capas de M, siendo C={Eαβ ⊆Vα×Vβ;α,β∈M,α6=β} el conjunto de interconexiones entre nodos de diferentes capas GαyGβcon α6= β. Nos referiremos a los elementos de Ccomo capas cruzadas, y los elementos de cada Eαse llamarán conexiones intracapas de M, mientras que a los elementos de cada Eαβ, con α6=β, los llamaremos conexiones intercapa. Definimos además Pαcomo el conjunto de todos los puntos en todas las aristas intracapa de la capa α∈M, y sea Pα,βel conjunto de todos los puntos en todas 7 las aristas intercapa entre las capas α∈Myβ∈M. Sean: P= [ α∈M Pα!∪ [ α,β∈M Pαβ  V=[ α∈M Vα Para una mayor claridad, en la definición presentada, sustituiremos Cαβ y Cα(las cuales hacen referencia a conexiones intracapa e intercapa) por Eαβ y Eαcuando nuestros grafos sean no dirigidos y por lo tanto, las conexiones sean aristas, y por Aαβ yAαcuando nuestros grafos sean dirigidos y las conexiones sean arcos. En este trabajo vamos a trabajar principalmente con grafos no dirigidos, excepto en el Problema de diseño de redes, que serán dirigidos. Podemos definir además unos ciertos pesos no negativos asociados a cada uno de los vértices y de las conexiones del grafo multicapa: reαel peso asociado a la arista intracapa eα, y reαβ el peso asociado a la arista intercapa eαβ, que puede representar su longitud o distancia entre sus dos vértices extremos. hα iel peso asociado al vértice vα i∈Vαde M. Para los problemas que vamos a considerar en adelante, vamos a requerir tener definida una distancia. Asumimos que el grafo multicapa es encajable en el plano en cada una de las capas, donde la métrica es la euclídea. Suponemos además que las aristas y arcos pueden modelarse mediante un segmento de una recta. Así, la longitud L(vα p,vβ q), donde (vα p,vβ q)es una arista intercapa o intracapa de M, es la distancia euclídea ||vα p−vβ q|| entre sus vértices extremos, y usando algoritmos de camino más corto podemos además computar la distancia entre cualquier par de nodos. Luego, en este modelo se cumple la desigualdad triangular. Así, las longitudes de las aristas inducen una función distancia dtal que, para dos puntos x,y∈P, 8 d(x,y) = distancia entre dos puntos xeyen M =longitud de cualquier camino más corto en Mentre los puntos xey Si xeyestán en la misma arista, entonces d(x,y)coincide con la longitud de la subarista (x,y). Podemos ver de forma inmediata, que Pes un espacio métrico. Ya que tenemos definida la distancia entre dos puntos xeycualesquiera de M, definiremos la distancia entre un punto xarbitrario y un vértice cualquiera del grafo multicapa. Sea así xun punto arbitrario de eγ= (vγ p,vγ q), y sea vα i∈Vαun vértice cualquiera de M. Entonces: d(vα i,x) = m´ ın{d(x,vp) + d(vp,vi),d(x,vq) + d(vq,vi)}(2.1) Sea d(vγ p,vγ q) = deγ=Leγ, y sea d(vγ p,x) = x. Por tanto, d(vq,x) = Leγ−x. De esta manera, la ecuación (4.3) puede escribirse como: d(vi,x) = m´ ın{x+d(vγ p,vα i),Leγ−x+d(vγ q,vα i)}. (2.2) Por otro lado, también nos será necesario definir una distancia entre dos vértices de un grafo cualesquiera. Para ello definiremos una matriz de distancias entre los vértices. Consideramos primero el conjunto de matrices Dα= [dα ij], con α∈ M, de dimensión |Vα|×|Vα|, donde: dα ij =(d(vα i,vα j), para vα i,vα j∈Vα, con i6=j d(vα i,vα j) = 0, para vα i,vα j∈Vα, con i=j Estas son las matrices de distancias que se pueden definir entre los vértices de cada una de las capas, teniendo en cuenta no solo las aristas de esa capa, sino todas las de Ma la hora de calcular el camino más corto. Sin embargo, también es posible definir distancias entre vértices de distintas capas. Para ello, consideramos el conjunto de matrices Dαβ = [dαβ ij ], con α,β∈M, de dimensión |Vα|×|Vβ|, donde: dαβ ij =d(vα i,vβ j),para vα i∈Vα,vβ j∈Vβ A partir de estos dos conjuntos de matrices podemos construir la matriz de 9 distancias Dde nuestro grafo multicapa M, de orden n=|V|.Dserá una matriz por bloques de la siguiente forma: D=     D1D12 · · · D1m D21 D2· · · D2m . . .. . ..... . . Dm1Dm2· · · Dm      Es decir, Dtendrá una matriz de distancias del tipo Dα, con α∈M, en sus bloques de la diagonal, y una matriz del tipo Dαβ en el resto de bloques. También es conveniente señalar que a priori podría parecernos que cualquier grafo multicapa podría transformarse fácilmente en un grafo unicapa. Esto haría que perdiera el sentido hablar de este tipo de estructura en grafos, pudiéndose aplicar los problemas tradicionales de localización en redes a cualquier variante de problema de localización que pudiera tener lugar en un grafo multicapa. (véase Figura 2.1) Figura 2.1: Transformación de un grafo multicapa a un grafo unicapa Aunque comenzaremos viendo este tipo de problemas, pasaremos a continuación a variantes para las cuales esta estructura multicapa juega un papel fundamental e indispensable para su planteamiento, sentido y resolución. 10 2.2. Tipos de grafos multicapa Es importante señalar que el concepto de red multicapa es muy general, y podemos diferenciar diferentes tipos de redes con distintas estructuras y características: Redes multiplex: Un grafo multiplex [18]Mcon mcapas es un conjunto de capas {Gα,α∈M={1, . . . , m}}, donde cada capa es un grafo dirigido o no Gα= (Vα,Eα), con Vα={v1, . . . , vN}. Como todas las capas tienen los mismos nodos, este tipo de grafo puede interpretarse como uno multicapa tomando V1=· · · =Vm=V, y Eαβ ={(v,v),v∈V}para cada 1 ≤α6=β≤m. En la Figura 2.2, podemos observar un ejemplo de grafo multiplex de cuatro vértices y tres capas. Nótese que las aristas intercapa que van de la primera capa a la tercera están superpuestas con las que van de la primera a la segunda y las que van de la segunda a la tercera. Figura 2.2: Ejemplo de grafo multiplex. Redes temporales: Un grafo temporal [11](G(t))T t=1puede representarse como un grafo multicapa con un conjunto de capas {G1, . . . , GT}, donde Gt=G(t),Eαβ =∅si β6=α+1, siendo Eα,α+1={(v,v),v∈Vα∩Vα+1} 11 Nótese que aquí tes un entero. En la Figura 2.3, tenemos un ejemplo de asociación de un grafo temporal con un grafo multicapa. En la parte de la derecha, podemos ver que para tiempos t=1,2,3, un grafo distinto caracteriza la estructura de interacciones entre las constituyentes del sistema. En la parte de la izquierda, vemos la representación correspondiente como un grafo multicapa donde cada instante de tiempo se asocia a una capa distinta.. Figura 2.3: Ejemplo de asociación de un grafo temporal con un grafo multicapa. Redes interconectadas: Si consideramos una familia de grafos {G1, . . . , GL}que interaccionan, éstos pueden modelarse como un grafo multicapa de capas {G1, . . . , GL}, cuyas capas cruzadas Eαβ se corresponden con las interaciones entre GαyGβ[6]. En la Véase la Figura 2.4, podemos observar una transformación de dos grafos interconectados en un grafo multicapa. Cada grafo coloreado de un color distinto en la parte de la izquierda se corresponde con una capa diferente de la parte de la derecha. Redes multidimensionales: Formalmente, un multigrafo de aristas etiquetadas o grafo multidimensional [4] es una tripla G= (V,E,D)donde 12 Figura 2.4: Transformación de dos grafos interconectados en un grafo multicapa. Ves un conjunto de vértices o nodos, Des un conjunto de etiquetas que representan las dimensiones, y Ees un conjunto de aristas etiquetadas, es decir, E={(u,v,d),u,v∈V,d∈D} Se asume que, dado un par de nodos u,v∈Vy una etiqueta d∈D, solo existe una arista (u,v,d). Además, si el modelo considerado es un grafo dirigido, las aristas (u,v,d)y(v,u,d)son distintas. Luego, dado |D|, cada par de nodos en Gpuede estar conectado por a lo sumo |D|posibles aristas. Cuando sea necesario, es posible considerar pesos para las aristas, dejando éstas de ser triplas para ser consideradas como 4−tuplas (u,v,d,w), siendo wun número real representando el peso de la relación entre u,v∈V, y etiquetada con d∈D. Un grafo multidimensional G= (V,E,D)puede modelarse como un grafo multiplex (y por tanto, como un grafo multicapa), asociando cada etiqueta a una capa. Concretamente, Gpuede ser asociado a una red multicapa de capas {G1, . . . , G|D|}, donde para cada α∈D,Gα= (Vα,Eα), siendo Vα=Vy Eα={(u,v)∈V×V,(u,v,d)∈Eyd=α} Eαβ ={(v,v),v∈V}para cada 1 ≤α6=β≤ |D| En la Figura 2.5, podemos observar una transformación de un grafo multidimensional en un grafo multicapa, con D={rojo, amarillo, verde} yd∈Dasociado a cada arista del grafo. Podemos ver como en el grafo multicapa correspondiente, cada etiqueta de D(es decir, cada color en 13 este caso) representa una capa. Nótese que las aristas intercapa que van de la capa con las etiquetas rojas a la de las verdes están superpuestas con las que van de la de las rojas a la capa de las amarillas y las que van de la capa de las amarillas a la capa de las verdes. Figura 2.5: Transformación de un grafo multidimensional en un grafo multicapa. Redes multinivel: Sea G= (V,E)un grafo. Una red o grafo multinivel [5] es una tripla M= (V,E,S), donde S={S1, . . . , Sp}es una familia de subgrafos Sj= (Vj,Ej), con j=1, . . . , pde Gtal que V= p [ j=1 Vj,E= p [ j=1 Ej El grafo Ges el grafo proyección de M, y cada subgrafo Sj∈ S se le llama slice (en castellano “rebanada” o “rodaja”) de un grafo multinivel M. Evidentemente, cada grafo multinivel M= (V,E,S)puede interpretarse como una red multicapa con capas {S1, . . . , Sp}y capas cruzadas Eαβ ={(v,v),v∈Vα∩Vβ} para cada 1 ≤α6=β≤p. Es directo verificar que cada grafo multiplex es un grafo multinivel, y cada grafo multinivel M= (V,E,S)es un grafo multiplex si y solo si Vα=Vβ,∀α,β∈ {1, . . . , p}. En la Figura 2.6 tenemos un ejemplo de un grafo multinivel con V={v1,v2,v3,v4,v5}, donde cada capa contiene un subgrafo Si, con i=1,2,3. Nótese que las aristas intercapa que van de S1aS3están 14 Figura 2.6: Ejemplo de un grafo multinivel. superpuestas con las que van de S1aS2y las que van de S2aS3. Hipergrafos: Un hipergrafo [1] es un par H= (V,H), donde Ves un conjunto de nodos no vacío y H={H1, . . . , Hp}es una familia de subconjuntos no vacíos de V, cada uno de ellos llamado hiperenlace de H. Ahora, si G= (V,E)es un grafo, una hiperestructura S= (V,E,H)es una tripla formada por el conjunto de vértices V, el conjunto de aristas E y el conjunto de hiperaristas H. Si H= (V,H)es un hipergrafo, puede modelarse como una red o grafo multicapa, tal que para cada hiperenlace Figura 2.7: Ejemplo de una transformación de un hipergrafo con tres hiperaristas en un grafo multicapa. 15 h= (v1, . . . , vk)∈Hdefinimos una capa Ghque será un grafo completo de nodos v1, . . . , vk, y las capas cruzadas son Eαβ ={(v,v),v∈Vα∩Vβ} En el ejemplo de (2.7), tenemos una transformación de un hipergrafo con tres hiperaristas en un grafo multicapa. El conjunto de nodos de la parte de la izquierda define tres hiperaristas, H1,H2yH3, cada una de ellas asociada con una capa en la cual hay un grafo completo formado a partir de sus nodos correspondientes. En este trabajo daremos resultados generales, sin aplicarlos a ningún tipo concreto de red multicapa. Sin embargo, podrían aplicarse a cualquiera de ellas. Bastaría considerar el tipo de grafo que deseemos, y aplicar el procedimiento en cuestión. 16 redes que estudiamos anteriormente: min (m´ ax w∈W ∑ α∈M ∑ aα∈Aα daαxw aα+∑ α,β∈M ∑ aαβ∈Aαβ daαβ xw aαβ  + +∑ α∈M ∑ aα∈Aα Caαxaα+∑ α,β∈M ∑ aαβ∈Aαβ Caαβ xaαβ )(3.9) s.a  ∑ aα∈δ+(vα) xw aα+∑ aβα∈δ+(vα) xw aβα  −  ∑ aα∈δ−(vα) xw aα+∑ aαβ∈δ−(vα) xw aαβ  =   1 si v=oα w −1 si v=dα w(3,2) 0 en otro caso xaα≥xw aα,∀w∈W,∀aα∈Aα,∀α∈ {1, . . . , m}(3,3) xaαβ ≥xw aαβ ,∀w∈W,∀aαβ ∈Aαβ,∀α,β∈ {1, . . . , m}(3,4)  ∑ aα∈δ+(vα) fw aα+∑ aβα∈δ+(vα) fw aβα  −  ∑ aα∈δ−(vα) fw aα+∑ aαβ∈δ−(vα) fw aαβ  =   Rwsi v=oα w −Rwsi v=dα w(3,6) 0 en otro caso faα=∑ w∈W fw aα≤Kaαxaα(3,7) faαβ =∑ w∈W fw aαβ ≤Kaαβ xaαβ (3,8) La expresión que se encuentra entre paréntesis en nuestra función objetivo vuelve a representar la distancia total recorrida por un par w. Además, la restricciones son las mismas que las del problema de la mediana. Nótese también que, en el caso de tener grafos no dirigidos, la expresión sería la misma sustituyendo arcos por aristas. El problema de centro tipo origen-destino que aparece en este trabajo está muy relacionado con un caso concreto del que se puede observar en [16]. Aquí, Schmidt y Schöbel se plantean el problema de encontrar una subred en un grafo dado, de una longitud menor o igual a una longitud máxima dada, tal que se 23 minimice la longitud del camino más largo de todos los que van de sus orígenes a sus destinos respectivos en cada par origen-destino. El caso concreto con el que se relaciona nuestro problema es con el que surge al tomar como longitud máxima una lo suficientemente grande como para que la longitud no constituya una restricción, como por ejemplo, infinito. Sin embargo, la estructura y el cariz del problema son distintos, pues si quisieramos añadir restricciones distinguiendo capas, ésto solo sería posible considerando nuestro problema. Nótese, finalmente, que tanto el problema propuesto por Schmidt y Schöbel como el estudiado en esta sección son fuertemente NP−duros. 3.2.3. Problema de cobertura Supongamos que tenemos las mismas condiciones que en los dos apartados anteriores. Sin embargo, ahora queremos maximizar el número de pares origen destino que están cubiertos, es decir, aquellos que recorren una distancia menor o igual a un cierto r0dado. A r0se le denomina radio o umbral máximo. Las variables de nuestro problema serán las siguientes: xw aα=1 si aαes usado por w 0 en otro caso xw aαβ =1 si aαβ es usado por w 0 en otro caso yw=1 si westá cubierto. 0 en otro caso xaα=1 si aαes usada 0 en otro caso xaαβ =1 si aαβ es usada 0 en otro caso Como ocurría con los dos problemas anteriores, la formulación del problema de cobertura estaría compuesta por la siguiente función objetivo y por ciertas restricciones, además de las restricciones que aparecían en el problema de diseño 24 de redes que estudiamos anteriormente: máx    ∑ w∈W yw− ∑ α∈M ∑ aα∈Aα Caαxaα+∑ α,β∈M ∑ aαβ∈Aαβ Caαβ xaαβ     (3.10) s.a ∑ α∈M ∑ aα∈Aα daαxw aα+∑ α,β∈M ∑ aα∈Aαβ daαβ xw aαβ ≤r0yw(3.11)  ∑ aα∈δ+(vα) xw aα+∑ aβα∈δ+(vα) xw aβα  −  ∑ aα∈δ−(vα) xw aα+∑ aαβ∈δ−(vα) xw aαβ  =   1 si v=oα w −1 si v=dα w(3,2) 0 en otro caso xaα≥xw aα,∀w∈W,∀aα∈Aα,∀α∈ {1, . . . , m}(3,3) xaαβ ≥xw aαβ ,∀w∈W,∀aαβ ∈Aαβ,∀α,β∈ {1, . . . , m}(3,4)  ∑ aα∈δ+(vα) fw aα+∑ aβα∈δ+(vα) fw aβα  −  ∑ aα∈δ−(vα) fw aα+∑ aαβ∈δ−(vα) fw aαβ  =   Rwsi v=oα w −Rwsi v=dα w(3,6) 0 en otro caso faα=∑ w∈W fw aα≤Kaαxaα(3,7) faαβ =∑ w∈W fw aαβ ≤Kaαβ xaαβ (3,8) La función objetivo busca maximizar la cantidad de pares cubiertos minimizando el coste asociado a los arcos usados, tanto intracapa (primer sumando de la expresión entre corchetes de la función objetivo) como intercapa (segundo sumando de esa misma expresión). Por otro lado, la restricción (3.11) obliga a que, cuando ywes cero, es decir, cuando no forma parte del conjunto de cobertura, entonces la distancia recorrida por el par wes obligadamente 0. Sin embargo, cuando ywvale uno, la distancia recorrida debe ser menor que r0. El resto de restricciones coinciden con las que aparecían en el Problema de la mediana y el Problema del centro. De nuevo, al igual que en los dos problemas anteriores, bastaría sustituir arcos 25 por aristas para obtener la formulación para el caso de grafos no dirigidos. 3.2.4. Problema restringido En las secciones anteriores, hemos estado utilizando los objetivos de los problemas de localización más típicos en el diseño de redes en grafos multicapa. A continuación vamos a ver restricciones necesarias para formular variaciones de estos problemas donde la estructura multicapa juega un papel fundamental. Centrémonos por ejemplo en el problema de cobertura. Consideremos un grafo multicapa en el que tenemos un conjunto de pares origen destino que queremos satisfacer. Sin embargo, puede que por las propias características de nuestro grafo, a la hora de resolver el problema, todos los pares cubiertos tuvieran sus nodos en las capas superiores, sin cubrirse los pares de las capas inferiores. Para evitar esto, bastaría añadir una restricción que obligara a que cada capa tuviera que contener al menos un cierto número de nodos origen o destino que estén cubiertos. Una primera opción sería obligar a que cada capa tuviera que tener al menos una cantidad fijada de antemano de nodos destino cubiertos. Para ello, basta considerar el vector M-dimensional γ, cuyas componentes son constantes, y el siguiente conjunto de restricciones: ∑ vα i∈Vα zα i≥γα,∀α=1, . . . , M(3.12) donde: zα i=(ywsi vα i=dα w, con w= (oα w,dβ w)∀α∈ {1, . . . , M} 0 en otro caso También podemos considerar obligar a que cada capa tuviera al menos una cantidad fijada de antemano de nodos origen. De igual manera que en el caso anterior, consideramos el vector M-dimensional δ, cuyas componentes son constantes, y el siguiente conjunto de restricciones: 26 ∑ vα i∈Vα tα i≥δα,∀α=1, . . . , M(3.13) donde: tα i=(ywsi vα i=oα w, con w= (oα w,dβ w)∀α∈ {1, . . . , M} 0 en otro caso Sin embargo, una segunda opción mucho más útil, podría ser una restricción que obligara a que el número de nodos destino cubiertos en cada capa debe ser el mismo, y además, todos los nodos cubiertos estén repartidos de forma equitativa por todas las capas. Sustituimos (3.12) por la restricción siguiente: ∑ vα i∈Vα zα i≥ b∑wyw Mc,∀α=1, . . . , M(3.14) Esta restricción puede resultarnos conveniente si tenemos el mismo número de nodos destino en cada capa. Pero si esto no ocurre, la restricción carece de sentido. Combinando las dos anteriores, podemos considerar el vector estocástico M-dimensional γ, cuyas componentes son constantes, donde cada una representa la proporción de la cantidad total de nodos destino cubiertos que buscamos que tenga cada capa. La restricción a considerar sería: ∑ vα i∈Vα zα i≥γαb∑wyw Mc,∀α=1, . . . , M(3.15) Nótese que, para evitar que la expresión anterior sea demasiado restrictiva, bastaría multiplicar el término de la derecha de la desigualdad por una constante entre 0 y 1. Mientras más cercana esté dicha constante a 1, más restrictiva será la expresión, mientras que si es cercana a 0, el problema tendrá una mayor libertad para cubrir los nodos. La restricciones (3.14) y (3.15) pueden reformularse para los nodos origen análogamente, considerando las variables tα i,∀vα i∈Vα, con i=1, . . . , m. 27 28 Capítulo 4 Problemas puntuales En este capítulo, haremos referencia como problemas puntuales aquellos en los que ya no tenemos pares orígenes-destino que satisfacer, sino que consideramos diferentes objetivos teniendo en cuenta los nodos del grafo, sin distinguir si un nodo es un origen o un destino de algún par. 4.1. Problema puntual del centro Definición 1. Llamamos centro de un grafo multicapa Mal vértice que minimiza el máximo de las distancias al resto de vértices de M. Para calcular el centro de un grafo multicapa, basta con seguir los pasos siguientes, a partir de la matriz de distancias más cortas D. Sea n=|V|: 1. Calculamos mipara cada columna de D, donde mi=el máximo de todas las entradas de la columna ide D. 2. Si mk=m´ ın{m1, . . . , mn}, entonces mkes el centro de M. A continuación, introduciremos un ejemplo para visualizar este procedimiento con una mayor claridad. Consideremos un grafo concreto (véase la Figura 4.1). Nótese que en los ejemplos considerados, denotaremos dos vértices cualesquiera vα iyvβ j, con α6=βcon el mismo índice, es decir, i=j, si ambos vértices hacen referencia al mismo vértice pero en capas distintas. Este es el motivo por el que en la capa 2 de la Figura 4.1 usamos v2 4en lugar de v2 3, sin haber en la capa 2 un vértice con un 3 como subíndice, dado que v1 3yv2 4son totalmente independien- 29 tes y distintos. Figura 4.1: Ejemplo de un grafo multicapa con pesos en sus aristas intercapa e intracapa Definamos las matrices de distancias D1yD2: v1 1v1 2v1 3 D1= v1 1 v1 2 v1 3   0 4 3 4 0 2 3 2 0   v2 1v2 2v2 4 D2= v2 1 v2 2 v2 4   0 7 1 7 0 6 1 6 0   A continuación definimos D12, que coincidirá con la traspuesta de D21 debido a que las distancias son simétricas. v2 1v2 2v2 4 D12 = (D21)t= v1 1 v1 2 v1 3   1 5 2 5 1 6 4 3 5   30 Por tanto, nos queda que: D=            0 4 3 1 5 2 4 0 2 5 1 6 3 2 0 4 3 5 1 5 4 0 7 1 5 1 3 7 0 6 2 6 5 1 6 0            Asumiremos que los pesos asociados a cada vértice valen uno para una mayor facilidad de cálculo. Si calculamos mipara cada columna de D, y calculamos su mínimo, obtenemos que: mk=m´ ın{5, 6,5,7,7,6}=5 Por tanto, tenemos que los centros son los vértices v1 1yv1 3. Definición 2. La distancia del vértice más lejano del centro del grafo multicapa se denomina radio r0de M. Luego, podemos escribir que r0=m´ ın vα i∈Vα,α∈Mm´ ax vα j∈Vα,α∈Md(vi,vj) Por ejemplo, el radio del grafo de la Figura 4.1 es 5. Tomemos a continuación un punto x0de la arista e1= (v1 1,v1 3), de forma que d(x0,v1 1) = 2, como podemos observar en la Figura 4.2. Figura 4.2: Localización del x0 31 Vemos que, para x0, se cumple que: m´ ax vα i∈Vα,α∈Md(vα i,x0) = 4<d(v1 1,v2 2) = 5 Esto nos lleva a pensar que debe haber puntos en un grafo multicapa M, como x0en el grafo de la Figura 4.2, que están localizados más centralmente que los propios centros de M. Definición 3. Definimos como centro absoluto de un grafo multicapa Mal x0en M para el cual se cumple que m´ ın x∈M m´ ax vα i∈Vα,α∈Mhα id(vα i,x) = m´ ax vα i∈Vα,α∈Mhα id(vα i,x0)(4.1) Definición 4. Definimos el radio absoluto de Mde la siguiente manera: r(x0) = m´ ın x∈M m´ ax vα i∈Vα,α∈Mhα id(vα i,x) La ecuación (4.1) puede reescribirse de la siguiente forma: m´ ın {m´ ın eα∈Eα"m´ ın x∈eαm´ ax vα i∈Vα,α∈Mhα id(vα i,x)#, (4.2) m´ ın eαβ∈Eαβ "m´ ın x∈eαβ m´ ax vα i∈Vα,α∈Mhα id(vα i,x)#}=r(x0) Sin embargo, a partir de la ecuación (4.2), deducimos que el problema de encontrar el centro absoluto x0puede reducirse al problema de resolver tantos problemas “min-max” como aristas intercapa e intracapa tenga nuestro grafo, y quedarnos con el mínimo de lo obtenido sólo considerando las intercapa y lo obtenido sólo considerando las intracapa. Más precisamente, sea xeγun punto de la arista eγtal que: m´ ın x∈eγm´ ax vα i∈Vα,α∈Mhα id(vα i,x) = m´ ax vα i∈Vα,α∈Mhα id(vα i,xeγ) = r(xeγ)(4.3) Entonces, decimos que xeγes un centro local de Men eγ, y por tanto, tenemos que la expresión m´ ın eα∈Eα,α∈M[r(xeα)](4.4) 32 con una mayor claridad. Consideremos de nuevo el grafo multicapa de la Figura 4.1, para el cual tenemos ya calculada la matriz de distancias D: D=            0 4 3 1 5 2 4 0 2 5 1 6 3 2 0 4 3 5 1 5 4 0 7 1 5 1 3 7 0 6 2 6 5 1 6 0            Si calculamos sipara cada columna de D, y calculamos su mínimo, obtenemos que: sk=m´ ın{15, 18,17,18,22,20}=15 Por tanto, tenemos que la mediana es el vértice v1 1. El concepto de mediana absoluta es más general, porque involucra pesos para cada uno de los vértices del grafo. Definición 6. Decimos que un punto x0de un grafo multicapa Mcon vértices ponderados es una mediana absoluta de Msi, para todo punto x en M, ∑ α∈M ∑ vα i∈Vα hα id(vα i,x0)≤∑ α∈M ∑ vα i∈Vα hα id(vα i,x) donde hα ies el peso de cada vα i∈Vα Teorema 1. Existe al menos un vértice del grafo multicapa que es una mediana absoluta. Demostración: Para demostrar este teorema, hace falta ver que si x0es un punto arbitrario en M, con x06=vα i, con vα i∈Vα,∀α∈M, entonces siempre existirá un vértice vγ k en la capa γde M, tal que: ∑ α∈M ∑ vα i∈Vα hα id(vα i,x0)≥∑ α∈M ∑ vα i∈Vα hα id(vα i,vγ k) Esto probaría que vγ ksería una mediana absoluta. 39 Sea x0un punto de una arista eγ= (vγ p,vγ q)de M. Sabemos que: d(vα i,x0) = m´ ın{d(x0,vγ p) + d(vγ p,vα i),d(x0,vγ q) + d(vγ q,vα i)} Definimos a continuación los conjuntos PyQde la siguiente forma: P={vα i|d(vα i,x0) = d(x0,vγ p) + d(vγ p,vα i),∀vα i∈Vα,∀α∈M} Q={vα i|d(vα i,x0) = d(x0,vγ q) + d(vγ q,vα i),∀vα i∈Vα,∀α∈M} Nótese que Pes el conjunto formado por los vértices de Mpara los cuales, si se trazara el camino más corto desde cada uno de ellos hasta x0, éste pasa por vγ p. Por otro lado, Qestá formado por los vértices de Mpara los cuales tal camino más corto a x0pasa por vγ q. Luego, podemos escribir: ∑ α∈M ∑ vα i∈Vα hα id(vα i,x0) = ∑ α∈M ∑ vα i∈P hα i[d(x0,vγ p) + d(vγ p,vα i)] + (4.7) +∑ α∈M ∑ vα i∈Q hα i[d(x0,vγ q) + d(vγ q,vα i)] Estudiamos a continuación la ecuación anterior considerando los dos casos que pueden darse por separado. Caso 1: Cuando ∑α∈M∑vα i∈Phα i≥∑α∈M∑vα i∈Qhα i Tenemos que: d(x0,vγ q) = d(vγ p,vγ q)−d(x0,vγ p) Si sustituimos esto en la ecuación (4.7), nos da: ∑ α∈M ∑ vα i∈Vα hα id(vα i,x0) = ∑ α∈M ∑ vα i∈P hα i[d(x0,vγ p) + d(vγ p,vα i)] + (4.8) +∑ α∈M ∑ vα i∈Q hα i[d(vγ p,vγ q)−d(x0,vγ p) + d(vγ q,vα i)] También sabemos que, como hemos considerado que la métrica en el plano es la euclídea, tenemos que: d(vγ q,vγ p) + d(vγ q,vα i)≥d(vγ p,vα i),∀α∈M Si usamos esta desigualdad en la ecuación (4.8), obtenemos: ∑ α∈M ∑ vα i∈Vα hα id(vα i,x0)≥∑ α∈M ∑ vα i∈P hα i[d(x0,vγ p) + d(vγ p,vα i)] + +∑ α∈M ∑ vα i∈Q hα i[d(vγ p,vα i)−d(x0,vγ p)] 40 Si reordenamos el término de la derecha de la desigualdad anterior, obtenemos: ∑ α∈M ∑ vα i∈Vα hα id(vα i,x0)≥∑ α∈M ∑ vα i∈Vα hα id(vγ p,vα i) + +∑ α∈M"∑ vα i∈P hα i−∑ vα i∈Q hα i#d(x0,vγ p) Debido a la hipótesis inicial de este caso 1, concluimos con que: ∑ α∈M ∑ vα i∈Vα hα id(vα i,x0)≥∑ α∈M ∑ vα i∈Vα hα id(vα i,vγ p) Caso 2: Cuando ∑α∈M∑vα i∈Phα i≥∑α∈M∑vα i∈Qhα i La demostración es análoga al caso 1. Sustituimos en (4.7)d(x0,vγ p) = d(vγ p,vγ q)−d(vγ q,x0). Luego, obtenemos: ∑ α∈M ∑ vα i∈Vα hα id(vα i,x0) = ∑ α∈M ∑ vα i∈P hα i[d(vγ p,vγ q)−d(vγ q,x0) + d(vγ p,vα i)] + +∑ α∈M ∑ vα i∈Q hα i[d(x0,vγ q) + d(vγ q,vα i)] (4.9) Y esta ecuación, análogamente a como hacíamos en el caso 1, puede reducirse a la siguiente desigualdad: ∑ α∈M ∑ vα i∈Vα hα id(vα i,x0)≥∑ α∈M ∑ vα i∈Vα hα id(vα i,vγ q) + +∑ α∈M"∑ vα i∈P hα i−∑ vα i∈Q hα i#d(x0,vγ q) Debido a la hipótesis inicial de este caso 1, concluimos con que: ∑ α∈M ∑ vα i∈Vα hα id(vα i,x0)≥∑ α∈M ∑ vα i∈Vα hα id(vα i,vγ q) Si en lugar de considerar x0un punto de la arista eγ= (vγ p,vγ q), con γ∈M, hubiéramos considerado x0un punto de la arista eγδ = (vγ p,vδ q), con γ,δ∈M, la demostración sería análoga, bastando sustituir vγ qpor vδ q. Con esto concluye 41 la demostración. Luego, gracias a este teorema podemos afirmar con total certeza que cuando nos referimos a mediana absoluta nos referimos a la propia mediana como tal. Señalar además, que el problema de encontrar la mediana en un grafo multicapa es un problema NP−duro. 4.3. Problema puntual del p-centro Anteriormente, hemos estudiado como hallar la localización óptima del centro de un grafo mediante el problema puntual del centro. Sin embargo, existe una generalización de dicho problema, en el que buscamos resolver el problema de localizar ppuntos en el grafo minimizando la máxima distancia desde cualquier vértice del grafo multicapa al punto más cercano de esos ppuntos. Consideramos así M= (G,C)un grafo multicapa. Recordemos que Pαes el conjunto de todos los puntos en todas las aristas intracapa de la capa α∈M, y Pα,βel conjunto de todos los puntos en todas las aristas intercapa entre las capas α∈My β∈M. Luego, tenemos definidos PyVde la siguiente manera P= [ α∈M Pα!∪ [ α,β∈M Pαβ  V=[ α∈M Vα Consideramos el conjunto de puntos πcomo π≡P∪V. Definición 7. Un conjunto de p-centros de un grafo multicapa es cualquier conjunto de p puntos pertenecientes ya sea a los vértices o a las aristas (tanto intracapa como intercapa), que minimizan la máxima distancia desde un vértice al p-centro más próximo. Para p=1,2, . . ., el problema de los p-centros se define de la siguiente manera: Encuentra un conjunto Xp∗con |Xp∗| ≤ pde manera que, para cualquier conjunto Xp⊆π, con |Xp| ≤ p, se tiene que m´ ax α∈M{m´ ax vα i∈Vαd(vα i,Xp)} ≥ m´ ax α∈M{m´ ax vα i∈Vαd(vα i,Xp∗)}(4.10) donde d(vα i,Xp)≡m´ ınw∈Xpd(vα i,w) 42 Denotamos además: τXp≡m´ ax α∈M{m´ ax vα i∈Vα d(vα i,Xp) τM≡m´ ax α∈M{m´ ax vα i∈Vα d(vα i,Xp∗)} Por tanto, podemos reescribir (4.10) como: τXp≥τM Los miembros de Xp∗son los p-centros de M. Es decir, el conjunto Xp∗ minimiza la máxima distancia τMentre un vértice de My el p-centro más próximo. Además, Xp∗no tiene por qué ser único. Si se nos da el conjunto de p-centros de M, entonces cada vértice de M puede ser asociado de forma arbitraria a su p-centro más cercano. Sea Vk un subconjunto cualquiera de Vasociado con kperteneciente al p-centro. Consideramos la función fk(c)≡m´ axα∈M{m´ axvα i∈Vkd(vα i,c)}, donde c∈π. Si k, un p-centro, no es un mínimo global de fksobre π, entonces claramente el mínimo global de fksobre πpuede reemplazar a ken el conjunto de p-centro. Además, d(vα i,c),∀vα i∈Vα,∀i∈M, es una función de ccontinua, lineal y definida a trozos, con dos trozos a lo sumo. Luego d(vα i,c)tiene pendiente ±1 cuando la pendiente existe. Sea P0⊆Pel conjunto de todos los puntos en las aristas de Mtal que: c∈P0⇐⇒ para algún vα p∈Vα, con α∈M, y para algún Vβ q∈Vβ, con β∈M, tal que vα p6=vβ q, con α=βoα6=β,ces el único punto en su arista tal que d(vα p,c) = d(vβ q,c) Sea π0≡P0∪V. Luego, el conjunto π0contiene todos los mínimos globales de fi. Por tanto, existe un conjunto de p-centros contenido en π0, y |P0|<∞. A continuación, veremos que podemos localizar un conjunto de p-centros resolviendo un número finito de problemas de cobertura. Recordemos que un problema de cobertura mínima tiene la siguiente forma: 43 Sea Auna matriz de dimensión p×nde ceros y unos. Sea xun n-vector desconocido de ceros y unos. El problema de minimizar ∑n i=1xital que cada componente de Ax sea mayor o igual que 1 es a lo que llamamos problema de cobertura mínima. Consideremos así H, una matriz con |V|filas y |π0|columnas, con cada entrada hij igual a la distancia más corta entre vα i∈Vα, con α∈M, y j∈π0. Un conjunto Mde pcolumnas, µ1, . . . , µpde H, tal que τp≡m´ ax α∈M(m´ ax vα j∈Vα m´ ın i=1,...,phj,µi) sea minimizado, se corresponde con el conjunto de p-centros de G. El problema de hallar los p−centros de un grafo multicapa es NP−duro, tal y como ocurre con los grafos unicapa (véase [12]). Lo mismo ocurre con la mayoría de las variantes del problema de los p-centros para grafos unicapa. Frederickson [8] presentó un algoritmo de complejidad O(n)para localizar pinstalaciones en un árbol unicapa con vértices no ponderados. Sin embargo, no se conoce aún un algoritmo exacto para la versión ponderada del problema de los p-centros, ni en un grafo unicapa ni en uno multicapa, incluso para un valor de pfijado. Veamos a continuación un ejemplo. Consideremos de nuevo el grafo de la Figura 4.8, para el cual tenemos calculado el conjunto π0porque lo hemos hallado en la sección del Problema puntual del centro. Por tanto, el siguiente paso sería calcular H: Figura 4.8: Ejemplo de un grafo multicapa 44 H=            0 4 3 1 5 2 4,5 2,29 2 1 4 0 2 5 1 6 4,5 2,71 2 3 3 2 0 4 3 5 6,5 0,71 4 4 1 5 4 0 7 1 3,5 3,29 3 2 5 1 3 7 0 6 3,5 3,71 3 4 2 6 5 1 6 0 2,5 4,29 4 3            Si buscamos calcular el 2-centro, debemos probar todas las combinaciones posibles de las diez columnas tomadas de dos en dos, y quedarnos con aquella que haga mínimo τ2. Para nuestro ejemplo, hay tres soluciones posibles para las cuales obtenemos que la máxima distancia desde un vértice a su 2-centro más cercano es mínima: v1 1yv1 2,v1 2yv2 1, y por último, v1 2yv2 4. Dicha distancia para las tres soluciones vale 2. 4.4. Problema puntual de la p-mediana En esta sección, empezaremos generalizando el concepto de mediana, al igual que hemos hecho con el concepto de centro en el problema de los p-centros. Definición 8. Consideramos M, un grafo ponderado. Sea Xpun conjunto de p puntos x1,x2, . . . , xpen M, y sea d(vα i,Xp) = m´ ın[d(vα i,x1),d(vα i,x2), . . . , d(vα i,xp)],α∈M El conjunto de puntos Xp∗será una p-mediana de Msi, para todo Xpen M ∑ α∈M ∑ vα i∈Vα hα id(vα i,Xp∗)≤∑ α∈M ∑ vα i∈Vα hα id(vα i,Xp) donde recordemos que hα ies el peso asociado al vértice vα i∈Vα, con α∈M, en M. Nótese que el problema de hallar la p−mediana de un grafo multicapa es NP−duro, tal y como ocurre con los grafos unicapa (véase [13]). A continuación, veamos un procedimiento para hallar Xp∗. Teorema 2. Existe un subconjunto Vp∗de V que contiene p vértices tal que, para todo conjunto X de p puntos en M, se cumple que 45 ∑ α∈M ∑ vα i∈Vα hα id(vα i,X)≥∑ α∈M ∑ vα i∈Vα hα id(vα i,Vp∗) Demostración: Sean los puntos de Xlos puntos x1,x2, . . . , xpde M. Definimos a continuación los conjuntos S1, . . . , Spde la siguiente forma: Sk={vα i|d(vα i,xk) = d(vα i,X),∀vα i∈Vα,∀α∈M},∀k∈ {1, . . . , p} Nótese que Skes el conjunto formado por los vértices de Mpara los cuales xk es el punto más cercano de los que figuran en X. Luego, podemos escribir: ∑ α∈M ∑ vα i∈Vα hα id(vα i,X) = p ∑ k=1 ∑ α∈M ∑ vα i∈Sk hα id(vα i,xk)(4.11) Por otro lado, si consideramos el primer término de la suma en kdel miembro derecho, tenemos que ∑ α∈M ∑ vα i∈S1 hα id(vα i,x1) = ∑ α∈M ∑ vα i∈S1 hα id(vα i,x1) + p ∑ k=2 ∑ α∈M ∑ vα i∈Sk 0d(vα i,x1)(4.12) Por tanto, podemos escribir ∑ α∈M ∑ vα i∈S1 hα id(vα i,x1) = p ∑ k=1 ∑ α∈M ∑ vα i∈Sk h0 iαd(vα i,x1)(4.13) donde h0 iα=hα isi vα i∈S1 0 en otro caso Sin embargo, en la Sección 4.2, probamos que existe un vértice vγ1 i1∈Vγ1, con γ1∈M, tal que ∑ α∈M ∑ vα i∈Vα h0 iαd(vα i,x1)≥∑ α∈M ∑ vα i∈Vα h0 iαd(vα i,vγ1 i1)(4.14) 46 Combinando (4.13)y(4.14), obtenemos ∑ α∈M ∑ vα i∈S1 hα id(vα i,x1)≥∑ α∈M ∑ vα i∈Vα hα id(vα i,vγ1 i1)(4.15) Si realizamos el mismo razonamiento, llegamos a las siguientes desigualdades: ∑ α∈M ∑ vα i∈S2 hα id(vα i,x2)≥∑ α∈M ∑ vα i∈Vα hα id(vα i,vγ2 i2)(4.16) . . . ∑ α∈M ∑ vα i∈Sp hα id(vα i,xp)≥∑ α∈M ∑ vα i∈Vα hα id(vα i,vγp ip) Si tomamos los miembros derechos de las desigualdades de (4.16) y usamos la igualdad (4.11), obtenemos: ∑ α∈M ∑ vα i∈Vα hα id(vα i,X)≥ p ∑ k=1 ∑ α∈M ∑ vα i∈Sk hα id(vα i,vγk lk)(4.17) Sea Vp∗={vγ1 l1, . . . , vγp lp}. Luego, tenemos que ∑ α∈M ∑ vα i∈Vα hα id(vα i,Vp∗)≤ p ∑ k=1 ∑ α∈M ∑ vα i∈Sk hα id(vα i,vγk lk)(4.18) Combinando (4.17)y(4.19), obtenemos ∑ α∈M ∑ vα i∈Vα hα id(vα i,X)≥∑ α∈M ∑ vα i∈Vα hα id(vα i,Vp∗)(4.19) lo cual demostraría el teorema. Este teorema prueba que, para hallar una p-mediana, solo debemos examinar todos los subconjuntos de Vque contengan pvértices. Sin embargo, no prueba que toda p-mediana de Mconsista en un conjunto de pvértices de M. Veamos un ejemplo numérico de como llevar a cabo el procedimiento para encontrar la p-mediana de un grafo multicapa. Consideremos el grafo ponderado Mde la Figura 4.9, con los pesos considerados en la Tabla 4.2. Nos gustaría encontrar una 3-mediana de M. Los pasos a seguir son los siguientes: 47 Figura 4.9: Ejemplo de un grafo multicapa con pesos en sus aristas intercapa e intracapa Capa Vértice Peso Capa 1 v1 14 v1 26 v1 37 Capa 2 v2 15 v2 26 v2 44 Capa 3 v3 23 v3 42 v3 55 v3 61 Cuadro 4.2: Tabla de los pesos de cada vértice de la Figura 4.9 1. Lo primero será calcular las matrices de distancias correspondientes a cada capa de M: v1 1v1 2v1 3 D1= v1 1 v1 2 v1 3   0 4 3 4 0 2 3 2 0   48 dad. Nuestro objetivo es encontrar una cobertura de Mque contenga kvértices y cubra el máximo número posible de vértices o nodos. A continuación, veamos cuáles serían las variables de nuestro problema: xα i=1 si vα iestá cubierto 0 en otro caso yα i=1 si vα ipertenece al cobertura. 0 en otro caso Definimos para cada vα iel conjunto formado por todos los vértices que se encuentran a una distancia menor o igual que el rdado: Nα i={vβ j∈Vβ|d(vα i,vβ j)≤r} Nótese que d(vα i,vα i) = 0, por lo que se tiene que cada vértice pertenece a su propio conjunto Nα i. La formulación del problema sería la siguiente: máx ∑ α∈M ∑ vα i∈Vα xα i(4.28) s.a xβ j≥yα i,∀vα i∈Vα,∀vβ j∈Nα i,∀α,β∈M(4.29) ∑ α∈M ∑ vα i∈Vα yα i=k(4.30) xβ j≤∑ vα i∈Nβ j yα i,∀vβ j∈Vβ,∀β∈M(4.31) Nótese que la expresión (4.29) obliga a que los vértices que se encuentren a una distancia menor de r de un vértice de la cobertura, estén cubiertos. La restricción (4.29) obliga a que se cumpla lo mismo, pero para las aristas intracapa. Por otro lado, la restricción (4.30) obliga a que el número de nodos de la cobertura sea k, y la restricción (4.31) obliga a que si un nodo está cubierto, debe 55 haber al menos un nodo en la cobertura a una distancia menor o igual que rde dicho nodo. 4.5.2. Problema restringido Al igual que hicimos en el capítulo anterior, a continuación veremos como plantear los problemas que hemos visto de forma que la estructura multicapa sea imprescindible para su adecuada resolución. En esta sección, vamos a introducir también una restricción que obliga a que en cada capa debe haber un mínimo número de nodos cubiertos. Una primera opción sería obligar a que cada capa tuviera que tener una cantidad fijada de antemano de nodos cubiertos. Para ello, basta considerar el vector m-dimensional γ, cuyas componentes son constantes, y el siguiente conjunto de restricciones: ∑ vα i∈Vα xα i≥γα,∀α=1, . . . , m(4.32) Una segunda opción podría ser considerar la restricción que obliga a que el número de nodos cubiertos sea menor o igual a la parte entera inferior del total de nodos cubiertos entre el número de capas: ∑ vα i∈Vα xα i≥$∑α∈M∑vα i∈Vαxα i m%,∀α=1, . . . , m(4.33) Al igual que en el caso de los problemas del tipo origen destino, esta restricción puede resultarnos conveniente si tenemos el mismo número de vértices en cada capa. Pero si esto no ocurre, la restricción carece de sentido. Combinando las dos anteriores, podemos considerar el vector estocástico m-dimensional γ, cuyas componentes son constantes, donde cada una representa la proporción de la cantidad total de nodos cubiertos que buscamos que tenga cada capa. La restricción a considerar sería: ∑ vα i∈Vα xα i≥γα$∑α∈M∑vα i∈Vαxα i m%,∀α=1, . . . , m(4.34) 56 4.6. Problema puntual con varios pesos para cada arista Nos planteamos a continuación una variante de los problemas anteriores. En ella, vamos a suponer que las aristas de una determinada capa αtienen un peso extra al que ya tienen sólo cuando son usadas para acceder desde un vértice vβ i∈Vβ, con β6=α, a un vértice vα j∈Vα. Es evidente que la matriz de distancias Dque hemos definido para un grafo multicapa no nos vale para este problema, siendo necesario redefinir una nueva matriz de distancias que depende de ciertos parámetros λ1, . . . , λm, con un λi≥1 asociado a cada capa. De esta forma, una arista (vα p,vα q)∈Eα tendrá un peso asociado λαr(vα p,vα q)si esa arista se usa para ir desde un vértice vγ iperteneciente a otra capa a un vértice vα jde esa capa, mientras que dicha arista tendrá un peso asociado distinto r(vα p,vα q)si solo se usa para ir de vértices a vértices de una misma capa α. Nótese que si se usara una arista para ir de un vértice a otro de una misma capa, pero dicha capa fuera distinta que la capa a la que pertenece la arista, también tendría peso λαr(vα p,vα q). De esta forma, redefinimos la matriz de distancias, dependiendo ésta ahora de los nuevos parámetros. La designamos por D(λ1, . . . , λm). En la mayoría de los casos se tendrá que será menos costoso ir por un camino perteneciente a una cierta capa para ir de un vértice a otro, ambos de esa misma capa, que utilizar aristas de otras capas con dicho fin. Si esto ocurre para cada pareja de vértices de una capa, y lo mismo ocurre en cada una de las capas, entonces la matriz D(λ1, . . . , λm)sería la siguiente: D(λ1, . . . , λm) =      D1D12(λ1, . . . , λm)· · · D1m(λ1, . . . , λm) D21(λ1, . . . , λm)D2· · · D2m(λ1, . . . , λm) . . .. . ..... . . Dm1(λ1, . . . , λm)Dm2(λ1, . . . , λm)· · · Dm      Es decir, las submatrices que conforman los bloques de la diagonal principal, no dependen de los parámetros. Estas nuevas matrices de distancias no son simétricas, pues mientras que antes 57 se tenía que d(vα p,vβ q) = d(vβ q,vα p), ahora esto no tiene por qué darse. Sin ir más lejos, la distancia d(vα p,vβ q)dependerá al menos del parámetro λβsi usa aristas intracapa de Eβ, mientras que d(vβ q,vα p)dependerá al menos del parámetro λα si usa aristas intracapa de Eα. Por otro lado, si λ1=· · · =λm=1, entonces D(λ1, . . . , λm) = D. Si λi=1 para alguna capa i, eso significa que esa capa no tiene sus aristas con un peso extra al usarse por vértices de otra capa, sino que el peso sería el mismo que si se usara dicha arista para ir de un vértice a otro de esa misma capa. Vamos a ilustrar todo esto con un ejemplo. Para ello, vamos a considerar el grafo de la Figura 4.9, y vamos a tomar los siguientes valores de los parámetros: λ1=3, λ2=4 y λ3=5. La matriz de distancias que obtenemos sería la siguiente:                       0 4 3 1 1 +4λ12 4 +4λ18+λ29+λ210 +λ2 4 0 2 1 +4λ11 2 +4λ14 6 7 8 3 2 0 1 +3λ11+2λ12+3λ14+2λ16+2λ17+2λ18+2λ1 1 5 4 0 7 1 9 +λ27+λ28+λ29+λ2 5 1 3 7 0 6 3 5 6 7 1+λ25+λ24+λ21 6 0 9 7 8 9 8 4 6 8 +2λ33 9 0 2 3 4 8+λ24+2λ36+2λ38 3 +2λ37 2 0 1 2 8+λ2+λ34+3λ36+3λ38+λ33+3λ37+λ33 1 0 1 8+λ2+2λ34+4λ36+4λ38+2λ33+4λ37+2λ34 2 1 0                       Si sustituimos los valores de λ, obtendríamos la matriz: 58 D=                      0 4 3 1 13 2 16 11 12 13 4 0 2 13 1 14 4 6 7 8 3 2 0 10 7 11 10 12 13 14 1 5 4 0 7 1 13 11 12 13 5 1 3 7 0 6 3 5 6 7 5 9 8 1 6 0 9 7 8 9 8 4 6 18 3 9 0 2 3 4 12 14 16 8 13 7 2 0 1 2 17 19 21 13 18 12 3 1 0 1 22 24 26 18 23 17 4 2 1 0                      Bastaría a esta matriz aplicar los procedimientos conocidos para hallar el centro y la mediana para calcularlos. Calculamos así el máximo de cada columna y nos quedamos con el valor mínimo: m´ ın{22, 24,26,18,23,17,16,12,13,14}=12 que es el correspondiente a v3 4, el cual sería pues el centro de M. Para la mediana, sumamos los valores de cada columna, y nos quedamos con el valor mínimo de estas sumas: m´ ın{77, 82,86,89,91,79,64,57,63,71}=57 que se vuelve a corresponder con v3 4, el cual también sería la mediana de Men este caso. En este ejemplo, debe destacarse que para ir de v3 2av2 4en el caso en el que las aristas solo tienen un peso, da lo mismo seguir el camino v3 2−v2 2−v2 4que el camino v3 2−v3 4−v2 4, pues la distancia recorrida en ambos casos es 9. Lo mismo ocurre con el trayecto inverso para ir de v2 4av3 2. Sin embargo, si las aristas tienen dos pesos, el camino v3 2−v2 2−v2 4tiene asociada una distancia 3 +6λ2, mientras que el camino v3 2−v3 4−v2 4tiene asociada una distancia 9. En tal caso, la primera opción conlleva un mayor coste. 59 Para hallar la p-mediana y el p-centro, los procedimientos serían totalmente análogos a los realizados para grafos multicapa donde las aristas solo tengan un peso, con la salvedad de que la matriz de distancias considerada en cada caso es D(λ1, . . . , λm). 60 Conclusiones En este trabajo, hemos estudiado los principales problemas de localización y transporte en un tipo de grafos con una estructura que generaliza a la de los grafos con la topología clásica: los grafos multicapa. Hemos visto que existen numerosas situaciones que no son posibles de modelar mediante la Teoría de Grafos clásica, pues considerar esta estructura intrínseca en cada una de las situaciones conllevaría una gran pérdida de información y un modelo nada representativo con el caso real. Por ello, en este trabajo hemos utilizado la estructura de las redes multicapa y hemos detectar problemas de localizacion en esta estructura no reducibles a problemas en grafos con la topología clásica. Nos hemos centrado en dos tipo de problemas de localización sumamente diferenciados, dentro de los cuales hemos profundizado en el problema de la mediana, el problema del centro y el problema de cobertura, así como diversas generalizaciones de los mismos. Por un lado, hemos visto los problemas de diseño de redes en los que tenemos pares origen-destino que debemos satisfacer atendiendo a diferentes condiciones impuestas y objetivos. Por otro lado, hemos visto los problemas puntuales de localización, en los que ya no tenemos pares origen-destino que satisfacer, sino que hemos consideraremos diferentes objetivos teniendo en cuenta los nodos del grafo, sin distinguir si un nodo es origen o destino de algún par. Con este trabajo queda asentada una base para posibles investigaciones en el campo de la localización en redes complejas. Existen numerosas extensiones de los problemas presentes en el trabajo que pueden formularse, dependiendo de casos y situaciones con condiciones más específicas. La naturaleza compleja de los sistemas que tienen lugar en la vida real requiere de la aplicación de dichos 61 problemas, así como de la consideración de la estructura multicapa intrínseca en los mismos, para poder modelarlos, entenderlos y manipularlos convenientemente. Queda así justificada la gran importancia y utilidad de su estudio, así como lo significante que resulta la continuación en su investigación. 62 Bibliografía [1] C. Berge, Hypergraphs: Combinatorics of Finite Sets, North-Holland, 1989. [2] O. Berman, D. Einav, G. Handler, The zone-constrained location problem on a network, European Journal of Operational Research 53 (1991) 14-24, North-Holland. [3] S. Boccaletti, G. Bianconi, R. Criado, C. I. del Genio, J. Gómez-Gardenes, M. Romance, I. Sendiña-Nadal, Z. Wang, M. Zanin, The structure and dynamics of multilayer networks, Physics Reports, 544(1), 1-122 (2014). [4] M. Coscia, Multidimensional network analysis (Ph.D. thesis), Universitá Degli Studi Di Pisa, Dipartimento di Informatica, 2012. [5] R. Criado, J. Flores, A. García del Amo, J. Gómez-Gardeñes, M. Romance, A mathematical model for networks with structures in the mesoscale, Int. J. Computer Math. 89 (3) (2012) 219-309. [6] J. Donges, H. Schultz, N. Marwan, Y. Zou, J. Kurths, Investigating the topology of interacting networks, The European Physical Journal B 84 (4) (2011) 635-651. http://dx.doi.org/10.1140/epjb/e2011-10795-8. [7] J. Elzinga and D.W. Hearn, Geometrical solutions for some minimax location problems, Transport. Sci. 6, 379-394 (1972). [8] G.N. Frederickson, Parametric search and locating supply centers in trees. LNCS, vol. 519, pp. 299–319. Springer, Heidelberg (1991) [9] S. L. Hakimi, Optimun distribution of switching centers in a communication network and some related graph theoretic problems, The Technological Institute, Northwestern University, Evanston, Illionis (1965) 462-475. [10] S. L. Hakimi, Optimun locations of switching centers and the absolute cen- 63 ters and medians of a graph, Northwestern University, Evanston, Ill (1964) 450-459. [11] J. P. Holme, Temporal networks, Physics Reports 519 (3) (2012) 97-125. [12] O. Kariv, S.L. Hakimi, An algorithmic approach to network location problems, Part I: The p-centers, SIAM Journal on Applied Mathematics, 37(3), 513-538. [13] O. Kariv, S.L. Hakimi, An algorithmic approach to network location problems, Part II: The p-medians, SIAM Journal on Applied Mathematics, Volume 37, 539-560 [14] N. Megiddo, A. Tamir, New results on the complexity of p−center problems, SIAM J Comput 12:751-758 (1983). [15] E. Minieka, The M-center problem, Tech. Rep. 24, Administrative Sciences Department. Yale University, New Heaven, Connecticut (1968) 138-139. [16] M. Schmidt, A. Schöbel, Location of speed-up subnetworks, Annals of Operations Research (2014), 223, 379-401. [17] J. Scott, Social Network Analysis: A Handbook, SAGE Publications, London, 2000. [18] L. Solá, M. Romance, R. Criado, J. Flores, A. García del Amo, S. Boccaletti, Eigenvector centrality of nodes in multiplex networks, Chaos 23 (3) (2013) 003131. [19] S. Wasserman, K. Faust, Social Networks Analysis, Cambridge University Press, Cambridge, 1994. [20] M. Zanin, F. Lillo, Modelling the air transport with complex networks: a short review, The European Physical Journal Special Topics, 215 (1) (2013) 5-21. http://dx.doi.org/10.1140/epjst/e2013-01711-9. 64