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 albero ha 32 lati. Quanti vertici |V| ha?

|E| = 32
|V| =
2.Facile

Una foresta (un grafo senza cicli) ha 21 vertici e 2 componenti connesse. Quanti lati |E| ha?

|V| = 21c = 2
|E| =
3.Media
ABCDEFGCircuito 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| = 7|E| = 9
  1. 1Circuito euleriano
  2. 2Cammino euleriano, nessun circuito
  3. 3nessuna delle due
4.Media

Un albero ha 4 vertici di grado 3, 3 vertici di grado 4, 2 vertici di grado 2, e tutti gli altri suoi vertici sono foglie (grado 1). Quante foglie L ha?

4 × deg 33 × deg 42 × deg 2
L =
5.Difficile
68391281559ABCDEFG

L’algoritmo di Dijkstra parte da A. Clicca il vertice che viene fissato (reso permanente) al passo 3; A stesso è il passo 1.

partenza: Apasso 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G
6.Difficile
620871021918415ABCDEFG

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

k = 4
  1. 1lato AB
  2. 2lato AC
  3. 3lato BD
  4. 4lato CE
  5. 5lato DE
  6. 6lato EF
  7. 7lato GB
  8. 8lato GC
  9. 9lato GD
  10. 10lato GE

Soluzioni

  1. 1. |V| = 33
  2. 2. |E| = 19
  3. 3. Cammino euleriano, nessun circuito
  4. 4. L = 12
  5. 5. D
  6. 6. lato CE

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