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
AABBCCDDEE0110010111110010100101110

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

|E| =
2.Facile
ABCDEFG

Esattamente un vertice del grafo ha grado 4. Cliccalo.

deg = 4
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G
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| = 7
  1. 1Circuito euleriano
  2. 2Cammino euleriano, nessun circuito
  3. 3nessuna delle due
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
2051174101811ABCDEF

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

partenza: Fk = 4
  1. 1lato AB
  2. 2lato AC
  3. 3lato BC
  4. 4lato BD
  5. 5lato DE
  6. 6lato DF
  7. 7lato EF
  8. 8lato BE
6.Difficile
671101071115ABCDEF

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| = 7
  2. 2. C
  3. 3. Cammino euleriano, nessun circuito
  4. 4. H = 12
  5. 5. lato BC
  6. 6. d(F) = 23

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