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 fiche S’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

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

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

deg = 1

3.Moyen

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

1Circuit eulérien
2Chemin eulérien, pas de circuit
3ni l’une ni l’autre

4.Moyen

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

K₄

H =

5.Difficile

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

départ : Ek = 2

1arête AB
2arête AC
3arête BC
4arête BD
5arête CE
6arête DE
7arête BE

6.Difficile

L’algorithme de Dijkstra part de A. Cliquez sur le sommet qui est fixé (rendu définitif) au tour 3 ; A lui-même est le tour 1.

départ : Atour 3

Corrigé

1. deg(D) = 2
2. F
3. Chemin eulérien, pas de circuit
4. H = 3
5. arête AC
6. B

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