Modelos de Redes: Árbol de expansión mínima · ¾Un centro regional de cómputo (C.R.C.), debe...

Modelos de Redes: Modelos de Redes: ÁÁrbol rbol de expanside expansióón mn míínimanima

M. En C. Eduardo Bustos FarM. En C. Eduardo Bustos Farííasas

ObjetivosObjetivos

Conceptos y definiciones de redes.Conceptos y definiciones de redes.Importancia de los modelos de redesImportancia de los modelos de redesModelos de programaciModelos de programacióón lineal, representacin lineal, representacióón en n en redes y soluciones usando el computador para:redes y soluciones usando el computador para:* Modelos de asignaci* Modelos de asignacióónn* Modelo del vendedor viajero* Modelo del vendedor viajero* Modelos de la ruta mas corta* Modelos de la ruta mas corta* Modelos de la rama mas corta* Modelos de la rama mas corta

Y otros.Y otros.

Un problema de Un problema de redes redes es aquel que puede es aquel que puede representarse por:representarse por:

Funciones en los arcos

IntroducciIntroduccióónn

La importancia de los modelos de redes:La importancia de los modelos de redes:

* Muchos problemas comerciales pueden ser resueltos a trav* Muchos problemas comerciales pueden ser resueltos a travéés s de modelos redesde modelos redes

* El resultado de un problema de redes garantiza una soluci* El resultado de un problema de redes garantiza una solucióón n entera, dada su estructura matementera, dada su estructura matemáática. No se necesitan tica. No se necesitan restricciones adicionales para obtener este tipo de solucirestricciones adicionales para obtener este tipo de solucióón.n.

* Problemas de redes pueden ser resueltos por peque* Problemas de redes pueden ser resueltos por pequeñños os algoritmos , no importando el tamaalgoritmos , no importando el tamañño del problema, dada su o del problema, dada su estructura matemestructura matemáática.tica.

TerminologTerminologíía de Redesa de Redes

* Flujo: * Flujo: Corresponde a la cantidad que debe transportarse Corresponde a la cantidad que debe transportarse desde un nodo i a un nodo j a travdesde un nodo i a un nodo j a travéés de un arco que los s de un arco que los conecta. La siguiente notaciconecta. La siguiente notacióón es usada:n es usada:

XXijij= cantidad de flujo= cantidad de flujo

UUijij= cota m= cota míínima de flujo que se debe transportarnima de flujo que se debe transportar

LLijij= cota = cota maxmaxíímama de flujo que se puede transportar.de flujo que se puede transportar.

* * Arcos dirigidos /no dirigidos: Arcos dirigidos /no dirigidos: Cuando el flujo puede Cuando el flujo puede transportarse en una sola direccitransportarse en una sola direccióón se tiene un arco dirigido (la n se tiene un arco dirigido (la flecha indica la direcciflecha indica la direccióón). Si el flujo puede transportarse en n). Si el flujo puede transportarse en ambas direcciones existe un arco no dirigido (sin flecha).ambas direcciones existe un arco no dirigido (sin flecha).

* * Nodos adyacentes:Nodos adyacentes: Un nodo j es adyacente con un nodo i si Un nodo j es adyacente con un nodo i si existe un arco que une el nodo j con el nodo i.existe un arco que une el nodo j con el nodo i.

Rutas/ConexiRutas/Conexióón entre nodosn entre nodos

*Ruta: *Ruta: Una colecciUna coleccióón de arcos formados por una serie de n de arcos formados por una serie de nodos adyacentesnodos adyacentes* Los nodos est* Los nodos estáán conectados si existe una ruta entre ellos.n conectados si existe una ruta entre ellos.

Ciclos / Arboles /Arboles expandidosCiclos / Arboles /Arboles expandidos

* Ciclos :* Ciclos : Un ciclo se produce cuando al partir de un nodo por Un ciclo se produce cuando al partir de un nodo por un cierto camino se vuelve al mismo nodo por otra ruta.un cierto camino se vuelve al mismo nodo por otra ruta.* Arbol :* Arbol : Una serie de nodos que no contienen ciclos.Una serie de nodos que no contienen ciclos.*Arbol expandido: *Arbol expandido: Es un Es un áárbol que conecta todos lo nodos de rbol que conecta todos lo nodos de la red (contiene nla red (contiene n--1 arcos).1 arcos).

