grafi e reti di flusso (generale) Flashcards
Cosa è una rete?
Con il termine rete indichiamo un grafo G = (N, A) pesato, cioè ai cui nodi e/o archi sono associati dei valori numerici detti pesi.
Cosa vuol dire se il bilancio di un nodo è positivo?
Il bilancio rappresenta la quantità del bene che esce dalla rete al nodo i. E’ quindi detto domanda del nodo, e il nodo viene detto destinazione o pozzo.
Cosa vuol dire se il bilancio di un nodo è negativo?
Rappresenta la quantità di bene che entra nella rete al nodo i. bi viene detto offerta del nodo, ed il nodo viene detto sorgente, o origine.
Cosa vuol dire se bi di un nodo è nullo?
Vuol dire che i è un nodo di trasferimento.
Nei problemi di flusso, la domanda globale è uguale all’offerta globale, questo significa che…
La somma dei bi di tutti i nodi dev’essere uguale a zero, e la somma dei nodi di bilancio negativo dev’essere uguale a meno la somma dei nodi di bilancio positivo.
Quali sono gli elementi di un algoritmo di visita?
La procedura di visita riceve in input il grafo orientato e un nodo origine, la radice r, e determina i nodi raggiungibili da r per mezzo di cammini orientati. Tali cammini individuano un albero che viene fornito attraverso il vettore predecessore.
Qual è la complessità dell’algoritmo di visita?
E’ limitato superiormente dal numero di archi perché non si visita più di un nodo alla volta.
L’implementazione di Q, insieme dei nodi da esaminare, come fila (queue), (FIFO), crea una procedura di visita…
BFS, Breadth-first search, In ampiezza, a ventaglio.
L’implementazione di Q, insieme dei nodi da visitare come pila (stack) (LIFO), rende una procedura di visita…
DFS, depth first search, a scandaglio, in profondità.
Le procedure di visita in ampiezza e in profondità creano alberi diversi.
VERO.
La procedura di visita in cui Q è implementato come fila (FIFO) determina, per ogni nodo i raggiungibile da r…
Un cammino orientato da r a i di lunghezza minima in termini di numero di archi.
