Scheda di esercizi di Teoria dei grafi con soluzioni

Scheda di esercizi di Teoria dei grafi gratuita e stampabile: 6 esercizi dal livello facile a quello d’esame, con le soluzioni. Stampala o salvala come PDF.

Nuova schedaEsercitati online con i suggerimenti

Per i docenti: gratuita da stampare, copiare e usare in classe. Ogni nuova scheda ha nuovi valori e le sue soluzioni. Un link a ExamProblems nella pagina del corso è molto apprezzato.

Nome: ____________________   Data: ____________

1.Facile

Un grafo semplice ha 7 vertici con gradi 3, 3, 3, 2, 2, 2, 1. Quanti lati |E| ha?

deg: 3, 3, 3, 2, 2, 2, 1
|E| =
2.Facile
ABCDEFG

Trova la somma dei gradi di tutti i vertici del grafo mostrato, Σ deg.

|V| = 7
Σ deg =
3.Media

Un grafo connesso ha 16 vertici e 16 lati. Quanti lati k vanno tolti per ottenere un albero di copertura?

|V| = 16|E| = 16
k =
4.Media
ABCDECircuito eulerianoCammino euleriano, nessun circuitonessuna delle due

Il grafo connesso ha un circuito euleriano, un cammino euleriano che non è un circuito, oppure nessuno dei due? Clicca la tua risposta.

|V| = 5|E| = 6
  1. 1Circuito euleriano
  2. 2Cammino euleriano, nessun circuito
  3. 3nessuna delle due
5.Difficile
91981151313102ABCDEFG

L’algoritmo di Kruskal costruisce un albero di copertura minimo. Clicca il lato che aggiunge come lato numero 2; i lati saltati non contano.

k = 2
  1. 1lato AB
  2. 2lato BC
  3. 3lato BD
  4. 4lato CE
  5. 5lato DE
  6. 6lato DF
  7. 7lato EF
  8. 8lato GC
  9. 9lato GD
  10. 10lato GE
6.Difficile
84141291137ABCDEF

Usa l’algoritmo di Dijkstra per trovare la lunghezza d(F) del cammino minimo da A a F nel grafo pesato.

partenza: Aarrivo: F
d(F) =

Soluzioni

  1. 1. |E| = 8
  2. 2. Σ deg = 16
  3. 3. k = 1
  4. 4. Circuito euleriano
  5. 5. lato GE
  6. 6. d(F) = 18

Soluzioni complete passo passo: esercitati su questo argomento su examproblems.com.