• Author / Uploaded
• Diego Castiblanco

Citation preview

8. PAREAMIENTO 8.1. DEFINICIÓN Es un método por el cual se establece generalmente un grafo bipartito de forma que para cada elemento del grupo de vértices A le pertenezca un único elemento del grupo de vértices B, matemáticamente se expresa como un grafo G = (V, A) en donde el subconjunto de aristas A en el que ningún par de aristas es incidente sobre el mismo vértice de V. Si se desea encontrar la selección con el máximo número de aristas es un pareamiento maximal y un pareamiento completo todo vértice es un punto final de alguna arista en ella. 8.2. APLICACIONES Y ALGORITMOS Se usa el pareamiento de grafos para distribuir los elementos de un grupo A para los elemento de un grupo B de forma que no hayan repeticiones en la asignación (la asignación de profesores a unos ciertos cursos por ejemplo). Un algoritmo consiste en generar todos los pareamientos y luego se marca uno que se tenga el mayor número de aristas. Pero este algoritmo presenta una complejidad de tipo exponencial. Los algoritmos de mayor eficiencia manejan una técnica llamada caminos aumentados que consiste en los caminos tengan una longitud impar se suprimen las aristas que estén en un vértice ya seleccionado y después se añaden las aristas que no estaban en el vértice dicho poniendo un grafo en donde las aristas están en solo uno de los dos subconjuntos (o exclusiva, C A). Teniendo en cuenta que existe un pareamiento maximal si y solo si, no existe un camino aumentado relativo al grafo pareado; su procedimiento es el siguiente: 1) Iniciar un conjunto C como vacío. 2) Encontrar un camino aumentado relativo a C y reemplazar C por C A. 3) Repetir el paso 2) hasta que ya no existan más caminos aumentados, en donde C es el pareamiento maximal. Para buscar el camino aumentado de debe empezar por un vértices que posea una arista sin parear hacia otro vértice, este se debe direccionar a una arista pareada y esta a su vez a un vértice con arista no pareada y así sucesivamente hasta encontrar un punto en donde no se pueda seguir este orden o hasta formar ciclos o circuitos en el camino. Ejemplo: Se tiene el siguiente grafo con un pareamiento

1

Figura 94. Ejemplo de un grafo para hallar el pareamiento maximal. Se inicia buscando el camino aumentado, iniciando con el vértice 2 y tomando su arista que conecta a 4 para cumplir que la primera arista no debe ser pareada.

Figura 95. Paso 1 del camino aumentado. El siguiente punto debe ser pareado luego se toma la arista {4, 1}

Figura 96. Paso 2 del camino aumentado. Luego se toma otra arista la cual se toma {1, 6} puesto que las demás forman circuitos, al tomar esta arista no pueden tener más aristas puesto que las demás forman ciclos o están pareadas; finalmente se obtiene el siguiente camino

Figura 97. Paso 3 del camino aumentado. Se procede a realizar C A, obteniendo el siguiente grafo

2

Figura 98. Grafo actual. Se vuelve a buscar el camino aumentado, iniciando con el vértice 3 y tomando su arista que conecta a 4 para cumplir que la primera arista no debe ser pareada

Figura 99. Paso 1 del camino aumentado. El siguiente punto debe ser pareado luego se toma la arista {4, 2}

Figura 100. Paso 2 del camino aumentado. Luego se toma otra arista la cual se toma {2, 5} puesto que las demás forman circuitos, al tomar esta arista no pueden tener más aristas puesto que las demás forman ciclos o están pareadas; finalmente se obtiene el siguiente camino

Figura 101. Paso 3 del camino aumentado. Se procede a realizar C A, obteniendo el siguiente grafo

Figura 102. Grafo actual. Nuevamente se busca el camino aumentado, iniciando con el vértice 1 y tomando su arista que conecta a 4 para cumplir que la primera arista no debe ser pareada

3

Figura 103. Paso 1 del camino aumentado. El siguiente punto debe ser pareado luego se toma la arista {4, 3}

Figura 104. Paso 2 del camino aumentado. Luego se toma otra arista la cual se toma {3, 6} puesto que las demás forman circuitos, al tomar esta arista no pueden tener más aristas puesto que las demás forman ciclos o están pareadas; finalmente se obtiene el siguiente camino

Figura 105. Paso 3 del camino aumentado. Se procede a realizar C A, obteniendo el siguiente grafo

