Discussioni su Analisi Numerica e Ricerca Operativa

Regole del forum

Consulta il nostro regolamento e la guida per scrivere le formule
Rispondi al messaggio

Matrice di incidenza nodo arco?

17/01/2021, 03:40

Salve, ho un dubbio sul problema del cammino minimo singola origine singola destinazione.

Nelle dispense del mio corso di ricerca operativa, viene detto che la matrice dei coefficienti tecnologici di un problema del cammino minimo da un nodo $s$ ad un nodo $d$ di un grafo orientato e pesato $(G,A,c)$, con $c$ non negativa, è pari alla matrice di incidenza nodo-arco di $G$.

Mi sapreste aiutare a capire il perché? Aggiungo di sotto i vincoli che mi definiscono la matrice dei coefficienti tecnologici.
Definito $x_{ij}=1$ se e solo se $(i,j)$ appartiene al cammino minimo tra $s$ e $d$, i vincoli da considerare sono i seguenti :
$$\sum_{j\in \text{FS(i)}}x_{ij}-\sum_{j\in \text{BS(i)}}x_{ji}=\begin{cases}
1, & i=s\\
-1, & i=d\\
0, & \text{altrimenti}
\end{cases}$$
essendo $FS(i)$ e $BS(i)$ la stella uscente ed entrante di $i$.
Rispondi al messaggio


Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000— Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.