Dimostrazioni Ottimizzazione Combinatoria Bruni

Dimostrazioni ottimizzazione combinatoria

Dimostrazione F1: Soluzione di base ammissibile (S.B.A) è foresta di G(N,A)

Svolgimento:

• Solo se
  1. Dalla definizione di soluzione di base segue che:
     ′ −1 ′ ≥ 0 ′ = ( ) = ( ) ′ 0 ′
     Dove per definizione B è una sottomatrice non singolare di M, e il vettore corrisponde ai termini noti.
     Per ipotesi (si dà per noto), le colonne di B corrispondenti agli archi definiscono un albero ricoprente di G.
  2. Da questo deriva che se tutte le componenti di sono maggiori di 0, e quindi la base è non degenere, il flusso relativo alla S.B.A è proprio uguale a, altrimenti sarà incluso nell'albero ricoprente, ovvero sarà un insieme di archi di una foresta.
• Se
  1. Si indica con la matrice ottenuta togliendo ad M la riga ridondante.
     ′( ) ⊂ .
     Dato il supporto di x e stabilito che il grafo è connesso, allora esisterà una sottomatrice B, che conterrà gli "n" archi dell'albero ricoprente, e le "n-1" righe della matrice, sarà inoltre non singolare. Ma allora
  2. Quindi è l'albero ricoprente relativo alla matrice B, dove ha componenti non nulle solo in corrispondenza delle colonne di B. Questo implica che è S.B.A.

Dimostrazione F2: Soluzione di base ammissibile (S.B.A) è vettore di incidenza su un cammino orientato P da a

Svolgimento:

• Solo se
  1. Dal teorema F1, si ha che essendo una S.B.A, gli archi del suo supporto definiscono una foresta H(N, relativa al grafo G(N,A).
  2. Si dimostra come non possa esistere una foglia z, appartenente alla foresta H(N, che sia diversa da s o da t.
     Per assurdo: Si suppone che esista una foglia z diversa da s o da t.
     (Si definisce Foglia un nodo che non abbia figli. La foresta è invece un sotto grafo del grafo G(N,A), dove non sono presenti cicli – possono però essere presenti nodi isolati, non è detto che H sia connesso).
  3. Si chiama f l'unico arco incide...