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 arbre a 38 arêtes. Combien de sommets |V| a-t-il ?

|E| = 38
|V| =
2.Facile

Combien d’arêtes |E| le graphe complet K11 a-t-il ?

K11
|E| =
3.Moyen

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

3 × deg 44 × deg 2
L =
4.Moyen

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

|V| = 11|E| = 19
k =
5.Difficile
8207111261410ABCDEFG

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

départ : Fk = 2
  1. 1arête AB
  2. 2arête AC
  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
6.Difficile
111414119151161ABCDEFG

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. |V| = 39
  2. 2. |E| = 55
  3. 3. L = 8
  4. 4. k = 9
  5. 5. arête DF
  6. 6. d(F) = 23

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