ÁÁrbol de expansirbol de expansióón mn míínimanima

Este problema surge cuando todos los nodos de una Este problema surge cuando todos los nodos de una red deben conectar entre ellos, sin formar un red deben conectar entre ellos, sin formar un looploop..

El El áárbol de expansirbol de expansióón mn míínima es apropiado para nima es apropiado para problemas en los cuales la redundancia es problemas en los cuales la redundancia es expansiva, o el flujo a lo largo de los arcos se expansiva, o el flujo a lo largo de los arcos se considera instantconsidera instantááneo.neo.

ÁÁrbol de expansirbol de expansióón mn míínimanima

Este problema se refiere a utilizar las ramas o arcos de Este problema se refiere a utilizar las ramas o arcos de la red para llegar a todos los nodos de la red, de manera la red para llegar a todos los nodos de la red, de manera tal que se minimiza la longitud total.tal que se minimiza la longitud total.La aplicaciLa aplicacióón de estos problemas de optimizacin de estos problemas de optimizacióón se n se ubica en las redes de comunicaciubica en las redes de comunicacióón eln elééctrica, telefctrica, telefóónica, nica, carretera, ferroviaria, acarretera, ferroviaria, aéérea, marrea, maríítima, etc.; donde los tima, etc.; donde los nodos representan puntos de consumo elnodos representan puntos de consumo elééctrico, ctrico, teltelééfonos, aeropuertos, computadoras.fonos, aeropuertos, computadoras.Y los arcos podrY los arcos podríían ser de alta tensian ser de alta tensióón, cable de fibra n, cable de fibra óóptica, rutas aptica, rutas aééreas, etc.reas, etc.Si n = numero de nodos, entonces la soluciSi n = numero de nodos, entonces la solucióón n óóptima ptima debe incluir ndebe incluir n--1 arcos.1 arcos.

Algoritmo de Algoritmo de KruskalKruskal

Algoritmo de Algoritmo de KruskalKruskal1.1. Comenzar en forma arbitraria en cualquier Comenzar en forma arbitraria en cualquier

nodo y conectarlo con el mas prnodo y conectarlo con el mas próóximo (menos ximo (menos distante o costoso).distante o costoso).

2.2. Identificar el nodo no conectado que esta mIdentificar el nodo no conectado que esta máás s cera o menos costoso de alguno de los nodos cera o menos costoso de alguno de los nodos conectados. Deshacer los empates de forma conectados. Deshacer los empates de forma arbitraria. Agregar este nodo al conjunto de arbitraria. Agregar este nodo al conjunto de nodos conectado.nodos conectado.

3.3. Repartir este aso hasta que se hayan Repartir este aso hasta que se hayan conectado todos los nodos.conectado todos los nodos.

EJEMPLO 1EJEMPLO 1EL TRANSITO DEL DISTRITO EL TRANSITO DEL DISTRITO

METROPOLITANOMETROPOLITANOÁÁrbol de expansirbol de expansióón mn míínimanima

EL TRANSITO DEL DISTRITO EL TRANSITO DEL DISTRITO METROPOLITANOMETROPOLITANOLa ciudad de Vancouver esta planificando el La ciudad de Vancouver esta planificando el desarrollo de una nueva ldesarrollo de una nueva líínea en sistemas de nea en sistemas de trtráánsito.nsito.El sistema debe unir 8 residencias y centros El sistema debe unir 8 residencias y centros comerciales.comerciales.El distrito metropolitano de transito necesita El distrito metropolitano de transito necesita seleccionar un conjunto de lseleccionar un conjunto de lííneas que conecten neas que conecten todos los centros a un mtodos los centros a un míínimo costo.nimo costo.La red seleccionada debe permitir:La red seleccionada debe permitir:

-- Factibilidad de las lFactibilidad de las lííneas que deban ser neas que deban ser construconstruíídasdas..-- MMíínimo costo posible por lnimo costo posible por líínea.nea.

Zona Oeste

Zona Norte Universidad

DistritoComercial

Zona EsteShoppingCenter

Zona Sur

Zona Centro

RED QUE REPRESENTAEL ARBOL EXPANDIDO.

