DEVOIR SURVEILLE N°2
Exercice n°1 : 4 points
On considère le graphe ci-contre:
1) Donner le degré de chaque sommet et en déduire le nombre d’arètes.
2) a) Démontrer que ce graphe est connexe.
b) Est-il complet? Justifier.
3) a) Quelle est la distance entre les sommets
1 et 3?
1 et 4?
b) Quel est le diamètre de ce graphe? Justifier
4) a) Existe-t-il un cycle eulérien? Justifier.
Si oui, en citer un.
b) Existe-t-il une chaine eulérienne? Justifier. Si oui, en citer une.
Exercice
n°2 : 4 points
Il a été décidé de placer des caméras au-dessus de certaines portes de façon à balayer les deux salles communiquant par cette porte.
Chercher le nombre de caméras minimal à utiliser, tout en surveillant toutes les salles.
Exercice n°3 : 4 points
On donne le graphe ci-contre.
1) Donner la matrice M associée à ce graphe. (on prendra les sommets dans l’ordre alphabétique).
2) a) Calculer A3.
b) Combien y a-t-il de chaînes de longueur 3 qui partent de A ?
c) Combien y a-t-il de chaînes de longueur 3 qui arrivent à F.
3) Sans calculer M4, indiquer la valeur de son
coefficient 
.
Nommer tous les chemins correspondant.
Exercice n°4 : 5 points
Stéphane doit finir son aventure: il doit arriver devant le seigneur Johan-Klod'h pour délivrer sa fiancée en la payant avec 3 écailles volées à trois dragons différents.
Pour charmer le dragon blanc, il doit trouver un violon d'or, un musicien capable d'en jouer et la partition d'Endil.
Pour combattre le dragon rouge, il doit trouver une afnlure de mithril, l' épée Excalibur et une fiole de résistance au feu. Enfin, pour endormir le dragon vert, il doit récupérer un bâton de sommeil, un anneau d'invisibilité et une cape de silence.
Tout semble donc très facile, mais s'il se présente devant le dragon blanc avec la fiole ou le bâton, celui-ci soufflera du froid et le gel les éclatera. Il ne peut se présenter devant le dragon rouge avec la partition ou la cape car il lui suffira de souffler du feu pour brûler ces objets.
Enfin si le dragon vert crache de l' acide sur le musicien ou l'armure de mithril, Stéphane devra en trouver d'autres ...
Finalement, s'il va voir le seigneur Johan-Klod'h sans les trois écailles, ce traître lui dérobera tous ,ces objets et l'enverra dans ses mines de sel.
1) Indiquer en rouge sur un graphe toutes les incompatibilités.
2) Sur ce graphe, indiquer en bleu une chaîne permettant de finir le jeu.
3) Représenter en vert une chaîne lui permettant d'avoir le maximum d'objets avant d'être confronté à chaque dragon.
Exercice n°5 : 3 points Le combat pour les anneaux.
Les trolls veulent attaquer les elfes qui détiennent les trois anneaux du Pouvoir. Un groupe d’elfes a pour ordre de détruire le minimum de ponts pour empêcher l’invasion.
En s’aidant d’un graphe, indiquer combien de ponts il suffit de détruire et lesquels.
Pour
contacter le webmaster 
.
Pour signer le
livre d'or .
Problème
de résolution des exercices ? allez sur le Forum.