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

Un arbre a 7 arêtes. Combien de sommets |V| a-t-il ?

|E| = 7
|V| =
2.Facile
AABBCCDD0110101011010010

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

deg(B) =
3.Moyen

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

K7
H =
4.Moyen

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

3 × deg 33 × deg 4
L =
5.Difficile
ABCDEF

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

M = matrice d’adjacenceL = 2
N =
6.Difficile
11654210817201914ABCDEFG

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

k = 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 EF
  9. 9arête GB
  10. 10arête GC
  11. 11arête GE

Corrigé

  1. 1. |V| = 8
  2. 2. deg(B) = 2
  3. 3. H = 360
  4. 4. L = 11
  5. 5. N = 1
  6. 6. arête AC

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