Figura 106. Grafo actual. Nuevamente se busca el camino aumentado, iniciando con el vértice 3 y tomando su arista que conecta a 4 para cumplir que la primera arista no debe ser pareada

Figura 107. Paso 1 del camino aumentado. El siguiente punto debe ser pareado luego se toma la arista {4, 1}

Figura 108. Paso 2 del camino aumentado.

4

Luego se toma otra arista la cual se toma {1, 5} puesto que las demás forman circuitos, al tomar esta arista no pueden tener más aristas puesto que las demás forman ciclos o están pareadas; finalmente se obtiene el siguiente camino

Figura 109. Paso 3 del camino aumentado. Se procede a realizar C A, obteniendo el siguiente grafo

Figura 110. Grafo actual. Al buscar el camino aumentado se observa que ya no es posible por lo que se define que se ha encontrado el pareamiento maximal del grafo.

5

9. ENVOLVENTES 9.1. DEFINICIÓN Un conjunto C del plano afín es convexo si dados dos puntos cualesquiera p y q de c, del segmento que une p y q está contenido en C Segmento: [p,q] = (1-t)p+tq, tE[0,1]

Figura 111. Grafo convexo y no convexo La envolvente convexa de un conjunto de puntos p es el mejor conjunto convexo que contiene a dichos puntos (es decir, la intersección de todos los conjuntos convexos en los que p está contenido) La envolvente convexa de un conjunto de puntos P es el menor conjunto convexo que contiene a dichos puntos.

Figura 112. Envolvente convexa de un conjunto de puntos P

6

Un subconjunto A de puntos del plano se dice que es convexo si para cualesquiera dos puntos de A, el segmento que los une está contenido en A. Dado B, un subconjunto de puntos del plano. Se llama Cierre Convexo (también conocido como Envolvente Convexa o Convex Hull) al menor conjunto convexo del plano que contiene a B.

Figura 113. Cierre convexo De forma intuitiva sería como si en cada punto de B claváramos una púa y las rodeáramos por una cinta elástica estirada. Cuando la cinta se contrayera, ésta tomaría la forma del cierre convexo. Aunque usualmente se mencionan refiriéndose a la misma cosa, es interesante puntualizar la diferencia entre Cierre Convexo y Envolvente Convexa. Cuando hablamos de Cierre Convexo nos estamos refiriendo a una región cerrada que incluye todos los puntos del interior del conjunto, mientras que cuando hablamos de Envolvente Convexa hablamos de la frontera de esa región. Se denominan puntos extremos a los vértices de la envolvente convexa. 9.2. PLANTEAMIENTO DEL PROBLEMA El problema de calcular el cierre convexo se puede dividir en dos frentes:  

Dado un conjunto de puntos del plano, encontrar aquellos que sean vértices del cierre convexo. Dado un conjunto de puntos del plano, encontrar una descripción de la frontera del cierre, es decir, encontrar el polígono que forma la envolvente convexa.

En los algoritmos que se van a mostrar responderemos a dicho problema de un modo intermedio. Por un lado la salida serán los vértices del cierre convexo, pero por otro lado, dichos vértices estarán ordenados, de forma que sea sencillo construir el polígono. 9.3. APLICACIONES Y ALGORITMOS 9.3.1. Algoritmo 1 Entrada: P Salida: Q (Vértices ordenados) 7

Paso 1: Tomar todas las parejas de puntos de P Paso 2: Para cada pareja (Pi,Pj)  Si todos los demás puntos de P están en D(Pi,Pj) y no hay mas puntos de P en el segmento [Pi,Pj], SE ALMACENA (Pi,Pj)  En caso contrario se pasa a la pareja siguiente. Paso 3: Extraer ordenadamente los vértices  Si están todos alineados, escoger el de un extremo (orden lexicográfico) y partir de el parta hallar los demás.  En caso contrario empezar por uno cualquiera y hacer (q1,q2) (q2,q3) (q3,q4)… Extraer q1,q2,q3,q4… 9.3.2. Búsquedas de Aristas: Notas Previas: Toda recta divide al plano en dos semiplanos. Dado S un conjunto de puntos, y r una recta que pasa por uno de esos puntos, dicha recta se llama RECTA SOPORTE si deja al resto de puntos de S en uno de los semiplanos. Descripción del Algoritmo: Para cada pareja de puntos de S se comprueba si la recta que pasa por la arista que los une es soporte. En el caso de serlo, los puntos origen y final de dicha arista formarán parte del conjunto de vértices de la envolvente convexa (puntos extremos). Complejidad del algoritmo:  

