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
AABBCCDD0111100010011010

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

deg(D) =
2.Facile

Combien d’arêtes |E| le graphe complet K12 a-t-il ?

K12
|E| =
3.Moyen

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

K8
H =
4.Moyen

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

K4
H =
5.Difficile
201416139181225ABCDEFG

L’algorithme de Kruskal construit un arbre couvrant minimal. Cliquez sur l’arête qu’il ajoute en numéro 6 ; les arêtes sautées ne comptent pas.

k = 6
  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 GB
  9. 9arête GE
6.Difficile
53113141112213ABCDEFG

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

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

Corrigé

  1. 1. deg(D) = 2
  2. 2. |E| = 66
  3. 3. H = 2520
  4. 4. H = 3
  5. 5. arête AC
  6. 6. d(F) = 9

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