TERMINOLOGIA DE REDES

Una red consiste en un conjunto de puntos y un conjunto de líneas que unen

ciertos pares de puntos. Los puntos se llaman nodos o vértices; por ejemplo, la
red de la figura 9.1 tiene siete nodos representados por siete círculos. Las
líneas se llaman arcos o ligaduras, aristas o ramas; por ejemplo la red del la
figura 9.1 tienen 12 arcos que corresponden a los 12 caminos del sistema del
parque. Los arcos se etiquetan para dar nombre a los nodos en sus puntos
terminales; por ejemplo en la figura 9.1, AB es el arco entre los nodos A y B.

Figura 9.1 Sistema de caminos del Seervada Park

T
2 2 7
5

5 B 4 D
O
7
3 1
4 1

C E
4

Los arcos de una red pueden tener un flujo de algún tipo que pase por ellos;
por ejemplo; el flujo de camionetas sobre los caminos de Seervada Park en la
sección 9.1. L a tabla 9.1 proporciona varios ejemplos de flujo en redes. Si el
flujo a través de un arco se permite solo en una dirección, como en una calle de
un sentido, se dice que el arco es un arco dirigido. La dirección se indica al
agregar una cabeza de flecha al final de la línea que representa el arco.
Cuando se etiqueta un arco dirigido con el nombre de los nodos que une
siempre se pone primero el nodo de donde viene y después el hacia donde va,
esto es, un arco dirigido del nodo A al nodo B debe etiquetarse como AB y no
como BA. Otra manera de etiquetarlo es A → B.

Tabla 9.1 componentes de redes representativas

Nodos Arcos Flujo

