Norme per inviare contributi

Spedire i contributi alla discussione per e-mail a malucell@elet.polimi.it.
I contributi devono essere sintetici, riportare nel subject "Forum" e la data del quesito, e l'identificazione chiara del mittente.

In una rete di flusso è presente un arco (i,j) con costo negativo. Come modificare la rete in modo da mantenere l'equivalenza?

soluzione

Modificare l'algoritmo di Dijkstra per determinare il cammino con peso minimo degli archi massimo.

soluzione

Valutare la complessità computazionale dell'algoritmo dei cammini aumentanti applicato al caso di grafo bipartito con capacità unitarie (problema di assegnamento di cardinalità massima).

Si vogliono accoppiare i nodi facenti parte di due insiemi, Ns (insieme di partenza) ed Nt (insieme di arrivo).
Formuliamo il problema come rete di flusso ed aggiungiamo il nodo sorgente (s) ed il nodo destinazione (t).
Dal nodo sorgente partono archi di capacità massima 1 verso i nodi dell'insieme Ns (uno verso ogni nodo).
Dagli archi dell'insieme Nt partono archi verso il nodo t (uno da ogni nodo).
Immaginiamo che |Ns|=|Nt| =n. Inoltre poniamo |A| = m, dove A è l'insieme che comprende tutti gli archi del grafo.
Utilizziamo l'algoritmo dei cammini aumentati.
Ad ogni iterazione il flusso aumenta esattamente di un'unità, per un massimo di n unità, e, nel caso pessimo, saremo costretti ad esaminare tutti gli m archi del grafo.
In tal caso la complessità dell'algoritmo è THETA(m*n).
Nel caso più generale in cui |Ns|!=|Nt| allora sappiamo che il flusso può aumentare al massimo di una quantità minore o uguale al min(|Ns|,|Nt|).
In tal caso la complessità dell'algoritmo diventa THETA(m*min(|Ns|,|Nt|)).

Formulare il problema di taglio di capacità minima tra due nodi s e t di un grafo orientato con capacità sugli archi:

soluzione

(nota: nella soluzione proposta vi sono dei vincoli ridondanti, vista la natura della funzione obiettivo, quali?)

Che differenza c'e' tra un albero di copertura di peso minimo e l'albero dei cammini minimi? fornire un esempio in cui le soluzioni dei due problemi sono diverse.

Nell'allegato presente riporto il mio esempio sottolineando in verde l'albero di copertura minimo e in rosso l'albero dei cammini minimo.
 
La differenza base è che nel caso dell'albero dei cammini minimi il peso di un arco utilizzato per due cammini (ad esempio) viene contato due volte.
Spero che la mia risposta le sia chiara e che sia esatta.
                                  
                                   distinti saluti Lorenzo D'Ercole