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é 2. Cliquez dessus.

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

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

K5
|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
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| = 12
  1. 1Circuit eulérien
  2. 2Chemin eulérien, pas de circuit
  3. 3ni l’une ni l’autre
5.Difficile
67211179414812ABCDEFG

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

départ : Ck = 2
  1. 1arête AB
  2. 2arête BC
  3. 3arête BD
  4. 4arête CE
  5. 5arête DF
  6. 6arête EF
  7. 7arête GB
  8. 8arête GC
  9. 9arête GD
  10. 10arête GE
6.Difficile
ABCDE

Combien de marches de longueur 3 vont de E à A ? Une marche peut répéter des sommets et des arêtes. Appelez ce nombre N.

M = matrice d’adjacenceL = 3
N =

Corrigé

  1. 1. E
  2. 2. |E| = 10
  3. 3. H = 12
  4. 4. Circuit eulérien
  5. 5. arête BD
  6. 6. N = 2

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