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

Quanti lati |E| ha il grafo completo K7?

K7
|E| =
2.Facile

Quanti lati |E| ha il grafo bipartito completo K6,9?

K6,9
|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

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

K4
H =
5.Difficile
794851217162ABCDEFG

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

k = 5
  1. 1lato AC
  2. 2lato BC
  3. 3lato BD
  4. 4lato CE
  5. 5lato DE
  6. 6lato DF
  7. 7lato GB
  8. 8lato GD
  9. 9lato GE
6.Difficile
ABCDE

Quanti cammini di lunghezza 3 vanno da C a D? Un cammino può ripetere vertici e lati. Chiama il numero N.

M = matrice di adiacenzaL = 3
N =

Soluzioni

  1. 1. |E| = 21
  2. 2. |E| = 54
  3. 3. nessuna delle due
  4. 4. H = 3
  5. 5. lato CE
  6. 6. N = 2

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