SoluciSolucióón n -- AnalogAnalogíía con un problema de redesa con un problema de redes-- El algoritmo que resuelve este problema es un procedimiento El algoritmo que resuelve este problema es un procedimiento muy fmuy fáácil (cil (““trivialtrivial””).).-- Corresponde a una categorCorresponde a una categoríía de algoritmos a de algoritmos “á“ávidosvidos””..-- Algoritmo:Algoritmo:

* Comience seleccionando el arco de menor longitud.* Comience seleccionando el arco de menor longitud.* En cada iteraci* En cada iteracióón, agregue el siguiente arco de menor n, agregue el siguiente arco de menor

longitud longitud del conjunto de arcos disponibles , tomando la del conjunto de arcos disponibles , tomando la precauciprecaucióón de no formar ningn de no formar ningúún n looploop..* El algoritmo finaliza cuando todos los nodos est* El algoritmo finaliza cuando todos los nodos estáán n conectados.conectados.

SoluciSolucióón mediante el computadorn mediante el computador

-- Los entrada consiste en el nLos entrada consiste en el núúmero de nodos, el largo de los mero de nodos, el largo de los arcos y la descripciarcos y la descripcióón de la red.n de la red.

Solución óptima mediante WINQSB

ShoppingCenter

Zona Oeste

Zona Norte

Universidad

DistritoComercial

Zona Este

Zona Sur

ZonaCentror

Costo Total = $236 millones

RED QU EREPRESENTA LASOLUCIÓN ÓPTIMA

EJEMPLO 2EJEMPLO 2RED DE COMUNICACIONESRED DE COMUNICACIONES

ÀÀRBOL DE EXPANSIRBOL DE EXPANSIÓÓN MN MÍÍNIMANIMA

Ejemplo 1Ejemplo 1

Se va a instalar una red de comunicaciSe va a instalar una red de comunicacióón n entre 12 ciudades. entre 12 ciudades. Los costos de los posibles enlaces Los costos de los posibles enlaces directos entre pares permisibles es el que directos entre pares permisibles es el que se muestra en la figura. se muestra en la figura. Cada unidad de costo representa $10,000 Cada unidad de costo representa $10,000 ddóólares.lares.

SOLUCISOLUCIÓÓN CON N CON WINQSBWINQSB

SoluciSolucióónnInteracción Nodo Con nodo Costo ($)1 1 5 12 1 2 43 2 6 34 6 7 55 7 8 26 8 4 17 7 11 28 11 12 19 11 10 310 10 9 511 2 3 6

SUMA $33

MMéétodo Tabulartodo Tabular1 2 3 4 5 6 7 8 9 10 11 12

1 4 12 4 6 33 6 6 74 6 15 1 4 96 3 4 5 77 7 5 2 28 1 2 29 9 510 7 5 311 2 3 112 2 1

EJEMPLO 3EJEMPLO 3winqsbwinqsb

Solucione el siguiente Solucione el siguiente áárbol de extensirbol de extensióón mn míínima para nima para la red de comunicaciones de emergencia usando el la red de comunicaciones de emergencia usando el mméétodo tabular. Las unidades son distancias en todo tabular. Las unidades son distancias en kmskms..

SOLUCISOLUCIÓÓNN

USANDO EL WINQSBUSANDO EL WINQSB

ITERACIITERACIÓÓNN DEL NODODEL NODO AL NODOAL NODO DISTANCIADISTANCIA11 11 1212 121222 1212 1515 131333 1515 1414 121244 1414 1313 4455 1313 1010 5566 1414 77 9977 77 88 1188 1010 99 101099 1414 1111 10101010 1111 66 881111 99 44 12121212 44 33 991313 33 22 11111414 44 55 1313

SUMASUMA 129129

EJEMPLO 4EJEMPLO 4CENTRO REGIONAL DE CENTRO REGIONAL DE

CCÓÓMPUTOMPUTOÁÁrbol de expansirbol de expansióón mn míínimanima

Un centro regional de cUn centro regional de cóómputo (mputo (C.R.CC.R.C.), debe .), debe instalar linstalar lííneas especiales para comunicacineas especiales para comunicacióón, a n, a fin de conectar a cinco usuarios satfin de conectar a cinco usuarios satéélite con una lite con una nueva computadora central, la companueva computadora central, la compañíñía a teleftelefóónica local es la que instalarnica local es la que instalaráá la nueva red la nueva red de comunicaciones, pero es una operacide comunicaciones, pero es una operacióón n costosa. costosa. Con el propCon el propóósito de reducir costos, se busca sito de reducir costos, se busca que la longitud total (que la longitud total (KmsKms.) de estas l.) de estas lííneas sea neas sea la menor posible. la menor posible. La red para este problema es la siguiente:La red para este problema es la siguiente:

