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 en un 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 SE NUMERAN : 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 5

Nodos

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

4
6

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 para cada par de nodos i,j  N existe un camino que conecte el nodo i con el nodo j.























GRAFICA G: Conexa

SUBGRAFICA G: 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
[continua]

Leer Ensayo Completo

Cite este ensayo

APA

(2012, 09). Tipos de choques. BuenasTareas.com. Recuperado 09, 2012, de http://www.buenastareas.com/ensayos/Tipos-De-Choques/5371701.html

MLA

"Tipos de choques" BuenasTareas.com. 09 2012. 2012. 09 2012 <http://www.buenastareas.com/ensayos/Tipos-De-Choques/5371701.html>.

MLA 7

"Tipos de choques." BuenasTareas.com. BuenasTareas.com, 09 2012. Web. 09 2012. <http://www.buenastareas.com/ensayos/Tipos-De-Choques/5371701.html>.

CHICAGO

"Tipos de choques." BuenasTareas.com. 09, 2012. consultado el 09, 2012. http://www.buenastareas.com/ensayos/Tipos-De-Choques/5371701.html.