Flusso su grafo capacitato

[lunaxv]

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