Para identificar si una arista está contenida en una recta soporte: O(N^3) Para obtener los puntos extremos a partir de las aristas : O(N^3)

9.3.3. Eliminación De Los Puntos Interiores Notas Previas Un punto de un conjunto S de puntos es interior al cierre convexo si y sólo si es interior al triángulo cuyos vértices son puntos de S, y no es él mismo un vértice de dicho triángulo. Descripción Del Algoritmo Para cada tres puntos del conjunto S se descartan los que sean interiores al triángulo formado por ellos. Los puntos que quedan tras este proceso son vértices de la envolvente convexa. Para formar las aristas que constituyen la envolvente convexa basta con ordenarlos angularmente respecto a un punto interior a ellos (calculando la orientación del triángulo formado por ambos vértices y el punto interior alrededor del cual se está realizando la ordenación) 8

Complejidad Del Algoritmo  Formar los triángulos, comprobar y eliminar los puntos interiores: O(N^4)  Ordenar los puntos mediante divide y vencerás: O(N.LogN)

9.3.4. Algoritmo De Jarvis (Envoltura Del Regalo) Notas Previas La idea intuitiva del algoritmo consiste en imaginar una recta que se desplaza desde menos infinito hacia arriba hasta tocar un punto del conjunto de puntos. Luego, dicha recta va rodeando la nube de puntos en sentido positivo, girando en cada vértice hasta tocar el siguiente, de modo que al final la envuelve por completo. Descripción Del Algoritmo 1. Dado el conjunto de puntos S, tomamos el punto P que tenga menor ordenada y mayor abcisa. y trazamos una recta r que pase por P y sea paralela al eje de abcisas. 2. Para cada punto de S trazar lineas que los unan con P. El próximo vértice del cierre convexo será el punto Q que forme el mínimo ángulo respecto a la recta r anterior. 3. Si Q no es el punto de partida, Repetir 2 tomando P=Q y r como la recta formada por P y Q. Complejidad Del Algoritmo  

Encontrar el punto de menor ordenada: O(N) Encontrar el menor ángulo: O(N^2)

9.3.5. Algoritmo Quickhull Notas Previas Dado un conjunto S de puntos y una arista que forma parte del cierre convexo de dicho conjunto, el punto de S que forma un triángulo de área máxima con dicha arista es un punto extremo. Si dicha área no es única el punto será el que maximice el ángulo del triángulo. Descripción Del Algoritmo 1. Formar la arista extrema tomando dos puntos P y Q de menor abcisa 2. Encontrar el punto H de modo que el triángulo HPQ tenga área máxima. 3. Guardar H como vértice de la envolvente convexa. 4. Descartar los puntos dentro del triángulo HPQ 9

5. Si el segmento PH tiene puntos a su izquierda, repetir recursivamente desde 2 con PH y los puntos que caen en él o a su izquierda 6. Si el segmento HQ tiene puntos a su izquierda, repetir recursivamente desde 2 con HQ y los puntos que caen en él o a su izquierda. Complejidad Del Algoritmo  En el peor caso es de orden: O(N^2)  En el mejor caso, cuando los puntos están distribuidos uniformemente en el plano, es de orden: O(N.logN) 9.3.6. Algoritmo Incremental Descripción Del Algoritmo 1. Ordenar los N puntos de menor a mayor abcisa. Llamaremos p(n) al punto situado en la posición n Llamaremos P(n) al cierre convexo de los n primeros puntos 2. Definimos P(1) := p(1) 3. Para i desde 2 a N a) A partir de p(i-1) recorrer los vértices de P(i-1) en sentido positivo hasta encontrar uno de modo que la recta formada por él y p(i) dejen a la izquierda a todos los vértices de P(i1). Dicho vértice se llama vértice soporte superior. Unirlo con p(i) b) A partir de p(i-1) recorrer los vértices de P(i-1) en sentido negativo hasta encontrar uno de modo que la recta formada por él y p(i) dejen a la izquierda a todos los vértices de P(i-1). Dicho vértice se llama vértice soporte superior. Unirlo con p(i) c) Añadir p(i) al cierre y eliminar los vértices de P(i-1) desde el vértice soporte inferior hasta el superior Complejidad Del Algoritmo  

