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

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

|V| = 7

Σ deg =

2.Facile

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

deg(F) =

3.Moyen

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

2 × deg 32 × deg 53 × deg 2

L =

4.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| = 5|E| = 6

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

5.Difficile

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

k = 3

1arête AC
2arête BD
3arête CE
4arête DF
5arête EF
6arête GB
7arête GC
8arête GD
9arête GE

6.Difficile

Utilisez l’algorithme de Dijkstra pour trouver la longueur d(F) du plus court chemin de A à F dans le graphe pondéré.

départ : Aarrivée : F

d(F) =

Corrigé

1. Σ deg = 18
2. deg(F) = 1
3. L = 10
4. Circuit eulérien
5. arête GC
6. d(F) = 27

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