• Non ci sono risultati.

Richiami di teoria dei grafi

N/A
N/A
Protected

Academic year: 2021

Condividi "Richiami di teoria dei grafi"

Copied!
2
0
0

Testo completo

(1)

Richiami di teoria dei grafi

Definizioni di base, grafi simmetrici, asimmetrici e antisimmetrci, grafo complemento, grafo completo e grafo vuoto, isomorfismo. Sottografi (indotti), cammini, catene e percorsi, connessione debole e forte, componenti connesse, grado, teorema del grado, numero di nodi con grado dispari in un grafo simmetrico. Insieme stabile e clique.

Numero di clique e numero di stabilità. Diametro di un grafo simmetrico. Colorazione di un grafo simmetrico. Numero cromatico. Grafi k-colorabili. Grafi bipartiti e loro caratterizzazione. Matching. Esempi. Grafi bipartiti completi. Grafi privi di cicli: alberi e foreste. Grafi d-regolari: matching e grafi cubici. Grafi intersezione: grafi intervallo e loro proprietà. Grafi cordali. Colorazione e numero di clique di un grafo intervallo.

Grafi intersezione: grafi intervallo d-dimensionali. Grafo di adiacenza (edge-graph) di un grafo simmetrico. Numero di clique e di stabilità di un grafo di adiacenza.

Richiami di algebra lineare

Vettori, scalari e operazioni elementari. Prodotto scalare, combinazione lineare, affine, conica e convessa. Chiusura rispetto alle operazioni di combinazione. Dipendenza e indipendenza lineare e affine. Semispazi chiusi, poliedri e loro rappresentazione algebrica. Sistemi di disequazioni lineari e loro soluzione. Teorema e metodo di Fourier-Motzkin. Basi per un insieme di vettori. Teorema di rappresentazione.

Teorema di sostituzione (Steinitz).

Problemi combinatorici e di ottimizzazione combinatoria

Algoritmo universale e sua complessità. Problemi subclusivi, superclusivi, né subclusivi né superclusivi. Esempi: zaino, edge-cover, insieme stabile, albero ricoprente, matching (perfetto). Algoritmo ingordo: pseudocodifica per problemi subclusivi e superclusivi. Ammissibilità della soluzione. Proprietà di scambio e sue implicazioni sulla cardinalità degli insiemi massimali. Convergenza dell'algoritmo ingordo a una soluzione ottima. Teorema di Rado, matroidi. Matroide banale, matroide grafico;

assegnamenti e matroide partizione. Matroide vettoriale.

Modelli di programmazione lineare e lineare intera

Riformulazione di problemi di ottimizzazione combinatoria in termini di programmazione lineare 0-1. Esempi: clique, insieme stabile, node-cover, colorazione, problemi dell’(s, t)-cammino minimo e del commesso viaggiatore e loro riformulazione in termini di programmazione lineare 0-1. Problemi di programmazione lineare.

Esempi: problema della dieta, ottimizzazione di un processo di produzione, problemi max-min e giochi a somma zero, gestione ottima di un portafoglio di titoli , ottimizzazione di un palinsesto televisivo.

Teoria della dualità e teoremi dell'alternativa

Teorema di Gale, Lemma di Fàrkas, esempi. Teorema di dualità forte. Duale di un problema di PL in forma standard. Proprietà del problema duale: reciprocità e dominanza. Condizioni di ottimalità primale e duale, ortogonalità. Costruzione del duale di un problema di PL generico. Formulazione del duale di un problema di PL.

Interpretazione del problema duale. Prezzo implicito delle risorse. Aspetti geometrici della programmazione lineare. Direzioni di un poliedro: cono di recessione e sue proprietà. Teorema di Weyl (enunciato). Esempi. Teorema fondamentale della programmazione lineare.

Il metodo del simplesso

Basi e soluzioni (ammissibili) di base; problemi equivalenti; forma e tabella canonica;

criteri di ottimalità e illimitatezza. Fase II del metodo del simplesso: tabella canonica e operazione di pivot, miglioramento della base corrente. Fase I del metodo del simplesso: calcolo della prima base tramite problema ausiliario. Applicazioni alla

(2)

programmazione lineare intera: rilassamento lineare, calcolo di limitazioni inferiori/superiori tramite simplesso, cenni sui metodi di branch-and-bound.

Riferimenti

Documenti correlati

[r]

2.5 Dimostrare che aggiungendo un arco di A ad un albero ricoprente di G(N,A), si genera un sottografo di G(N,A) contenente

• Inizialmente vengono ordinati gli archi e definita una particolare soluzione duale iniziale y 0 che non è ammissibile ma è facile da scrivere. • A ogni iterazione gli archi

Determinare l'ampiezza dell'angolo al centro del settore circolare in modo che il cono abbia

Durante l'anno scolastico 2005-2006 insegnavo nella classe 5F del Liceo Scientifico Statale “Leonardo da Vinci” di Reggio Calabria, e nel mese di Aprile tre miei studenti :

“Sia ABCD un trapezio isoscele di area S^2 e con angoli adiacenti alla base di 45°. Determina l'altezza del trapezio in modo che abbia

Per stabilire se `e possibile chiudere qualche problema `e necessario individuare una soluzione ammissi- bile per il problema (11.1.2) e quindi il valore dell’ottimo corrente

• operazione di bound: valutazione ottimistica della funzione obiettivo per le soluzioni rappresentate da ciascun nodo (bound ), per evitare lo sviluppo completo di sotto-