Ing de Sistemas Redes

4 REDES
4.1 Conceptos y definiciones
Una red o grafo es un conjunto de puntos llamados nodos, que están unidos entre sí por líneas que se denominan arcos.
Algunos problemas que se presentan en la realidad, sobre todo, en las ciudades; se pueden modelar como una red, por ejemplo:
Sistemas de transporteSistemas de distribución
Sistemas de comunicación
Una red se puede describir numerando los nodos y los arcos que la constituyen. Así, los nodos se numeran o se indican con letras del alfabeto, y el arco se denota por los nodos o puntos que conecta.
Además de la representación gráfica, una red también puede representarsecomo una matriz booleana (formada por ceros y unos), en donde los i renglones y las j columnas serán los nodos de la red. Un cero en el elemento (i,j) de la matriz indica que no hay arco uniendo al nodo i con el nodo j. Si el elemento (i,j) de la matriz es uno, indica que sí hay un arco uniendo al nodo i con el nodo j.Figura 4.1 Matriz booleana de una red

Un arco puede ser dirigido, si tiene asociado un sentido o no dirigido, en el caso de que no lo tenga.
Si la red sólo tiene arcos dirigidos, se trata de una red dirigida.
Una cadena es un conjunto ordenado de arcos que conectan a dosnodos por medio de nodos intermedios.
Una red conexa es una red para la cual existe una cadena entre cualquier par de nodos.
Un anillo o ciclo es una cadena que conecta a un nodo con él mismo.
Un árbol es una red conexa que no tiene anillos.



Tabla 4.1 Tipos de red y algoritmos
Conceptos
Tipo de red
Algoritmos

Cadena


Dirigida

Flujo máximo (Ford y Fulkerson)
GráficoFlujo máximo (Labeling Technique)
Numérico (matriz)
Red conexa


Gráfico


Flujo máximo
Gráfico

Anillo

No dirigida
Caminos de valor óptimo
Máximo



Mínimo


Árbol
Máxima expansión
Árbol






Mínima expansión


El cartero chino
Gráfico

4.2 Flujo máximo, red de transporte
Definición
Se llama red de transporte a una gráfica finita sin anillos tal que:
a.Cada arco u tiene asociado un número c(u) 0 llamado capacidad del arco.
b. Existe un vértice x0 y uno solo tal que w+(x0)= este vértice se llama fuente de la red.
c. Existe un vértice xn y uno solo tal que w-(xn)= este vértice se llama sumidero de la red.

Flujo
Sean w-(xi) el conjunto de los arcos incidentes al vértice xi hacia el interior y w+(xi) el conjunto de arcos incidentes alvértice xi hacia el exterior. Se dice que una función entera (u) definida sobre el conjunto A de los arcos ui es un flujo para una red de transporte si:
(4.1)
xix0(4.2)
xixn

(4.3)
Puede pensarse que es un gasto que fluye por el arco u y que nunca puede exceder lacapacidad c(u) de dicho arco. Aún más, si xi no es ni la fuente ni el sumidero, entonces (4.2) significa que el gasto que llega a xi es igual al gasto que sale de xi , que es la llamada propiedad conservativa del flujo.
De acuerdo con lo anterior se deberá tener:
(4.4)
A se le llama el valor del flujo. Se tratará el...