Introduzione ai Grafi

False (B)

Le estremità del grafo devono avere un numero pari di archi.

<p>{coppie di persone che si sono strette la mano} o {(x, y) tale che x ha inviato una mail a y}</p> Signup and view all the answers

<p>Vertici = Punti nel grafo dove gli archi si incontrano Archivi = Collegamenti tra i vertici Grafo = Rappresentazione delle relazioni Multigrafo = Grafo con più archi tra le stesse coppie di vertici</p> Signup and view all the answers

<p>1736 (A)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>Che non è possibile partire da un vertice e ritornare attraversando ogni ponte esattamente una volta.</p> Signup and view all the answers

<p>W : E → R (A)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>In un grafo non orientato, gli archi non hanno una direzione. (A), In un grafo orientato, gli archi hanno una direzione. (B)</p> Signup and view all the answers

<p>Un peso infinito</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>peso</p> Signup and view all the answers

<p>(A, D) e (D, A)</p> Signup and view all the answers

<p>(A, B) = 3 (D, E) = -2.3 (C, F) = ∞ (A, D) = 1.2</p> Signup and view all the answers

<p>non ordinate</p> Signup and view all the answers

<p>Un sottografo H deve avere V* ⊆ V. (A)</p> Signup and view all the answers

<p>Grafo orientato = Coppie ordinate Grafo non orientato = Coppie non ordinate Arco = Connessione tra due vertici Vertice = Punto in un grafo</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>Un vertice x è adiacente a y se (y, x) ∈ E (B)</p> Signup and view all the answers

<p>{A, C, D, E}</p> Signup and view all the answers

<p>Ogni arco in un grafo è unico e può apparire solo una volta. (B), Di solito gli archi in un grafo non orientato non possono essere duplicati. (C)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>{A, B, C, D, E, F}</p> Signup and view all the answers

<p>A e C</p> Signup and view all the answers

<p>alcun</p> Signup and view all the answers

<p>(A, B) = A è adiacente a B (B, D) = B è adiacente a D (C, E) = C è adiacente a E (D, A) = D è adiacente a A</p> Signup and view all the answers

<p>C è adiacente a B, D e E (C)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>Sì, C è adiacente a D.</p> Signup and view all the answers

<p>È aciclico (C)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>Indica quali nodi sono connessi tra loro.</p> Signup and view all the answers

<p>0</p> Signup and view all the answers

<p>Foresta = Grafo aciclico non necessariamente connesso Albero = Foresta connessa Matrice di adiacenza = Rappresentazione dei collegamenti tra nodi Graficato non orientato = Grafo senza direzione sugli archi</p> Signup and view all the answers

<p>Due (B)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>Un albero è connesso, mentre una foresta può non esserlo.</p> Signup and view all the answers

<p>foresta</p> Signup and view all the answers

<p>Gli archi non hanno direzione (D)</p> Signup and view all the answers

<p>Una lista di nodi e dei loro archi (B)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>M(x, y) = W(x, y)</p> Signup and view all the answers

<p>x</p> Signup and view all the answers

<p>Grafo orientato = Gli archi hanno un verso definito Grafo pesato = Gli archi hanno un peso associato Lista di adiacenza = Rappresentazione efficace per grafo sparso Matrice di adiacenza = Rappresentazione efficace per grafo denso</p> Signup and view all the answers

<p>La matrice è quadrata e riflette le connessioni tra vertici (B)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>Il peso dell'arco</p> Signup and view all the answers

<p>1.2</p> Signup and view all the answers

<p>Matrice di adiacenza (C)</p> Signup and view all the answers

Un insieme di nodi (vertici), che rappresentano gli oggetti in questione, e un insieme di archi (spigoli), che rappresentano la relazione tra due nodi.

Un grafo in cui ogni coppia di nodi è collegata da al massimo un arco.

Un grafo in cui ogni coppia di nodi è collegata da uno o più archi.

Un grafo in cui è specificata una direzione per ogni arco.

Un grafo in cui gli archi hanno un peso associato.

Un grafo in cui gli archi non hanno una direzione.

