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

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

K4,9
|E| =
2.Facile

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

deg: 3, 2, 2, 2, 2, 2, 1
|E| =
3.Moyen
ABCDEFCircuit 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| = 6|E| = 6
  1. 1Circuit eulérien
  2. 2Chemin eulérien, pas de circuit
  3. 3ni l’une ni l’autre
4.Moyen

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

4 × deg 32 × deg 5
L =
5.Difficile
1961612145151813820ABCDEFG

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

départ : Ck = 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 GD
  11. 11arête GE
6.Difficile
9512463410101ABCDEFG

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

Corrigé

  1. 1. |E| = 36
  2. 2. |E| = 7
  3. 3. ni l’une ni l’autre
  4. 4. L = 12
  5. 5. arête AC
  6. 6. E

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