SOLUCISOLUCIÓÓNN

Desarrollo del algoritmo:Desarrollo del algoritmo:·· UbicarseUbicarse en el nodo 3 (puede ser en en el nodo 3 (puede ser en

cualquier otro nodo) y se encuentra que el cualquier otro nodo) y se encuentra que el nodo mnodo máás prs próóximo es el 4 (10 ximo es el 4 (10 KmsKms.).)

·· ElEl siguiente nodo msiguiente nodo máás cercano al 3 o 4 es s cercano al 3 o 4 es el nodo 6 (20 el nodo 6 (20 KmsKms).).

·· RepitiendoRepitiendo el paso anterior tenemos el el paso anterior tenemos el siguiente siguiente áárbol de extensirbol de extensióón mn míínima:nima:

Con una extensión de 110 Kms.

Interacción Nodos Distancia (Km.)

1 3-4 102 4-6 203 3-5 304 4-1 305 1-2 20

110 Km.

1 2 3 4 5 6

1 20 40 30 50 40

2 20 40

3 40 10 30

4 30 10 20

5 50 40 30 40

6 40 20 40

MMÉÉTODO TABULARTODO TABULAR

PROBLEMA PARA PROBLEMA PARA RESOLVERRESOLVER

CAMINOS EN EL PARQUECAMINOS EN EL PARQUE

RUTA MRUTA MÁÁS CORTAS CORTA

SOLUCISOLUCIÓÓNN

EJERCICIO PARA EJERCICIO PARA RESOLVERRESOLVER

La cLa cíía. MCC acaba de obtener la aprobacia. MCC acaba de obtener la aprobacióón n para ofrecer el servicio de televisipara ofrecer el servicio de televisióón por cable n por cable en una zona metropolitana. en una zona metropolitana. Los nodos de la red que aparece en seguida Los nodos de la red que aparece en seguida representan los puntos de distribucirepresentan los puntos de distribucióón a los que n a los que deben llegar las ldeben llegar las lííneas primarias del cable. neas primarias del cable. Los arcos de la red muestran el nLos arcos de la red muestran el núúmero de mero de millas que existen entre los puntos de millas que existen entre los puntos de distribucidistribucióón.n.Determine la soluciDetermine la solucióón que permitirn que permitiráá a la a la compacompañíñía llegar a todos los puntos de a llegar a todos los puntos de distribucidistribucióón con una longitud mn con una longitud míínima de la lnima de la líínea nea del cable primario.del cable primario.

SOLUCISOLUCIÓÓNN

1.1. TV Cable VisiTV Cable Visióón desea establecer una red de n desea establecer una red de comunicacicomunicacióón para brindar el servicio de cable que n para brindar el servicio de cable que permita enlazar las 14 ciudades de la Reppermita enlazar las 14 ciudades de la Repúública blica Mexicana.Mexicana.

Determinar cDeterminar cóómo se conectarmo se conectaríían dichos 14 ciudades de an dichos 14 ciudades de forma que la longitud de cable a utilizarse sea mforma que la longitud de cable a utilizarse sea míínima.nima.

El nodo 1 constituye la estaciEl nodo 1 constituye la estacióón de reparto.n de reparto.Los nLos núúmeros expresados en cada rama expresan las meros expresados en cada rama expresan las

distancias entre las ciudades.distancias entre las ciudades.A travA travéés de la aplicacis de la aplicacióón de este algoritmo, podemos n de este algoritmo, podemos

calcular la cantidad mcalcular la cantidad míínima de cable a ser utilizadas en nima de cable a ser utilizadas en la red de comunicacila red de comunicacióón por cable (expresado en metros)n por cable (expresado en metros)

SOLUCISOLUCIÓÓNN

Usando TORAUsando TORA

11°° A = {1}A = {1} B = {2,3,4,5,6,7,8,9,10,11,12,13,14,15}B = {2,3,4,5,6,7,8,9,10,11,12,13,14,15}MinMin = {(1,2)(1,3)(1,4)} = (1,2) = 4000= {(1,2)(1,3)(1,4)} = (1,2) = 4000

