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

Exactement un sommet du graphe a pour degré 1. Cliquez dessus.

deg = 1
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
2.Facile

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

deg: 3, 2, 2, 2, 2, 1
|E| =
3.Moyen

Combien de circuits hamiltoniens différents H le graphe complet K5 a-t-il ? Les circuits qui ne diffèrent que par le sommet de départ ou le sens comptent comme un seul.

K5
H =
4.Moyen

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

|V| = 19|E| = 22
k =
5.Difficile
7106216819ABCDE

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

départ : Ek = 2
  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 BE
6.Difficile
8191314161317ABCDEF

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

départ : Ak = 3
  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 EF
  8. 8arête BE

Corrigé

  1. 1. A
  2. 2. |E| = 6
  3. 3. H = 12
  4. 4. k = 4
  5. 5. arête BD
  6. 6. arête BD

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