Ordenar los puntos: O(N.LogN) Realizar el Bucle: O(N)

9.3.7. ALGORITMO DE GRAHAM (SCAN DE GRAHAM) Notas Previas Este algoritmo surgió a finales de los 60, cuando en los laboratorios Bell se necesitaba calcular el cierre convexo de unos 10.000 puntos, y con uno de los algoritmos de por entonces, de O(N^2) resultaba demasiado lento. Entonces Graham lo solucionó con el presente algoritmo. Descripción Del Algoritmo

10

1. Hallar un punto q interior al cierre convexo 2. Ordenar los N puntos angularmente en sentido positivo alrededor de él. Llamaremos p(n) al punto situado en la posición n 3. (Scan) Recorrer la lista ordenada de puntos hasta que se llegue al punto de partida Examinar tripletas de puntos consecutivos [p(i-1),p(i),p(i+1)] a) Si la tripleta es un giro a la izquierda se avanza un vértice y se comprueba [p(i),p(i+1),p(i+2)] b) Si la tripleta no es un giro a la izquierda, entonces p(i) no es un vértice, ya que es interior a [q,p(i-1),p(i+1)]. c) I. Eliminar p(i) II. Comprobar la Tripleta [p(i-2),p(i-1),p(i+1)] 4. Los puntos que queden son los vértices de la envolvente convexa.

Complejidad Del Algoritmo    

Encontrar punto Interior: O(N) Ordenar los puntos alrededor del interior: O(N.logN) Encontrar el vértice donde iniciar el scan de Graham: O(N) Scan de Graham: O(N)

9.3.8. Algoritmo De Andrew Notas Previas Es una variación del Scan de Graham, donde cambia la forma de preordenar los puntos. Descripción Del Algoritmo 1. Determinar los puntos de mayor y menos abcisa en la nube de puntos y trazar una recta que pase por ellos. 2. Con los puntos que quedan por encima de la recta a) Ordenarlos de mayor a menor b) Aplicar el Scan de Graham a dichos puntos c) Se obtiene una linea poligonal (cierre superior) 3. Con los puntos que quedan por debajo de la recta a) Ordenarlos de menor a mayor b) Aplicar el Scan de Graham a dichos puntos c) Se obtiene una linea poligonal (cierre inferior)

11

4. Concatenar el cierre superior y el cierre inferior Complejidad Del Algoritmo    

Ordenar los puntos: O(N.LogN) Repartir los puntos encima y debajo de la recta: O(N) Aplicar Scan a ambos conjuntos de puntos: O(N) Concatenar los cierres: O(N)

9.3.9. Divide Y Vencerás Con Preordenación Notas Previas La idea de la técnica divide y vencerás es dividir un problema en subproblemas del mismo tipo y aproximadamente todos ellos del mismo tamaño, resolver los subproblemas recursivamente y, finalmente, combinar la solución de los subproblemas para dar una solución al problema original. La recursión finaliza cuando el problema es pequeño y la solución es fácil de construir directamente. Descripción Del Algoritmo Ordenar el conjunto de puntos S de menor a mayor abcisa. Cierre de S 1. Si sólo hay un punto, ese punto es el cierre Si no 2. 3. 4. 5.

Dividir S por la mitad obteniendo los conjuntos S1 y S2 Calcular el cierre de la mitad izquierda S1 obteniendo P1 Calcular el cierre de la mitad derecha S2 obteniendo P2 Mezclar los cierres P1 y P2 para obtener P, el cierre de S.

Esta Mezcla se realiza de la siguiente forma: a) Se une el vértice más a la derecha de P1 con el más a la izquierda de P2. Este segmento se va desplazando hacia abajo, recorriendo P1 en sentido positivo y P2 en sentido negativo alternativamente, hasta que todos los puntos de S queden por encima. Puente Inferior. b) Se une el vértice más a la derecha de P1 con el más a la izquierda de P2. Este segmento se va desplazando hacia arriba, recorriendo P1 en sentido negativo y P2 en sentido positivo alternativamente, hasta que todos los puntos de S queden por debajo. Puente Superior 9.3.10. Divide Y Vencerás Genérico 12

