telecomunicaciones

1.

MODELO DE REDES
•
•

INTRODUCCION
TERMINOLOGÍA

2. ÁRBOL DE EXPANSIÓN MÍNIMA
•
•

BASE TEORICA
ALGORITMO DE KRUSKAL

3. RUTA MAS CORTA
•
•

BASE TEORICA
ALGORITMO DE DIJKSTRA

4. FLUJO MÁXIMO
•
•

BASE TEORICA
ALGORITMO DE FULKERSON

1.

LA IMPORTANCIA DE LOS MODELOS DE REDES
1.
2.

3.

Muchos problemas comerciales pueden ser resueltos por modelo
deredes.
El resultado de un problema de redes garantiza una solución
entera, dada su estructura matemática. No se necesitan
restricciones adicionales para obtener este tipo de solución.
Problema de redes puedes ser resueltos por pequeños algoritmos,
no importando el tamaño del problema, dada su estructura
matemática

ARCOS
1- FLUJO: Corresponde a la cantidad
que debe transportarse de unnodo i
a un nodo j a través de un arco que
los conecta. La siguiente notación
es usada:
• Xij=cantidad de flujo
• Uij=cota mínima de flujo que se
debe transportar
• Lij=cota máxima de flujo que se
puede transportar
2.- ARCOS DIRIGIDOS/NO
DIRIGIDOS:
Cuando el flujo puede transportarse
en una sola dirección se tiene un
arco dirigido. Si el flujo puede
transportarse en ambas direccionesse tiene un arco no dirigido.

NODOS

TRAYECTORIA

RUTAS CONEXIÓN ENTRE NODOS:
•Ruta: Una colección de arcos formados por
una serie de nodos adyacentes. Los nodos
están conectados si existe una ruta entre ellos.
CICLOS/ARBOLES/ARBOLES EXPANDIDOS
•Ciclos: Se produce cuando al partir de un
nodo por un cierto camino se vuelve al mismo
nodo por cierta ruta.
•Árbol: Una serie de nodos queno tienen
ciclos.
•Arboles Expandidos: Es un árbol que
conecta todos los nodos de la red (contiene n-1
arcos)

Joseph Kruskal

ALGORITMO DE EXPANSIÓN
MÍNINA
• Este problema surge cuando todos los nodos de una red deben
conectar entre ellos, sin formar un loop.
• El árbol de expansión mínima es apropiado para problemas en
los cuales la redundancia es expansiva, o el flujo a lolargo de
los arcos se considera instantáneo.

Una Empresa textil desea hacer un viaje en avión todo
Sudamérica, con el propósito de instalar algunas cedes
en cada país. Para esto debemos desarrollar un
algoritmo que nos permita verificar cual será el camino
correcto hacia cada país, para realizar menos tiempo al
exportar los materiales textiles la distancia (en km2).

22000
A. ColombiaA.Venezuela

A.Brasil
90000

70000

55000

14000
20000

A. Ecuador

A. Bolivia

15000

30000

12000

40000

13000
90000

A.Peú

62000

A.Chie

17000

A. Argentina

80000

10000

A.
Paraguay

se toma a Perú como partida
C1= Ф + {Perú}
ĉ1= {ecuador, Colombia, argentina, Venezuela,
chile, Paraguay Bolivia, Brasil}

22000
Colombia

VenezuelaBrasil
90000

70000

55000

14000
20000

Ecuador

Bolivia

15000

Paraguay
30000

12000

40000

13000
90000

Perú

Argentina

80000

10000

62000

Chile

17000

Ahora buscamos quien esta más cercano a Perú , como chile es el más
cercano a Perú , tomamos a chile
C2= {Perú} + {chile}
C2= {Perú, chile}
ĉ2= {ecuador, Colombia, argentina, Venezuela,Paraguay, Bolivia, Brasil}

22000
Colombia

Venezuela

Brasil
90000

70000

55000

14000
20000

Ecuador

Bolivia

15000

Paraguay
30000

12000

40000

13000

90000

Perú

Argentina

80000

10000

62000

Chile

17000

Ahora buscamos quien esta más cercano a Perú , como ecuador es el
más cercano a Perú, toma a Ecuador.
C3= {Perú, chile} + {ecuador}
C3={Perú, chile, ecuador}
ĉ3= {Colombia, argentina, Venezuela, Paraguay, Bolivia, Brasil}

22000
Colombia

Venezuela

Brasil
90000

70000

55000

14000
20000

Ecuador

Bolivia

15000

Paraguay
30000

12000
13000

90000

40000

Perú

Argentina

80000

10000

62000

Chile

17000

Ahora buscamos quien esta más cercano a Perú , como Bolivia es el más...