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
AABBCCDDEEFF010000101100010010010001001001000110

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| =
2.Facile
ABCDEFG

Trouvez la somme des degrés de tous les sommets du graphe représenté, Σ deg.

|V| = 7
Σ deg =
3.Moyen

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

3 × deg 34 × deg 44 × deg 5
L =
4.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| = 8
  1. 1Circuit eulérien
  2. 2Chemin eulérien, pas de circuit
  3. 3ni l’une ni l’autre
5.Difficile
714513126119ABCDEF

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
6.Difficile
18192014121045ABCDEF

Trouvez le poids total W d’un arbre couvrant minimal du graphe pondéré.

|V| = 6|E| = 8
W =

Corrigé

  1. 1. |E| = 6
  2. 2. Σ deg = 20
  3. 3. L = 25
  4. 4. ni l’une ni l’autre
  5. 5. D
  6. 6. W = 49

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