Éric SOPENA - avril 2002 Éléments de théorie des graphes - Quelques exercices d'application (avec solutions) page 1 ÉLÉMENTS DE THÉORIE DES GRAPHES QUELQUES EXERCICES D'APPLICATION (AVEC SOLUTIONS) Le but principal de cette série d'exercices et de servir de « source d'inspiration ». Bon nombre de ces exercices peuvent être à l'origine de toute une « famille » d'exercices que l'enseignant n'aura aucun mal à « générer »… Les exercices (ou questions) sont classés par niveau de difficulté : (o) facile (oo) assez facile (ooo) difficile Il est possible que certaines des solutions comportent des erreurs, de frappe ou d'inattention… Merci au lecteur attentif de me les signaler… 1. NOTIONS DE BASE 1.1. Modélisation Exercice 1. (o) Construire un graphe orienté dont les sommets sont les entiers compris entre 1 et 12 et dont les arcs représentent la relation « être diviseur de ». Solution Exercice 1. Aucune difficulté particulière (ne pas oublier les boucles)… 1 2 3 4 5 6 7 8 9 10 11 12 Exercice 2. (oo) Une chèvre, un chou et un loup se trouvent sur la rive d'un fleuve ; un passeur souhaite les transporter sur l'autre rive mais, sa barque étant trop petite, il ne peut transporter qu'un seul d'entre eux à la fois.
- fois des couples donnant le contenu du récipient
- composante connexe du sommet d'arrivée
- parcours du cavalier
- couple