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
ABCDE

Esattamente un vertice del grafo ha grado 1. Cliccalo.

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

Un grafo 2-regolare ha 4 vertici (ogni vertice ha grado 2). Quanti lati |E| ha?

n = 4k = 2
|E| =
3.Media

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

|V| = 10|E| = 12
k =
4.Media

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

|V| = 12|E| = 21
k =
5.Difficile
20105211128ABCDE

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 BC
  4. 4lato BD
  5. 5lato CE
  6. 6lato DE
  7. 7lato BE
6.Difficile
5311149610410ABCDEFG

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

partenza: Aarrivo: C
d(C) =

Soluzioni

  1. 1. D
  2. 2. |E| = 4
  3. 3. k = 3
  4. 4. k = 10
  5. 5. lato AC
  6. 6. d(C) = 8

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