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 grafo semplice ha 7 vertici con gradi 4, 3, 3, 3, 2, 2, 1. Quanti lati |E| ha?

deg: 4, 3, 3, 3, 2, 2, 1
|E| =
2.Facile
AABBCCDDEEFF011000101110110010010011011101000110

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

|E| =
3.Media

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

K8
H =
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
1011128571317ABCDEF

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 AB
  2. 2lato AC
  3. 3lato BC
  4. 4lato BD
  5. 5lato CE
  6. 6lato DE
  7. 7lato EF
  8. 8lato BE
6.Difficile
8510132123ABCDE

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

partenza: Ek = 2
  1. 1lato AB
  2. 2lato AC
  3. 3lato BC
  4. 4lato BD
  5. 5lato CE
  6. 6lato DE
  7. 7lato BE

Soluzioni

  1. 1. |E| = 9
  2. 2. |E| = 9
  3. 3. H = 2520
  4. 4. H = 3
  5. 5. lato EF
  6. 6. lato BE

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