Sono alle prese con la determinazione di un flusso di base su un grafo capacitato...
Abbiamo un grafo capacitato e ne facciamo un tri-partizione
L= insieme degli archi NON in base e NON saturi
U=insieme degli archi saturi(dove il flusso e' pari alla capacita')
B=insieme degli archi della base (albero di copertura)
Allora:
-sia Xb le soluzioni del flusso per gli archi in base
-sia Eb la matrice di incidenza per gli archi in base (dove e' gia stata eliminata una riga cioe quella relativa al nodo finale, perche altrimenti il sistema e' sovradeterminato)
-sia b il vettore dei bilanciamenti dei nodi
-sia Eu la matrice di incidenza relativa agli archi saturi
-sia Uu il vettore delle capacita' degli archi saturi
Allora la mia dispensa riporta che le soluzioni di base Xb sono:
Eb*Xb + Eu*Xu = b
Ma siccome Xu=Uu (viene dimostrato), allora segue che:
Eb*Xb = b - Eu*Uu
Questa cosa nn mi torna.. Perche' b e' un vettore riga o cmq colonna nn importa questa cosa ed Eu*Uu e' una matrice 5*5 !!!!!!!!!!
infatti Eu nel caso in cui ci sia sono un arco saturo e' un vettore colonna 5*1 ed Uu e' un vettore 1*5 contente la capacita' dell'arco saturi..
Quindi sottrarre un vettore colonna b da una 5*5 la vedo dura'...
Ora Immagino che ci sia un mistero dietro il vettore Uu...
Perche' della matrice di incidenza Eu c'e' poco da ragionare.. e il vettore b dei bilanciamenti dei nodi,pure..
Chi sa che COOOOOOSa e' questo Uu ?
grazie