Cruceros Caminos Vehículos
Aeropuertos Líneas Aéreas Aviones
Puntos de conmutación Cables, canales Mensajes
Estaciones de bombeo Tuberías Fluidos
Centros de trabajo Rutas de manejo de Trabajos
materiales
Aunque se permita que el flujo a través de un arco no dirigido ocurra en
cualquier dirección, se supone que ese flujo será solo en una dirección, en la
seleccionada, y no se tendrán flujos simultáneos en direcciones opuestas.
(Este último caso requiere usar un par de arcos dirigidos en direcciones
opuestas). En el proceso de toma de decisiones sobre el flujo de un arco no
dirigido, se permite hacer una serie de asignaciones de flujos en direcciones
opuestas, pero en el entendido de que el flujo real será el flujo neto, la
diferencia de los flujos asignados en las dos direcciones. Por ejemplo, si se
asigna un flujo de10 en una dirección y después un flujo de 4 en la dirección
opuesta, el efecto real es la cancelación de 4 unidades de la asignación
original, lo que reduce el flujo en la dirección original de 10 a 6. Aun en el caso
de un arco dirigido, en ocasiones se usa la misma técnica como una manera
conveniente de reducir un flujo asignado con anterioridad. En particular, se
puede hacer una asignación ficticia de flujo en la dirección “equivocada” a
través de un arco dirigido para registrar una reducción en esa cantidad del flujo
que va en la dirección “correcta”
Una red que tiene solo arcos dirigidos se llama red dirigida. De igual manera,
si todos sus arcos son no dirigidos, se dice que se trata de una red no dirigida.
Una red con una mezcla de arcos dirigidos y no dirigidos o incluso una con
todos sus arcos no dirigidos se puede convertir en una red dirigida, si se desea,
mediante la sustitución de cada arco no dirigido por una par de arcos dirigidos
en direcciones opuestas. (Después se puede optar por interpretar los flujos a
través de cada par de arcos dirigidos como flujos simultáneos en direcciones
opuestas o de proporcionar un flujo neto en una dirección, según convenga el
caso.)
Cuando dos nodos no están unidos por un arco es valido preguntar si están
conectados por una serie de arcos. Una trayectoria entre dos nodos es una
sucesión de arcos distintos que conectan estos nodos. Por ejemplo, una de las
trayectorias que conectan a los nodos O y T en la figura 9.1 es la sucesión de
arcos OB-BD-DT (O → B → D → T), y viceversa. Cuando algunos o todos los
arcos de una red son arcos dirigidos, se hace la distinción entre trayectorias
dirigidas y trayectoria no dirigidas. Una trayectoria dirigida del nodo i al nodo j
es una sucesión de arcos cuya dirección (si la tiene) es hacia el nodo j, de
manera que el flujo del nodo i al nodo j através de esta trayectoria es factible.
Una trayectoria no dirigida del nodo i al nodo j es una sucesión de arcos cuya
dirección (si la tiene) puede ser hacia o desde el nodo j. (obsérvese que una
trayectoria dirigida también satisface la definición de trayectoria no dirigida pero
el inverso no se cumple.). Con frecuencia una trayectoria no dirigida tendrá
unos arcos dirigidos hacia el nodo j y otros desde el – es decir, hacia el nodo i
-. En las secciones 9.5 y 9.7 se vera que tal vez de manera sorprendente las
trayectorias no dirigidas juegan un papel muy importante en el análisis de las
redes dirigidas.
Para ilustrar estas definiciones, la figura 9.2 muestra una red dirigida común.
(Sus nodos y arcos son los mismos que los de la figura 3.13, donde los nodos
A y B representan dos fabricas y los nodos D y E representan dos almacenes,
en nodo C es un centro de distribución y los arcos representan las rutas de
embarque). La sucesión de arcos AB-BC-CE es una trayectoria dirigida
(A→B→C→E) del nodo A al nodo E, puesto que el flujo hacia el nodo E en toda
esta trayectoria es factible. Por otro lado, BC-AC-AD (B→C→A→D) no es una
trayectoria dirigida del nodo B la nodo D, por que la dirección del arco AC es
desde el nodo B (sobre esta trayectoria). No obstante, B→C→A→D es una
trayectoria no dirigida del nodo B al nodo D, debido a que la secuencia de BC-
AC-AD conecta a estos dos nodos- aun cuando la dirección del arco AC evita el
flujo a través de esta trayectoria-.
Como ejemplo de la relevancia de las trayectorias no dirigidas, suponga que se
habían asignado dos unidades de flujo del nodo A al nodo C al arco AC. En
razón de esta asignación previa, ahora es factible asignar un flujo mas
pequeño, por ejemplo una unidad, a la trayectoria no dirigida B→C→A→D,
aunque la dirección de AC evite un flujo positivo através de C→A. la razón es
que esta asignación de flujo en la dirección “equivocada” para el arco AC en
realidad solo reduce el flujo en la dirección “correcta” en una unidad. Las
secciones 9.5 y 9.7 hacen un uso amplio de esta técnica de asignación de
flujos a través de una trayectoria no dirigida que incluye arcos cuya dirección es
opuesta al flujo, y en la que el efecto real para estos arcos es una reducción de
los flujos positivos asignados antes en la dirección “correcta”.
Un ciclo es una trayectoria que comienza y termina en el mismo nodo. En una
red dirigida un ciclo puede ser dirigido y no dirigido, según la trayectoria en
cuestión sea dirigida o no dirigida. (Como una trayectoria dirigida también es no
dirigida, un ciclo dirigido es un ciclo no dirigido, pero en general el inverso no es
cierto) por ejemplo, en la figura 9.2 de DE-ED es un ciclo dirigido. Por el
contrario, AB-BC-CA no es un ciclo dirigido puesto que la dirección del arco AC
es opuesta a la de los arcos AD y BC. Por otro lado, AB-BC-AC no es un ciclo
dirigido por que A→B→C→A es una trayectoria no dirigida. En la red no
dirigida que se muestra en la figura 9.1 existen muchos ciclos. Por ejemplo,
OA-AB-BC-CA. De cualquier forma observe que la definición de trayectoria –
una sucesión de arcos distintos- elimina la posibilidad de retroceder al formar
un ciclo. Por ejemplo, OB-BO en la figura 9.1 no califica como ciclo, por que OB
y BO son dos etiquetas del mismo arco (ligadura). Por otra parte, en la figura
9.2, DE-ED es un ciclo (dirigido) por que DE y ED son arcos distintos.
Se dice que dos nodos están conectados si la red contiene al menos una
trayectoria no dirigida entre ellos. (Observe que no es necesaria que la
trayectoria sea dirigida aun cuando la red es dirigida). Una red conexa es una
red en la que cada par de nodos esta conectado entonces como las redes de
las figuras 9-1 y 9.2 son ambas conexas. La ultima red no seria conexa si se
eliminara los arcos AD y CE.
Considere una red conexa con n nodos – por ejemplo, los n = 5 nodos de la
figura 9.2 – en la que han sido eliminados todos los arcos. Se puede “hacer
crecer” un “árbol” si se agrega un arco- o “rama”- a la vez a partir de la red
original de cierta manera. El primer arco puede ir en cualquier lugar de modo
que conecte algún par de nodos. De ahí en adelante, cada arco nuevo debe
agregarse entre un nodo que haya sido conectado a otros nodos y a un nuevo
nodo no conectado. Si se agregan arcos de esta manera, se evita que se forme
un ciclo y además se asegura que el número de nodos conexos sea uno mas
que el numero de arcos. Cada nuevo arco crea un árbol mas grande, que es
una red conexa-para algún subconjunto de n nodos- que no contiene ciclos no
dirigidos. Una vez agregado el (n-1)-esimo arco, el proceso se detiene por que
el árbol resultante se expande (conecta) hacia todos los n nodos. Este árbol,
que se llama árbol de expansión que es una red conexa para los n nodos que
contienen ciclos no dirigidos. Todo árbol de expansión tiene exactamente n-1
arcos puesto que este es el número mínimo de arcos necesarios para tener
una red conexa y el máximo numero posible para que no haya ciclos no
dirigidos.
En la figura 9.3 se muestra los 5 nodos y alguno de los arcos de la figura 9.2
para ilustrar este proceso de hacer crecer un árbol mediante la colocación de
un árbol (rama) a la vez, hasta que se obtiene un árbol de expansión. En cada
etapa del proceso existen varias alternativas para el nuevo arco por lo que la
figura 9.3 muestra solo una de las muchas formas de construir un árbol de
expansión en este caso. Sin embargo observe como cada nuevo arco que se
agrega satisface las condiciones especificadas en los párrafos anteriores. Los
árboles de expansión se estudiaran más a fondo en la sección 9.4. los
árboles de expansión tienen un papel clave en el análisis de muchas redes.
Por ejemplo, forman la base del problema del árbol de minima expansión que
se presentan en la sección 9.4. Otro ejemplo es que los árboles de expansión
(factibles) corresponden a las soluciones BF del método simple de redes que
se analizan en la sección 9.7.
Por último será necesario producir terminología adicional sobre los flujos en
redes. La cantidad máxima de flujo (quizá infinito) que puede circular en un
arco dirigido se conoce como capacidad del árbol. Entre los nodos se puede
distinguir aquellos que son generadores de flujo, absorbedora netos o ninguno
de los dos. Un nodo fuente- o nodo origen –tiene la propiedad de que el flujo
que sale del nodo supera al que entra a el caso inverso es un nodo demanda-
o nodo destino-, donde el flujo que llega excede a al que sale de el. Un nodo de
transbordo (o intermedio) satisface la conservación del flujo, es decir, el flujo
que entra es igual al que sale.
Figura 9.3
Ejemplo de hacer crecer un árbol poniendo
Un arco a la vez en la red de la figura 9.2 (a).
Los nodos sin arcos;(b) árbol con un arco; (c)
Árbol con dos arcos;(d) árbol con tres arcos;(e)
Árbol de expansión.

A D
A D

C
C

E
B E
D

a)

A D

A D
A D

C B E