Un percorso che passa esattamente una volta per ogni arco del grafo.

Un cammino euleriano che inizia e termina nello stesso nodo.

In un grafo orientato, un arco (x, y) "parte" dal nodo x e "arriva" al nodo y.

In un grafo orientato, due nodi sono adiacenti se esiste un arco che li collega direttamente.

Un arco (x, y) è incidente da x in y se parte dal nodo x e arriva al nodo y.

Un arco (x, y) è incidente in y se "arriva" al nodo y.

Il nodo x è adiacente al nodo y se esiste un arco che parte dal nodo x e arriva al nodo y.

In un grafo orientato, un arco che "parte" dal nodo x e "arriva" al nodo y è incidente da x in y.

In un grafo orientato, un arco che "arriva" al nodo y è incidente in y.

Un nodo è adiacente ad un altro nodo se esiste un arco che li collega direttamente.

Un grafo in cui gli archi non hanno una direzione specifica. Ad esempio, l'arco tra A e B è lo stesso arco tra B e A.

Un grafo in cui gli archi hanno una direzione specifica. Ad esempio, l'arco da A a B è diverso dall'arco da B a A.

Un insieme di nodi in un grafo.

Un insieme di archi in un grafo.

Una rappresentazione di un grafo attraverso un insieme di coppie ordinate (nodo iniziale, nodo finale).

Una rappresentazione di un grafo attraverso un insieme di coppie non ordinate (nodo1, nodo2).

Relazione tra coppie ordinate. Implica un ordine specifico tra gli elementi.

Relazione tra coppie non ordinate. L'ordine degli elementi non è significativo.

Un grafo che contiene un sottoinsieme di nodi e archi del grafo originale. I nodi del sottografo devono essere contenuti nel grafo originale, e gli archi del sottografo devono connettere solo nodi che sono presenti nel sottografo.

La funzione che associa un peso reale ad ogni arco del grafo pesato.

Un numero infinito. In un grafo pesato, un peso infinito indica che non esiste un percorso tra i due nodi corrispondenti all'arco.

Un gruppo di nodi e archi che formano una struttura connessa all'interno di un grafo più grande.

Il nodo iniziale e finale coincidono, formando un percorso chiuso.

Una struttura dati che rappresenta un grafo usando una lista di adiacenza per ogni vertice. Ogni lista contiene i vertici adiacenti a quel vertice.

Una rappresentazione di un grafo usando una matrice in cui ogni elemento rappresenta il peso dell'arco tra due vertici.

Il peso dell'arco tra i vertici x e y.

Un metodo per rappresentare un grafo, dove ad ogni vertice x è associata la lista L(x) di tutti i vertici y a cui x è direttamente connesso.

Il peso dell'arco tra i vertici x e y nella matrice di adiacenza.

Un collegamento diretto tra due vertici in un grafo.

Un nodo in un grafo.

Un grafo in cui è possibile passare da un qualsiasi vertice a un qualsiasi altro vertice tramite una sequenza di archi

Una foresta è un grafo non orientato aciclico, cioè senza cicli. Una foresta può essere composta da uno o più alberi.

Un albero è un grafo non orientato connesso che non contiene cicli.

Un grafo aciclico è un grafo che non contiene cicli. Un ciclo è un percorso che inizia e termina nello stesso nodo, attraversando tutti i nodi almeno una volta.

La rappresentazione matriciale M(x, y) di un grafo non orientato mostra la presenza o l'assenza di un arco tra i nodi x e y. Se un arco esiste, la cella M(x, y) avrà valore 1, altrimenti sarà 0.

Gli algoritmi e le strutture dati sono strumenti fondamentali nell'informatica. Gli algoritmi sono sequenze di istruzioni ben definite che risolvono un problema, mentre le strutture dati sono modi di organizzare i dati per permettere un accesso efficiente.

Ugo de'Liguoro e András Horváth sono due autori di un libro di testo sul tema degli algoritmi e delle strutture dati.

Le pagine indicate nel testo indicano la sezione specifica del libro di testo dove si trova l'argomento in questione.