Ottimizzazione Combinatoria 2

Sistemi di Indipendenza

definizioni ed esempi

Prof. Antonio Sassano

Dipartimento di Informatica, Automatica e Gestionale “Antonio Ruberti”

Università di Roma “Sapienza”

A.A. 2016

Sistemi di Indipendenza

• Insieme base G = {1,2,…,n} (elementi)

• Insieme delle soluzioni ammissibili

S = { F1 , F2 , … , Fm } (Fi G )

• S Sistema di Indipendenza (Independence System)

T Fi T S

1

S

2

3

4 5

6 7

• B è una Base di S BS T B T S

Basi

1

2

3

4 5

6 7

• C è un Circuito di S CS T C TS

Circuiti

1

2

3

4 5

6 7

Sistemi di Indipendenza

TS { T B : B Base di S }

TS { C T : C Circuito di S }

TS T è un dipendente di S

TS T è un indipendente di S

Le basi definiscono il sistema di indipendenza

Indipendenti = sottoinsiemi di G contenuti in qualche base

.. anche i circuiti definiscono il sistema di indipendenza

Indipendenti = sottoinsiemi di G che non contengono un circuito (ogni dipendente contiene un circuito)

Sistemi di Indipendenza (esempio 1)

S = {insiemi stabili di un grafo G(V,E)}

S = { , { v1 }, {v1 , v2 }, … }

Basi = stabili massimali

v7

v4 v1

v3

v2

G(N,A)

v9 v5 v8

v6

Circuiti = vi vhE

Elementi = nodi

Insiemi di nodi a coppie non adiacenti

T non stabile contiene gli estremi di un arco

T massimale non contenuto propriamente in uno stabile

Sistemi di Indipendenza (esempio 2)

S = {“matching” di un grafo G(V,E)}

S = { , { v1v2 }, {v3v8},

{ v1v2 ,v3v8}, … }

Basi = “matching” massimali

Elementi = archi

Insiemi di archi a coppie non incidenti nello stesso nodo

T non è un “matching” (almeno) due archi incidenti

v7

v4

v1

v3

v2

v9 v5 v8

v6

Circuiti = {ei ,eh} con ei , eh incidenti nello stesso nodo

( che non sono contenuti propriamente in un “matching” )

Sistemi di Indipendenza (esempio 3)

S = { foreste di un grafo G(V,E)}

Base = Albero Ricoprente

Circuito = ciclo

Elementi = archi b

a

d

w

e y

g G(V,E) foresta F E H(V,F) foresta

F non è una foresta F contiene un ciclo

Notazione: G(V,F) foresta

F foresta

Sistemi di Indipendenza (esempio 4)

S = {insiemi di vettori linearmente indipendenti }

Base = insieme massimale di vettori linearmente indipendenti

Circuito = insieme minimale di vettori linearmente dipendenti

Elementi = vettori

linearmente indipendenti

j00v jQj

n

j

j

nt21 Rvvv ,...,,G

QS

1

2

3

4

-1 -1

0

1 0 0

1 0 0

v1 v2 v3 v4 v5

0 0 0

1 0 -1

1

1

-1

0

-1

Base

431 vvvB ,,

1

2

3

4

-1 -1

0

1 0 0

1 0 0

v1 v2 v3 v4 v5

0 0 0

1 0 -1

1

1

-1

0

-1

Circuito

321 vvvC ,,

Sistemi di Indipendenza (esempio 5)

S = { insiemi di progetti “compatibili” con un “budget”}

3x1+2x2+x3+2x4 5

S = { , { 1 }, { 2 }, {1 , 2 }, {2, 3, 4 } … }

Base = insieme di progetti “compatibile” massimale

Circuito = un insieme di progetti non “compatibile”

ma tale che ogni sottoinsieme è “compatibile”

Elementi = progetti

“budget” “risorse” per il progetto

Indipendenti = soluzioni di “knapsack” a coefficienti positivi

{1 , 2 , 3}

{1 , 4 }

Sistemi di Indipendenza (esempio 5)

S = { sotto-sistemi di disequazioni ammissibili }

(a) x1-x2 1 (b) x2-x3 -3 (c) x3-x1 1 (d) x1-x4 -2 (e) x4-x5 1 (f) x5-x1 0

Elementi = disequazioni

Base = insieme di disequazioni ammissibile massimale

Circuito = un insieme di disequazioni non ammissibile

ma tale che ogni sottoinsieme è ammissibile {a,b,c}

non ammissibile

{a,b,e,f}

Sistemi di Indipendenza (esempio 6)

S = { insiemi di archi la cui rimozione non

disconnette il grafo G(N,A) }

S = { , {v1v8 }, {v1v8 ,v2v3},… }

Base = Complemento di un albero ricoprente

v9

v4 v8

v3

v2

G(N,A) v1 v5 v7

v6

Circuiti = Tagli minimali

Elementi = archi

( non contengono propriamente un taglio)

TS connesso )T,N(H

Grafo connesso G(N,A)