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
ABCDEFG

Esattamente un vertice del grafo ha grado 2. Cliccalo.

deg = 2
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G
2.Facile
AABBCCDD0101100000011010

È mostrata la matrice di adiacenza di un grafo semplice non orientato. Quanti lati |E| ha il grafo?

|E| =
3.Media

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

2 × deg 43 × deg 2
L =
4.Media

Quanti cicli hamiltoniani diversi H ha il grafo completo K5? I cicli che differiscono solo per il vertice iniziale o per il verso contano come lo stesso.

K5
H =
5.Difficile
118121215910152ABCDEFG

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) =
6.Difficile
1217155131146720ABCDEFG

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

partenza: Ck = 2
  1. 1lato AC
  2. 2lato BC
  3. 3lato CE
  4. 4lato DE
  5. 5lato DF
  6. 6lato EF
  7. 7lato GB
  8. 8lato GC
  9. 9lato GD
  10. 10lato GE

Soluzioni

  1. 1. F
  2. 2. |E| = 3
  3. 3. L = 6
  4. 4. H = 12
  5. 5. d(F) = 50
  6. 6. lato GB

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