22°° A = {1,2}A = {1,2} B = {3,4,5,6,7,8,9,10,11,12,13,14,15}B = {3,4,5,6,7,8,9,10,11,12,13,14,15}MinMin = {(1,3)(1,4)(2,3)(2,5)(2,6)} = (2,3) = 200= {(1,3)(1,4)(2,3)(2,5)(2,6)} = (2,3) = 200

33°° A = {1,2,3}A = {1,2,3} B = {4,5,6,7,8,9,10,11,12,13,14,15}B = {4,5,6,7,8,9,10,11,12,13,14,15}MinMin = {(1,4)(2,5)(2,6)(3,4)(3,5)} = (3,4) = 200= {(1,4)(2,5)(2,6)(3,4)(3,5)} = (3,4) = 200

44°° A = {1,2,3,4}A = {1,2,3,4} B = {5,6,7,8,9,10,11,12,13,14,15}B = {5,6,7,8,9,10,11,12,13,14,15}MinMin = {(2,5)(2,6)(3,5)(4,5)(4,9)} = (4,5) = 250= {(2,5)(2,6)(3,5)(4,5)(4,9)} = (4,5) = 250

55°° A = {1,2,3,4,5}A = {1,2,3,4,5} B = {6,7,8,9,10,11,12,13,14,15}B = {6,7,8,9,10,11,12,13,14,15}MinMin = {(2,6)(4,9)(5,6)(5,7)(5,9)} = (5,6) = 200= {(2,6)(4,9)(5,6)(5,7)(5,9)} = (5,6) = 200

66°° A = {1,2,3,4,5,6}A = {1,2,3,4,5,6} B = {7,8,9,10,11,12,13,14,15}B = {7,8,9,10,11,12,13,14,15}MinMin = {(4,9)(5,7)(5,9)(6,7)(6,8)(6,12)} = (6,7) = 200= {(4,9)(5,7)(5,9)(6,7)(6,8)(6,12)} = (6,7) = 200

77°° A = {1,2,3,4,5,6,7}A = {1,2,3,4,5,6,7} B = {8,9,10,11,12,13,14,15}B = {8,9,10,11,12,13,14,15}MinMin = {(4,9)(5,9)(6,8)(6,12)(7,8)(7,9)} = (7,8) = 150= {(4,9)(5,9)(6,8)(6,12)(7,8)(7,9)} = (7,8) = 150

88°° A = {1,2,3,4,5,6,7,8}A = {1,2,3,4,5,6,7,8} B = {9,10,11,12,13,14,15}B = {9,10,11,12,13,14,15}MinMin = {(4,9)(5,9)(6,12)(7,9)(8,9)(8,11)(8,12)} = (8,9) = 200= {(4,9)(5,9)(6,12)(7,9)(8,9)(8,11)(8,12)} = (8,9) = 200

99°° A = {1,2,3,4,5,6,7,8,9}A = {1,2,3,4,5,6,7,8,9} B = {10,11,12,13,14,15}B = {10,11,12,13,14,15}MinMin = {(6,12)(8,11)(8,12)(9,10)} = (9,10) = 250= {(6,12)(8,11)(8,12)(9,10)} = (9,10) = 250

1010°° A = {1,2,3,4,5,6,7,8,9,10}A = {1,2,3,4,5,6,7,8,9,10} B = {11,12,13,14,15}B = {11,12,13,14,15}MinMin = {(6,12)(8,11)(8,12)(10,11)(10,15)} = (10,11) = 180= {(6,12)(8,11)(8,12)(10,11)(10,15)} = (10,11) = 180

1111°° A = {1,2,3,4,5,6,7,8,9,10,11}A = {1,2,3,4,5,6,7,8,9,10,11} B = {12,13,14,15}B = {12,13,14,15}MinMin = {(6,12)(8,12)(10,15)(11,13)(11,14)(11,15)} = (11,13) = 350= {(6,12)(8,12)(10,15)(11,13)(11,14)(11,15)} = (11,13) = 350

1212°° A = {1,2,3,4,5,6,7,8,9,10,11,13}A = {1,2,3,4,5,6,7,8,9,10,11,13} B = {12,14,15}B = {12,14,15}MinMin = {(6,12)(8,12)(10,15)(11,13)(11,14)(11,15)(13,14)} = (13,14) == {(6,12)(8,12)(10,15)(11,13)(11,14)(11,15)(13,14)} = (13,14) = 120120

