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

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

|V| = 14c = 5
|E| =
2.Facile

Un arbre a 27 sommets. Combien d’arêtes |E| a-t-il ?

|V| = 27
|E| =
3.Moyen
ABCDEFGCircuit eulérienChemin eulérien, pas de circuitni l’une ni l’autre

Le graphe connexe a-t-il un circuit eulérien, un chemin eulérien qui n’est pas un circuit, ou ni l’un ni l’autre ? Cliquez sur votre réponse.

|V| = 7|E| = 10
  1. 1Circuit eulérien
  2. 2Chemin eulérien, pas de circuit
  3. 3ni l’une ni l’autre
4.Moyen

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

2 × deg 32 × deg 44 × deg 52 × deg 2
L =
5.Difficile
420141019313151716ABCDEFG

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

k = 5
  1. 1arête AB
  2. 2arête AC
  3. 3arête BC
  4. 4arête BD
  5. 5arête CE
  6. 6arête DF
  7. 7arête EF
  8. 8arête GB
  9. 9arête GC
  10. 10arête GD
6.Difficile
715988141087ABCDEFG

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. |E| = 9
  2. 2. |E| = 26
  3. 3. Chemin eulérien, pas de circuit
  4. 4. L = 20
  5. 5. arête BC
  6. 6. d(F) = 29

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