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
AABBCCDDEEFF011000101000110010000010001101000010

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
AABBCCDDEE0110010011100000100101010

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

deg(E) =
3.Moyen

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

2 × deg 34 × deg 52 × deg 2
L =
4.Moyen

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

|V| = 7|E| = 16
k =
5.Difficile
31615107812ABCDEF

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

départ : Fk = 4
  1. 1arête AB
  2. 2arête AC
  3. 3arête BC
  4. 4arête BD
  5. 5arête CE
  6. 6arête DE
  7. 7arête DF
  8. 8arête BE
6.Difficile
ABCDE

Combien de marches fermées de longueur 2 partent de E et y reviennent ? Une marche peut répéter des sommets et des arêtes. Appelez ce nombre N.

M = matrice d’adjacenceL = 2
N =

Corrigé

  1. 1. |E| = 6
  2. 2. deg(E) = 2
  3. 3. L = 16
  4. 4. k = 10
  5. 5. arête AC
  6. 6. N = 3

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