Diamo in questa sezione una soluzione parziale alla seconda questione che ci siamo posti: in quali casi l’algoritmo greedy fornisce la soluzione ottima?
Il nostro obiettivo `e quello di caratterizzare la classe dei sistemi di indipendenza per i quali l’algo-ritmo greedy fornisce la soluzione ottima qualunque sia la funzione peso considerata. Dimostreremo (teorema di Rado) che un sistema di indipendenza verifica la propriet`a precedente se e solo se esso `e un matroide.
Un sistema di indipendenza hE, F i `e detto matroide se, per ogni A, B ∈ F tali che |B| = |A| + 1 (qui |X| indica la cardinalit`a di un insieme X), allora esiste b ∈ B − A per cui A ∪ {b} ∈ F . Per esempio, `e facile verificare che, per ogni insieme finito E, la coppia hE, 2Ei forma un matroide.
La nozione di matroide `e stata introdotta nel 1935 da Birkhoff e altri per generalizzare il concetto di dipendenza lineare. Questa nozione ha trovato proficue applicazioni in vari settori, dalla teoria dei grafi agli algoritmi, e pu`o essere considerata un ponte tra l’algebra lineare e la matematica combinatoria.
Esempio 12.3
Sia E un insieme finito di vettori di uno spazio vettoriale V . Sia F la famiglia di sottoinsiemi di E formati da vettori linearmente indipendenti. Si pu`o verificare facilmente che hE, F i forma un matroide, detto matroide vettoriale.
L’esempio pi`u importante di matroide `e tuttavia fornito dal sistema di indipendenza hE, FGi definito nell’Esempio 12.1. La seguente proposizione dimostra questa propriet`a .
Proposizione 12.1 Per ogni grafo non orientato G = (V, E), la coppia hE, FGi `e un matroide.
Dimostrazione. Dall’Esempio 12.1 sappiamo che hE, FGi `e un sistema di indipendenza. Dobbiamo quindi solo provare l’ulteriore condizione sopra definita. A tale scopo, siano A e B due insiemi di lati in FG tali che |B| = |A| + 1. Denotiamo con U l’insieme U = B − A. Chiaramente U 6= ∅ e possiamo porre U = {b1, b2, . . . , bm}. Per assurdo supponiamo ora che ogni bi formi un ciclo con A, ovvero A ∪ {bi} 6∈ FG per ogni i. Sia Ci tale ciclo. Allora, in Ci deve esistere un lato ai ∈ A − B, altrimenti avremmo un ciclo interamente incluso in B contro l’ipotesi B ∈ FG. Inoltre, possiamo scegliere a2 6= a1, altrimenti l’insieme C1∪ C2− {a1} forma nuovamente un ciclo in B. Per lo stesso
motivo possiamo scegliere a3 diverso da a2 e a1 e cos`ı via: tutti gli ai, per i = 1, 2, . . . , m, possono essere scelti in modo distinto dai precedenti. Di conseguenza |A| ≥ m + |A ∩ B| = |U | + |A ∩ B| = |B|, ma questo `e assurdo perch`e abbiamo supposto |B| = |A| + 1.
La coppia hE, FGi `e anche chiamata matroide grafico.
Un risultato interessante, che fornisce una interpretazione algoritmica dei matroidi, `e il seguente:
Teorema 12.2 (Rado) Dato un sistema di indipendenza hE, F i, le seguenti proposizioni sono
equiva-lenti:
a) per ogni funzione peso w : E → IR+, l’algoritmo MIOPE fornisce una soluzione ottima al problema di massimo su input E, F, w;
b) hE, F i `e un matroide.
Dimostrazione. Proviamo innanzitutto che se hE, F i non `e un matroide allora esiste una funzione peso
w : E → IR+per la quale l’algoritmo greedy non fornisce la soluzione ottima. Infatti, poich´e hE, F i non `e un matroide, esistono due insiemi A, B ∈ F tali che, per qualche k ∈ IN,
|A| = k, |B| = k + 1, e inoltre b ∈ B − A ⇒ A ∪ {b} 6∈ F
Definiamo ora una funzione peso w nel modo seguente. Scelto α > 1, poniamo per ogni x ∈ E:
w(x) = α se x ∈ A 1 se x ∈ B − A 0 se x ∈ (A ∪ B)c
Assegnata tale funzione peso, l’algoritmo greedy fornir`a una soluzione S, formata da tutti gli elementi in A (i quali, avendo peso maggiore, verranno selezionati per primi) pi`u , eventualmente, un insieme di elementi C ⊆ (A ∪ B)c. Nota che in S non vi possono essere elementi di B − A in quanto, per ogni b ∈ B − A, abbiamo A ∪ {b} 6∈ F . Posto t = |A ∩ B|, abbiamo
w(S) = w(A ∪ C) = w(A) + w(C) = α · |A| = α · k w(B) = w(B − A) + w(A ∩ B) = (k + 1 − t) + α · t Ne segue allora che
w(S) < w(B) ⇐⇒ α · k < k + 1 − t + α · t ⇐⇒ α < 1 + 1 k − t Quindi, se scegliamo α tale che
1 < α < 1 + 1 k − t,
si verifica che la soluzione S costruita dall’algoritmo greedy non `e ottima.
Viceversa, dimostriamo ora che, se hE, F i `e un matroide, comunque si scelga una funzione peso w : E → IR+, l’algoritmo greedy restituisce la soluzione ottima. Sia infatti S = {b1, b2, . . . , bn} la soluzione fornita dall’algoritmo, con w(b1) ≥ w(b2) ≥ · · · ≥ w(bn). Sia A = {a1, a2, . . . , am} un qualunque elemento di F , con w(a1) ≥ w(a2) ≥ · · · ≥ w(am).
Innanzitutto verifichiamo che m ≤ n. Infatti se fosse n < m, essendo hE, F i un matroide, es-isterebbe aj ∈ A − S tale che S ∪ {aj} ∈ F . Inoltre, tutti i sottoinsiemi di S ∪ {aj} apparterrebbero a F ,
e di conseguenza l’algoritmo non avrebbe scartato ajma lo avrebbe inserito nella soluzione, restituendo l’insieme S ∪ {aj} invece di S.
Quindi m ≤ n e dimostriamo allora che w(ai) ≤ w(bi) per ogni i = 1, 2, . . . , m. Infatti, per assurdo, sia k il primo intero tale che w(ak) > w(bk). Nota che l’insieme D = {b1, b2, . . . , bk−1} appartiene a F e inoltre |D| + 1 = |{a1, a2, . . . , ak}|. Di conseguenza, essendo hE, F i un matroide, esiste un intero j, 1 ≤ j ≤ k, tale che aj 6∈ D e D ∪ {aj} ∈ F . Poich´e l’algoritmo greedy sceglie al passo k-esimo l’elemento di peso massimo tra quelli disponibili, abbiamo w(bk) ≥ w(aj); d’altro lato, essendo j ≤ k, abbiamo w(aj) ≥ w(ak) e quindi w(bk) ≥ w(aj) ≥ w(ak), contro l’ipotesi w(ak) > w(bk). Questo prova che w(A) ≤ w(S) e quindi la soluzione fornita dall’algoritmo `e ottima.
Anche per il problema di minimo `e possibile provare che l’algoritmo greedy fornisce la soluzione ottima sui matroidi.
Corollario 12.3 Se un sistema di indipendenza hE, F i `e un matroide allora, per ogni funzione peso
w : E → IR+, l’algoritmo MIOPE-MIN fornisce una soluzione ottima al problema di minimo (su input
E, F, w).
Dimostrazione. Innazitutto `e facile verificare che in ogni matroide hE, F i gli insiemi A ∈ F massimali
hanno la stessa cardinalit`a . Sia quindi m la cardinalit`a degli insiemi massimali in F . Inoltre, data una funzione peso w : E → IR+, fissa p = max{w(x) | x ∈ E} e definisci la funzione w0 : E → IR+ ponendo w0(x) = p − w(x), per ogni x ∈ E. Allora, per ogni A ∈ F massimale, abbiamo w0(A) = mp−w(A) e quindi w0(A) `e massimo se e solo se w(A) `e minimo. Per il teorema precedente la procedura MIOPE su input E, F, w0determina l’elemento S ∈ F di peso massimo rispetto a w0. Tuttavia `e facile verificare che S `e anche l’output della procedura MIOPE-MIN su input E, F, w. Di conseguenza, per l’osservazione precedente, S `e anche insieme massimale in F di peso minimo rispetto a w.
Esercizi
1) Dato un grafo non orientato G = hV, Ei nel quale V `e l’insieme dei nodi ed E quello degli archi, definiamo la seguente famiglia di sottoinsiemi di E:
F = {A ⊆ E | ∃v ∈ V tale che ogni lato α ∈ A `e incidente a v}
Per ipotesi assumiamo ∅ ∈ F .
a) La coppia hE, F i forma un sistema di indipendenza? b) La coppia hE, F i forma un matroide?
c) Considera il problema di determinare l’elemento di peso massimo in F assumendo per istanza un grafo G con pesi positivi associati agli archi. Descrivere un algoritmo greedy per tale problema.
d) L’algoritmo descritto al punto c) determina sempre la soluzione ottima?
2) Ricordiamo che in un grafo non orientato G = hV, Ei (dove V `e l’insieme dei nodi e E quello dei lati) una clique `e un sottoinsieme C ⊆ V tale che, per ogni u, v ∈ C, se u 6= v allora {u, v} ∈ E. Sia FGla famiglia di tutte le clique di G, cio`e
FG= {A ⊆ V | ∀u, v ∈ A, u 6= v ⇒ {u, v} ∈ E}
a) La coppia hV, FGi forma un sistema di indipendenza?
c) Dato un grafo non orientato G = hV, Ei e una funzione peso w : V −→ IR+, ogni insieme A ⊆ V ammette un peso w(A) definito da
w(A) =X
x∈A
w(x).
Descrivere una procedura greedy che cerca di determinare un insieme C ∈ FGdi peso massimo in FG. La soluzione prodotta dall’algoritmo `e sempre ottima?
3) Svolgere l’analisi dell’algoritmo greedy per il problema di minimo introdotto nella sezione 12.1.