1313°° A = {1,2,3,4,5,6,7,8,9,10,11,13,14}A = {1,2,3,4,5,6,7,8,9,10,11,13,14} B = {15}B = {15}MinMin = {(6,12)(8,12)(10,15)(11,15)(14,15)} = (14,15) = 120= {(6,12)(8,12)(10,15)(11,15)(14,15)} = (14,15) = 120

Una compaUna compañíñía desea anunciar su producto a las a desea anunciar su producto a las 12 principales estaciones de radio locales. 12 principales estaciones de radio locales. La red de comunicaciones por cable que enlaza La red de comunicaciones por cable que enlaza a las estaciones de radio se indica en la figura. a las estaciones de radio se indica en la figura. Determine como se conecta las 12 estaciones Determine como se conecta las 12 estaciones de radio de modo que se minimice la longitud de radio de modo que se minimice la longitud total del cable que se utiliztotal del cable que se utilizóó ((KmsKms).).

SOLUCISOLUCIÓÓNN

SOLUCION EN EL TORA :SOLUCION EN EL TORA :ARBOL1ARBOL1------------------------------------------------------------------------------------------------------------------*** MINIMAL SPANNING TREE SOLUTION ****** MINIMAL SPANNING TREE SOLUTION ***

Minimal spanning tree length = 28.0000Minimal spanning tree length = 28.0000

From To Arc LengthN1 N2 3.00N2 N4 1.00N4 N6 4.00N6 N10 1.00N6 N5 2.00N10 N12 3.00N4 N8 4.00N8 N11 1.00N10 N9 4.00N9 N7 3.00N7 N3 2.00

ÁÁRBOL DE EXPANSIRBOL DE EXPANSIÓÓN MN MÍÍNIMANIMA

Una empresa de paqueterUna empresa de paqueteríía ha iniciado a ha iniciado sus labores, repartiendo paquetes por sus labores, repartiendo paquetes por toda la ciudad, pero tiene clientes toda la ciudad, pero tiene clientes principales, los cuales necesitan sus principales, los cuales necesitan sus paquetes lo mpaquetes lo máás pronto posible. s pronto posible. La empresa necesita saber cual es el La empresa necesita saber cual es el camino mcamino máás rs ráápido para que sus enviados pido para que sus enviados lleguen a su destino para hacer la entrega lleguen a su destino para hacer la entrega a tiempo. a tiempo.

Distancia en Kms.

SOLUCISOLUCIÓÓNN

Paso 0:Paso 0:A = 0A = 0B = {1,2,3,4,5,6,7,8,9,10,11,12,13}B = {1,2,3,4,5,6,7,8,9,10,11,12,13}Paso 1:Paso 1:A = {1}A = {1}B = {2,3,4,5,6,7,8,9,10,11,12,13}B = {2,3,4,5,6,7,8,9,10,11,12,13}MinMin = {(= {(1,21,2)(1,3)(1,5)} = 1)(1,3)(1,5)} = 1 Nodo = 2Nodo = 2

Paso 2:Paso 2:A = {1,2}A = {1,2}B = {3,4,5,6,7,8,9,10,11,12,13}B = {3,4,5,6,7,8,9,10,11,12,13}MinMin = {(1,3)(1,5)(2,4)(= {(1,3)(1,5)(2,4)(2,52,5)}= 2 )}= 2 Nodo = 5Nodo = 5

Paso 3:Paso 3:A = {1,2,5}A = {1,2,5}B = {3,4,6,7,8,9,10,11,12,13}B = {3,4,6,7,8,9,10,11,12,13}MinMin = {(1,3)(1,5)(= {(1,3)(1,5)(2,42,4)(5,7)(5,8)}= 3)(5,7)(5,8)}= 3 Nodo = 4Nodo = 4

Paso 4:Paso 4:A = {1,2,4,5}A = {1,2,4,5}B = {3,6,7,8,9,10,11,12,13}B = {3,6,7,8,9,10,11,12,13}MinMin = {(1,3)(1,5)(5,7)(5,8)(= {(1,3)(1,5)(5,7)(5,8)(4,34,3)(4,7)}= 2 )(4,7)}= 2 Nodo = 3Nodo = 3

