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

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

|V| = 5
Σ deg =
2.Facile
ABCDE

Exactement un sommet du graphe a pour degré 1. Cliquez dessus.

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

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

|V| = 14|E| = 18
k =
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| = 6
  1. 1Circuit eulérien
  2. 2Chemin eulérien, pas de circuit
  3. 3ni l’une ni l’autre
5.Difficile
2816151014127317ABCDEFG

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

|V| = 7|E| = 10
W =
6.Difficile
817217419620105ABCDEFG

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. Σ deg = 12
  2. 2. A
  3. 3. k = 5
  4. 4. Chemin eulérien, pas de circuit
  5. 5. W = 48
  6. 6. arête GE

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