Notas Previas Este método es una variación del algoritmo Divide y Vencerás con Preordenación. Para su ejecución se necesitará conocer el concepto de Recta Soporte y el algoritmo Scan de Graham Descripción Del Algoritmo Sea S el conjunto de puntos, ordenados de forma arbitraria Cierre de S 1. Si hay un punto en S, entonces ese punto es el cierre convexo Si hay dos puntos en S, entonces el cierre convexo es el segmento que los une. Si hay tres puntos en S, entonces el cierre es el triángulo formado por ellos Si hay más de tres puntos 2. 3. 4. 5.

Dividir S en dos subconjuntos S1 y S2 según ese orden arbitrario Calcular el cierre de S1 obteniendo P1 Calcular el cierre de S2 obteniendo P2 Mezclar los cierres P1 y P2 para obtener P, el cierre de S.

Esta Mezcla se realiza de la siguiente forma: a) Obtener un punto p interno a P1 b) Si p es interno a P2: I. II.

Mezclar los vértices de P1 y P2 obteniendo P12 Aplicar Scan de Graham a P12 para obtener el cierre P

c) Si p es externo a P2: I. II. III. IV.

Hallar las rectas soporte de p respecto a P2 Los vértices entre las rectas se descartan El resto de vértices se mezclan con P2 obteniendo P12 Aplicar Scan de Graham a P12 para obtener el cierre P

9.3.11. Aproximación Inferior Notas Previas Este algoritmo da un método aproximado para calcular el cierre convexo de una nube de puntos. Se llama Aproximación inferior porque el cierre que nos dará es un subconjunto del cierre exacto, es decir, habrá puntos que caigan fuera del cierre aproximado. Descripción Del Algoritmo 13

1. Encontrar los puntos Xmin y Xmax con mayor y menor abcisa. 2. Dividir el espacio que hay entre Xmin y Xmax en K franjas verticales de igual anchura. 3. Para cada franja, incluyendo las franjas de los extremos escoger los puntos de mayor y menor ordenada (Hay K+2 franjas y 2k+4 puntos). 4. Aplicar un algoritmo conocido para calcular el cierre convexo de los puntos obtenidos. Se recomienda usar Andrew, ya que los puntos están casi ordenados por la abcisa, faltaría ordenar los dos puntos de cada franja. Nota: Se puede demostrar que la distancia máxima entre un punto fuera del cierre aproximado y dicho cierre es (Xmax-Xmin)/K. Luego a mayor valor de K mejor será la aproximación.

Figura 113. Aproximación inferior

Complejidad Del Algoritmo    

Búsqueda de Xmin y Xmax: O(N) Dividir el espacio en franjas y asignar los 2 puntos a cada una: O(N) Ordenar la muestra: O(K) Aplicar Andrew: O(K)

9.3.12. Aproximación Superior Notas Previas Este algoritmo da un método aproximado para calcular el cierre convexo de una nube de puntos. Se llama Aproximación superior porque el cierre que nos dará contiene al cierre exacto. Descripción Del Algoritmo 1. Encontrar los puntos Xmin y Xmax con mayor y menor abcisa. 2. Dividir el espacio que hay entre Xmin y Xmax en K franjas verticales de igual anchura. 3. Para cada franja, escoger los puntos de mayor y menor ordenada y proyectarlos sobre las líneas verticales que delimitan dicha franja. El par de proyecciones que se genera en cada caso serán los nuevos puntos a considerar (Hay como mucho 4K+4 puntos). 14

4. Aplicar un algoritmo conocido para calcular el cierre convexo de los puntos obtenidos. Se recomienda usar Andrew por estar los puntos ordenados. Nota: Se puede demostrar que la distancia máxima entre un punto del cierre aproximado y otro del cierre reales (Xmax-Xmin)/K. Luego a mayor valor de K mejor será la aproximación.

Figura 114. Aproximación superior Complejidad Del Algoritmo    

Búsqueda de Xmin y Xmax: O(N) Dividir el espacio en franjas y asignar los 2 puntos a cada una: O(N) Obtener los puntos mediante las proyecciones: O(K) Aplicar Andrew: O(K)

15

CONCLUSIONES De lo anterior se puede concluir que:        





   

