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 31 vertici. Quanti lati |E| ha?

|V| = 31
|E| =
2.Facile
ABCDE

Esattamente un vertice del grafo ha grado 3. Cliccalo.

deg = 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
3.Media

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

4 × deg 33 × deg 44 × deg 2
L =
4.Media

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

|V| = 16|E| = 20
k =
5.Difficile
2471417191883ABCDEFG

L’algoritmo di Prim costruisce un albero di copertura minimo a partire dal vertice C. Clicca il lato che aggiunge come lato numero 5.

partenza: Ck = 5
  1. 1lato AB
  2. 2lato AC
  3. 3lato BC
  4. 4lato BD
  5. 5lato DE
  6. 6lato EF
  7. 7lato GB
  8. 8lato GC
  9. 9lato GD
6.Difficile
3472512104ABCDEF

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

partenza: Apasso 4
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F

Soluzioni

  1. 1. |E| = 30
  2. 2. C
  3. 3. L = 12
  4. 4. k = 5
  5. 5. lato DE
  6. 6. D

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