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

Un graphe simple a 7 sommets de degrés 4, 3, 3, 3, 3, 2, 2. Combien d’arêtes |E| a-t-il ?

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

Une forêt (un graphe sans cycle) a 40 sommets et 2 composantes connexes. Combien d’arêtes |E| a-t-elle ?

|V| = 40c = 2
|E| =
3.Moyen

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

|V| = 17|E| = 25
k =
4.Moyen

Un arbre a 2 sommets de degré 3, 3 sommets de degré 4, 2 sommets de degré 5, 4 sommets de degré 2, et tous ses autres sommets sont des feuilles (degré 1). Combien de feuilles L a-t-il ?

2 × deg 33 × deg 42 × deg 54 × deg 2
L =
5.Difficile
101253913277ABCDEF

L’algorithme de Dijkstra part de A. Cliquez sur le sommet qui est fixé (rendu définitif) au tour 4 ; A lui-même est le tour 1.

départ : Atour 4
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
6.Difficile
191413120177316418ABCDEFG

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 5.

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

Corrigé

  1. 1. |E| = 10
  2. 2. |E| = 38
  3. 3. k = 9
  4. 4. L = 16
  5. 5. D
  6. 6. arête GC

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