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
ABCDE

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

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

La matrice d’adjacence d’un graphe simple non orienté est représentée. Combien d’arêtes |E| le graphe a-t-il ?

|E| =
3.Moyen

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

|V| = 9|E| = 14
k =
4.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| = 11
  1. 1Circuit eulérien
  2. 2Chemin eulérien, pas de circuit
  3. 3ni l’une ni l’autre
5.Difficile
71495139152ABCDEF

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

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

Utilisez l’algorithme de Dijkstra pour trouver la longueur d(D) du plus court chemin de A à D dans le graphe pondéré.

départ : Aarrivée : D
d(D) =

Corrigé

  1. 1. E
  2. 2. |E| = 3
  3. 3. k = 6
  4. 4. Chemin eulérien, pas de circuit
  5. 5. D
  6. 6. d(D) = 18

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