Tipos de choques

OPTIMIZACIÓN EN REDES
• EN ALGUNOS PROBLEMAS DE OPTIMIZACIÓN PUEDE SER ÚTIL REPRESENTAR EL PROBLEMA A TRAVÉS DE UNA GRÁFICA: ruteo de vehículos, distribución de producto, programa de actividades enun proyecto, redes de comunicación, etc.
• MODELOS DE REDES: algoritmos especiales

GRÁFICA
• ES UN CONJUNTO DE NODOS (N) Y ARCOS (A) QUE CONECTAN LOS NODOS. NOTAMOS G=(N,A) • LOS NODOS SENUMERAN : 1,2,...,n • LOS ARCOS SE DENOTAN (i,j) indicando que une el nodo i al nodo j

i j

CONCEPTOS BÁSICOS
• Un arco (i,j) es dirigido si conecta i con j pero no j con i.
• Una gráfica G=(N,A)es dirigida si sus arcos están dirigidos. En una gráfica no dirigida (i,j) y (j,i) representan el mismo arco ( no dirigido).

i j

CONCEPTOS BÁSICOS
Gráfica no dirigida

Arcos no dirigidos 5Nodos

2 1
Gráfica dirigida

4
3

7
6 Arcos dirigidos Nodos 5

2

1
3

4 6

7

CONCEPTOS BÁSICOS
• Un Camino o Ruta del nodo i al nodo j es una secuencia de arcos que unen elnodo i con el nodo j: (i,i1), (i1,i2), (i2,i3),...,(ik,j). Ruta de k arcos. • Un Ciclo es un camino que une un nodo consigo mismo:(i,i1), (i1,i2), (i2,i3),...,(ik,i)

CONCEPTOS BÁSICOS
2 1 3 5

46

7

CAMINO DE 4 A 7 CICLO

CONCEPTOS BÁSICOS
• UNA SUBGRÁFICA G’=(N’,A’) DE UNA GRÁFICA G=(N,A) es un conjunto de nodos y arcos de G: N’ N y G’  G. • UNA GRÁFICA G=(N,A) ES CONEXA si paracada par de nodos i,j  N existe un camino que conecte el nodo i con el nodo j.

























GRAFICA G: Conexa

SUBGRAFICAG: no conexa

 SUBGRÁFICA G’: conexa

CONCEPTOS BÁSICOS
• Una RED es una gráfica con uno o mas valores asignados a los nodos y/o a los arcos: Nodos: (ai)demanda, oferta, eficiencia,confiabilidad.
Arcos: (cij) costo, distancia, capacidad Ejemplos: representar a través de una red : red de agua potable, red de comunicación, red logística.

PROBLEMAS Y MODELOS DE REDES
• PROBLEMAS:...