1.Facile
Exactement un sommet du graphe a pour degré 1. Cliquez dessus.
deg = 1
- 1A
- 2B
- 3C
- 4D
- 5E
- 6F
- 7G
Fiche d’exercices de Théorie des graphes avec corrigé
2.Facile
Un graphe simple a 5 sommets de degrés 3, 3, 2, 2, 2. Combien d’arêtes |E| a-t-il ?
deg: 3, 3, 2, 2, 2
|E| =
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| = 5|E| = 6
- 1Circuit eulérien
- 2Chemin eulérien, pas de circuit
- 3ni l’une ni l’autre
4.Moyen
Un arbre a 2 sommets de degré 3, et tous ses autres sommets sont des feuilles (degré 1). Combien de feuilles L a-t-il ?
2 × deg 3
L =
5.Difficile
L’algorithme de Prim construit un arbre couvrant minimal en partant du sommet B. Cliquez sur l’arête qu’il ajoute en numéro 3.
départ : Bk = 3
- 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 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
- 1arête AB
- 2arête BC
- 3arête BD
- 4arête CE
- 5arête EF
- 6arête GB
- 7arête GC
- 8arête GD
- 9arête GE
Corrigé
- 1. F
- 2. |E| = 6
- 3. Circuit eulérien
- 4. L = 4
- 5. arête BC
- 6. arête BD
Corrigés complets pas à pas : entraînez-vous sur ce thème sur examproblems.com.