Fiche d’exercices de Théorie des graphes avec corrigé

Fiche d’exercices de Théorie des graphes gratuite et imprimable : 6 exercices, du niveau facile au niveau examen, avec corrigé. Imprimez-la ou enregistrez-la en PDF.

Nouvelle ficheS’entraîner en ligne avec indices

Pour les enseignants : gratuite à imprimer, copier et utiliser en classe. Chaque nouvelle fiche a de nouvelles valeurs et son propre corrigé. Un lien vers ExamProblems sur la page de votre cours est apprécié.

Nom: ____________________   Date: ____________

1.Facile
ABCDE

Trouvez la somme des degrés de tous les sommets du graphe représenté, Σ deg.

|V| = 5
Σ deg =
2.Facile
ABCDEF

Exactement un sommet du graphe a pour degré 1. Cliquez dessus.

deg = 1
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
3.Moyen

Un graphe connexe a 6 sommets et 8 arêtes. Combien d’arêtes k faut-il retirer pour obtenir un arbre couvrant ?

|V| = 6|E| = 8
k =
4.Moyen

Combien de circuits hamiltoniens différents H le graphe complet K5 a-t-il ? Les circuits qui ne diffèrent que par le sommet de départ ou le sens comptent comme un seul.

K5
H =
5.Difficile
181451721181916ABCDEFG

L’algorithme de Prim construit un arbre couvrant minimal en partant du sommet B. Cliquez sur l’arête qu’il ajoute en numéro 6.

départ : Bk = 6
  1. 1arête AC
  2. 2arête BC
  3. 3arête BD
  4. 4arête CE
  5. 5arête DE
  6. 6arête DF
  7. 7arête EF
  8. 8arête GB
  9. 9arête GC
  10. 10arête GE
6.Difficile
139251917ABCDEF

Utilisez l’algorithme de Dijkstra pour trouver la longueur d(F) du plus court chemin de A à F dans le graphe pondéré.

départ : Aarrivée : F
d(F) =

Corrigé

  1. 1. Σ deg = 12
  2. 2. F
  3. 3. k = 3
  4. 4. H = 12
  5. 5. arête AC
  6. 6. d(F) = 15

Corrigés complets pas à pas : entraînez-vous sur ce thème sur examproblems.com.