Page 158 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 158
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
hileras y columnas que contienen solo ∞. Cada diferencia a cero se suma en la
variable r. La matriz resultante será B. Ya realizadas todas las substracciones del
paso anterior, entonces:
c (S) = c (R) + A<i, j> + r para nodos hoja c (.) = c( ).
Siendo S el número de nodo actual.
Siendo R el número de nodo padre.
Los dos primeros pasos son válidos y no existirá un recorrido en el subárbol S que contenga las
aristas del tipo <j, k> o <k, j> o <j, 1> (excepto para la arista <i, j>). En este momento r es el monto
total substraído del paso 3, entonces c(S) = c(R) + A<i, j> + r. Para los nodos hoja є(.) = c() es fácil
calcular, ya que cada rama hasta la hoja define un único recorrido. Para la función de la cota superior
u, se requiere usar u(R) = ∞ para todo nodo R.
Siendo S el número de nodo actual.
Siendo R el número de nodo padre.
Para ver el árbol de transición se tomará el siguiente ejemplo:
Tomando la notación de la transición:
I = y
s
donde
I indica en este caso transición.
s indica el nivel //nodo hijo.
y indica la columna.
De esta forma el árbol de trayectorias para el ejemplo quedaría como se muestra en la figura 7.5:
152