Ricerca Operativa - Grafi

38.1. Due archi di un grafo si dicono consecutivi se: hanno un vertice in comune. incidono sulla stessa coppia di vertici. non hanno vertici in comune. se sono separati da un solo arco.

2. Dato il seguente grafo il grado del vertice v1 è. 2. 3. 4. 5.

38.3. Tra i seguenti grafi, risulta essere completo: A. B. C. D.

38.4. Dato il seguente grafo, un suo sottografo parziale è. A. B. C. D.

38.5. Dato il seguente grafo G e la selezione di nodi W={v1,v2,v4,}, il sottografo indotto da W in G è. A. B. C. D.

38.6. Dato il seguente grafo G e gli insiemi di archi H={(v3,v5),(v4,v5)} e L={(v1,v2)}, il grafo G+H-L è. A. B. C. D.

38.7. Da un grafo G=(V,E) un cammino euleriano su G è: una qualsiasi sequenza di archi consecutivi facenti parte del grafo G. un cammino che passa almeno una volta per tutti gli archi di G. un cammino chiuso su G. un cammino che contiene tutti gli archi di G una sola volta.

38.8. Dato un grafo euleriano G=(V,E), possiamo dire che: ogni nodo di G ha grado pari. ogni nodo di G ha grado dispari. i nodi di G possono avere grado sia pari che dispari. in G non sono presenti cicli.

38.9. Tra i seguenti grafi, risulta essere euleriano: A. B. C. D.

38.10. Tra i seguenti grafi, non risulta essere euleriano: A. B. C. D.

39.1. Dato un grafo G, un generico elemento dij della matrice di incidenza nodi-archi è pari a 1 se: l'arco i ha un estremo nel nodo j. l'arco i non ha alcun estremo nel nodo j. l'arco i fa parte del grafo G. se il nodo j è isolato.

39.2. Dato il seguente grafo la matrice di incidenza nodi-archi è. A. B. C. D.

39.3. Dato il seguente grafo il vettore dei gradi dei nodi dG(v) è. A. B. C. D.

39.4. Rispetto al seguente grafo possiamo dire che. è euleriano. diventa euleriano aggiungendo l'arco (v3,v4). diventa euleriano rimuovendo l'arco (v1,v3). diventa euleriano aggiungendo un altro arco (v3,v5).

39.Rispetto al seguente grafo possiamo dire che. diventa euleriano rimuovendo l'arco (v2,v4). è euleriano. diventa euleriano aggiungendo l'arco (v1,v2). diventa euleriano aggiungendo l'arco (v4,v5).

39.6 Dato il seguente grafo, possiamo dire che. e' euleriano ed è dato dall'unione dei cicli disgiunti: C1 = v1, e1, v2, e2, v3, e3, v4, e6, v1 C2 = v5, e8, v2, e7, v4, e4, v5 C3 = v3, e9, v5, e5, v1, e10, v3. e' euleriano ed è dato dall'unione dei cicli disgiunti: C1 = v1, e1, v2, e7, v4, e4, v5, e5, v1 C2 = v2, e2, v3, e3, v4, e7, v2 C3 = v3, e9, v5, e5, v1, e10, v3. e' euleriano ed è dato dall'unione dei seguenti cicli disgiunti: C1 = v1, e10, v3, e2, v2, e1, v1 C2 = v5, e9, v3, e3, v4, e4, v5 C3 = v5, e8, v2, e7, v4, e6, v1, e1, v2, e8, v5. non è euleriano.