Terminología de redes (III)

Cuando dos nodos no están unidos por un arco surge la pregunta natural de 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 10.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 trayectorias no dirigidas. Una trayectoria dirigida del nodo i al nodo j es una sucesión de arcos cuya dirección (si la tienen) es hacia el nodo j, de manera que el flujo del nodo i al nodo j a través e esta trayectoria sea factible. Una trayectoria no dirigida del nodo i al nodo j es una sucesión de arcos cuya dirección (si la tienen) 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á algunos arcos dirigidos hacia el nodo j y otros desde él (es decir, hacia el nodo i). En las secciones 10.5 y 10.6 se verá que, tal vez de manera sorprendete, las trayectorias no dirigidas juegan un papel muy importante en el análisis de la redes dirigidas.

Para ilustrar estas definiciones, la figura 10.2 muestra una red dirigida común, la sucesión de arcos AB-BC-CE (A→ B→ C→ E) es una trayectoria dirigida del nodo A al nodo E, ya que el flujo hacia el nodo E a lo largo de toda esta trayectoria es factible. Por otro lado, BC-AC-AD (B→ C→ A→ D) no es una trayectoria dirigida al nodo B al nodo D, porque la dirección del arco AC es desde el nodo D (sobre su trayectoria). No obstante, B→ C→ A→ D es una trayectoria no dirigida del nodo B al nodo D. Como ejemplo de la relevancia des esta trayectoria no dirigida, supóngase que 2 unidades del flujo del nodo A al nodo C se habían asignado antes del arco AC. dada esta asignación previa, ahora es factible asignar un flujo más pequeño, D, ya que esto implica reducir el flujo sobre el arco AC en 1 unidad. La reducción de un flujo asignado antes "en la dirección equivocada" cuando se agrega un flujo a una trayectoria no dirigida será un concepto medular en las secciones 10.5 y 10.6