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
ABCDEF

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

|V| = 6
Σ deg =
2.Facile

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

K4
|E| =
3.Moyen

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

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

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

|V| = 6|E| = 9
k =
5.Difficile
15151535514ABCDEF

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) =
6.Difficile
147192171511102018ABCDEFG

L’algorithme de Kruskal construit un arbre couvrant minimal. Cliquez sur l’arête qu’il ajoute en numéro 4 ; les arêtes sautées ne comptent pas.

k = 4
  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 GB
  9. 9arête GC
  10. 10arête GE

Corrigé

  1. 1. Σ deg = 16
  2. 2. |E| = 6
  3. 3. k = 6
  4. 4. k = 4
  5. 5. d(F) = 14
  6. 6. arête DF

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