Las operaciones entre grafos sirven en gran manera para poder crear nuevos grafos a partir de los elementos de los originales. Con estas operaciones problemas de diversos campos como la síntesis de circuitos secuenciales, contadores o sistemas de aperturas son utilizadas con el fin de resolverlas con las menores de las dificultades. Usando las operaciones podemos obtener caminos de sistema de autobuses cuando se tienen varias opciones para un destino. En la arquitectura de redes estas operaciones ayudaran para poder relacionar más de un sistema de redes con el fin de proveer la comunicación de la manera más eficaz en todos los nodos. Un árbol binario se define como un conjunto finito de elementos llamados nodos. Se puede usar terminología de relaciones familiares para descubrir las relaciones entre los nodos de un árbol Un árbol puede ser implementado fácilmente en una computadora. Lo que tiene que ver con los árboles: Entre las cosas que podemos mencionar se encuentra la raíz, los nodos de un árbol y la diferencia entre nodos sucesores y nodos terminales, como se muestran en el contenido del trabajo. Los arboles de expansión son demasiados útiles cuando se representa un costo para transportarse de un nodo en otro, ejemplo el sistema de redes eléctricos, donde para viajar de un punto a otro hay un costo de voltaje. Si el costo para viajar de un nodo a otro no es de energía sino de tiempo así como el sistema de redes de comunicación el tema de arboles de expansión es muy útil ya que uno desea que una maquina se conecte con otra en el menor tiempo posible. Los arboles de expansión son útiles cuando se trata de viajas de comercio, esto se debe para hallar la ruta optima para llegar al destino con facilidad. Un conjunto de corte de vértices U en un grafo G, es un conjunto de vértices de G, tal que G-U no es conexo o trivial. Similarmente, un conjunto de corte de aristas F es un conjunto de aristas tal que G-F no es conexo. Si los vértices de una componente conexa a un grafo se divide en dos subconjuntos, de manera que cada dos vértices en cada subconjunto estén conectados por un paseo que sólo atraviesa vértices en tal subconjunto, entonces el conjunto de aristas que una los vértices de los dos subconjuntos es un conjunto de corte.

16

       

Una arista de corte o puente, es una arista análoga a un vértice de corte; es decir, una que al eliminarla incrementa el número de componentes conexos del grafo. Un grafo es biconectado si entre cada par de vértices del grafo existen al menos dos caminos disjuntos en vértices. La coloración de grafos sirve para cuando a cada compilador o nodo se le quiere agregar una labor en particular, con este tema sería muy sencillo crear la asignación. La telefonía móvil utiliza la coloración de grafos en varios aspectos como por ejemplo en poder darle mayor soporte a ciertos nodos que son de una demanda más abundante que otros. Un conjunto C del plano afín es convexo si dados dos puntos cualesquiera p y q de c, del segmento que une p y q está contenido en C La envolvente convexa de un conjunto de puntos p es el mejor conjunto convexo que contiene a dichos puntos Un punto de un conjunto S de puntos es interior al cierre convexo si y sólo si es interior al triángulo cuyos vértices son puntos de S, y no es él mismo un vértice de dicho triángulo. La idea de la técnica divide y vencerás es dividir un problema en subproblemas del mismo tipo y aproximadamente todos ellos del mismo tamaño, resolver los subproblemas recursivamente y, finalmente, combinar la solución de los subproblemas para dar una solución al problema original.

17

BIBLIOGRAFÍA           

CAIRÓ, Osvaldo; GUARDATI, Silvia. Estructuras de datos. 3 ed. México D.F. Mc Graw Hill. AHO, J. ULLMAN, J. HOPCROFT, J. Estructuras de datos y algoritmos. Addison Wesley. GRIMALDI, Ralph P. Matemáticas discretas y combinatorias. 3 Ed. 1994, Addison Wesley. ROSEN, Kenneth H. Matemáticas discretas y sus aplicaciones. 5 Ed. 2004, Mc Graw Hill http://www.ual.es/~fbeltran/envolvente/ http://www.ma3.upc.edu/users/pelayo/research/producto%20fuerte.pdf http://dac.escet.urjc.es/rvmaster/rvmaster/asignaturas/mga/construcciones_ planas.pdf http://users.dcc.uchile.cl/~bebustos/apuntes/cc3001/Grafos/#4 http://www.franjafceia.com.ar/i/apuntes/34.pdf http://users.dcc.uchile.cl/~nbaloian/cc20a/post/redes3.html http://www.dma.fi.upm.es/grafos/3distcaminos.pdf

18