Paso 5:Paso 5:A = {1,2,3,4,5}A = {1,2,3,4,5}B = {6,7,8,9,10,11,12,13}B = {6,7,8,9,10,11,12,13}MinMin = {(1,3)(1,5)(5,7)(5,8)(4,7)(= {(1,3)(1,5)(5,7)(5,8)(4,7)(3,63,6)(3,7)}= 1)(3,7)}= 1 Nodo = 6Nodo = 6

Paso 6:Paso 6:A = {1,2,3,4,5,6}A = {1,2,3,4,5,6}B = {7,8,9,10,11,12,13}B = {7,8,9,10,11,12,13}MinMin = {(1,3)(1,5)(5,7)(5,8)(4,7)(3,7)(6,9)(= {(1,3)(1,5)(5,7)(5,8)(4,7)(3,7)(6,9)(6,116,11)}= 1)}= 1 Nodo = 11Nodo = 11

Paso 7:Paso 7:A = {1,2,3,4,5,6,11}A = {1,2,3,4,5,6,11}B = {7,8,9,10,12,13}B = {7,8,9,10,12,13}MinMin = {(1,3)(1,5)(5,7)(5,8)(4,7)(3,7)(6,9)(11,12)(= {(1,3)(1,5)(5,7)(5,8)(4,7)(3,7)(6,9)(11,12)(11,1311,13)}= 1)}= 1 Nodo = 13Nodo = 13

Paso 8:Paso 8:A = {1,2,3,4,5,6,11,13}A = {1,2,3,4,5,6,11,13}B = {7,8,9,10,12}B = {7,8,9,10,12}MinMin = {(1,3)(1,5)(5,7)(5,8)(4,7)(3,7)(= {(1,3)(1,5)(5,7)(5,8)(4,7)(3,7)(6,96,9)(11,12)(13,12)}= 2)(11,12)(13,12)}= 2 Nodo = 9Nodo = 9

Paso 9:Paso 9:A = {1,2,3,4,5,6,9,11,13}A = {1,2,3,4,5,6,9,11,13}B = {7,8,10,12}B = {7,8,10,12}MinMin = {(1,3)(1,5)(5,7)(5,8)(4,7)(3,7)(6,9)(9,10)(9,13)(11,12)(= {(1,3)(1,5)(5,7)(5,8)(4,7)(3,7)(6,9)(9,10)(9,13)(11,12)(13,1213,12)}= 2)}= 2 Nodo = 12Nodo = 12

Paso 10:Paso 10:A = {1,2,3,4,5,6,9,11,12,13}A = {1,2,3,4,5,6,9,11,12,13}B = {7,8,9,10}B = {7,8,9,10}MinMin = {(1,3)(1,5)(5,7)(5,8)(4,7)(3,7)(6,9)(= {(1,3)(1,5)(5,7)(5,8)(4,7)(3,7)(6,9)(9,109,10)(9,13)(11,12)}= 3)(9,13)(11,12)}= 3 Nodo = 10Nodo = 10

Paso 11:Paso 11:A = {1,2,3,4,5,6,9,10,11,12,13}A = {1,2,3,4,5,6,9,10,11,12,13}B = {7,8,9}B = {7,8,9}MinMin = {(1,3)(1,5)(5,7)(5,8)(4,7)(3,7)(6,9)(9,13)(11,12)(= {(1,3)(1,5)(5,7)(5,8)(4,7)(3,7)(6,9)(9,13)(11,12)(10,710,7)(10,8)}= 2 )(10,8)}= 2

Nodo = 7Nodo = 7

Paso 12:Paso 12:A = {1,2,3,4,5,6,7,9,10,11,12,13}A = {1,2,3,4,5,6,7,9,10,11,12,13}B = {8,9}B = {8,9}MinMin = {(1,3)(1,5)(5,7)(5,8)(4,7)(3,7)(6,9)(9,13)(11,12)(10,8)(= {(1,3)(1,5)(5,7)(5,8)(4,7)(3,7)(6,9)(9,13)(11,12)(10,8)(7,87,8)}= 3)}= 3

Nodo = 8Nodo = 8

Resultado final: Resultado final: 1 + 2 + 3 + 2 + 1 + 2 + 1 + 3 + 2 + 3 + 1 + 2 = 231 + 2 + 3 + 2 + 1 + 2 + 1 + 3 + 2 + 3 + 1 + 2 = 23

