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 complet K12 a-t-il ?

K12
|E| =
2.Facile
AABBCCDD0001001001011010

La matrice d’adjacence d’un graphe simple non orienté est représentée. Trouvez le degré deg(B) du sommet B.

deg(B) =
3.Moyen
ABCDECircuit 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| = 5|E| = 5
  1. 1Circuit eulérien
  2. 2Chemin eulérien, pas de circuit
  3. 3ni l’une ni l’autre
4.Moyen

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

|V| = 11|E| = 21
k =
5.Difficile
9615784102ABCDEF

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

départ : Dk = 3
  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 BE
6.Difficile
1511313127102ABCDEF

L’algorithme de Dijkstra part de A. Cliquez sur le sommet qui est fixé (rendu définitif) au tour 3 ; A lui-même est le tour 1.

départ : Atour 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F

Corrigé

  1. 1. |E| = 66
  2. 2. deg(B) = 1
  3. 3. Circuit eulérien
  4. 4. k = 11
  5. 5. arête BE
  6. 6. E

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