100100

101101

102102

Desarrolle la soluciDesarrolle la solucióón del n del áárbol de extensirbol de extensióón n mmíínima (nima (KmsKms.) para la siguiente red de .) para la siguiente red de

comunicaciones de emergencia:comunicaciones de emergencia:

103103

ANEXO ALGORITMO ANEXO ALGORITMO DE KRUSKAL DE KRUSKAL

GRAFOSGRAFOS

104104

Algoritmo de Algoritmo de KruskalKruskalDado un grafo ponderado G=(V, A), el algoritmo parte de un grafoDado un grafo ponderado G=(V, A), el algoritmo parte de un grafoGG’’= (V, = (V, ØØ). Cada nodo es una componente conexa en s). Cada nodo es una componente conexa en síí misma.misma.En cada paso de ejecuciEn cada paso de ejecucióón se elige la arista de menor costo de A.n se elige la arista de menor costo de A.

Si une dos nodos que pertenecen a distintas componentes conexas Si une dos nodos que pertenecen a distintas componentes conexas entonces se aentonces se aññade al ade al áárbol de expansirbol de expansióón Gn G’’..En otro caso no se coge, ya que formarEn otro caso no se coge, ya que formaríía un ciclo en Ga un ciclo en G’’..

Acabar cuando GAcabar cuando G’’ sea conexo: cuando tengamos nsea conexo: cuando tengamos n--1 aristas.1 aristas.Estructura del algoritmo de Estructura del algoritmo de KruskalKruskal

Sea T de tipo Conjunto de aristas, el lugar donde se guardarSea T de tipo Conjunto de aristas, el lugar donde se guardaráán las aristas del n las aristas del áárbol de expansirbol de expansióón. Asignar T a n. Asignar T a ØØ..Mientras T contenga menos de nMientras T contenga menos de n--1 aristas hacer:1 aristas hacer:

Elegir la arista (v, w) de A con menor costo.Elegir la arista (v, w) de A con menor costo.Borrar (v, w) de A (para no volver a cogerla).Borrar (v, w) de A (para no volver a cogerla).Si v, w estSi v, w estáán en distintos componentes conexos entonces an en distintos componentes conexos entonces aññadir (v, w) a adir (v, w) a T. En otro caso, descartar (v, w).T. En otro caso, descartar (v, w).

105105

ÁÁrboles de expansirboles de expansióón.n.Algoritmo de Algoritmo de KruskalKruskal

Ejemplo.Ejemplo. Mostrar la ejecuciMostrar la ejecucióón del algoritmo de n del algoritmo de KruskalKruskal..

Necesidades del algoritmo:Necesidades del algoritmo:Las aristas deben ser ordenadas, segLas aristas deben ser ordenadas, segúún el costo.n el costo.Necesitamos operaciones para saber si dos nodos estNecesitamos operaciones para saber si dos nodos estáán en la misma n en la misma componente conexa y para unir componentes.componente conexa y para unir componentes.

RelaciRelacióón dos nodos pertenecen a una componente conexa: es una n dos nodos pertenecen a una componente conexa: es una relacirelacióón binaria de equivalencia n binaria de equivalencia ⇒⇒ podemos usar la estructura de podemos usar la estructura de representacirepresentacióón para relaciones de equivalencia (con operaciones Inicia, n para relaciones de equivalencia (con operaciones Inicia, Encuentra y UniEncuentra y Unióón).n).

Modelos de Redes: Árbol de expansión mínima · ¾Un centro regional de cómputo (C.R.C.), debe...

Documents

Revista cómputo

Presentación Conectar

Equipos de Cómputo

Cómputo movil

Conectar Flex

Sistemas y Cómputo

Sensibilización Conectar Igualdad

Conectar La Rioja

Auditoría de Gestión Programa Conectar Igualdadeducaciondigital.neuquen.gov.ar/wp-content/uploads/...Conectar-Igua… · 1 . Auditoría de Gestión Programa Conectar Igualdad Ejercicios

Trabajo de cómputo

CÓMPUTO II - cunori.edu.gt

Conectar proyector

Conectar 3.0

Taller de Cómputo

Proyecto de cómputo

Conectar netbook

Sistemas de Cómputo

Conectar igualdad

Informe de Cómputo

#ConectAR - emexi.cancilleria.gob.ar