Exercice3 :

Une grande surface est conçue de telle façon que six secteurs notés A, B, C, D, E, F sont reliés par des allées selon le graphe (G) ci-contre.

1) Le graphe est-il connexe ?pourquoi ?

2) Un visiteur désire parcourir l'ensemble des allées en ne passant par celle-ci qu'une seule fois.

Graphe (G)

a- Démontrer que son souhait est réalisable.

b-Donner un exemple d'un tel parcours.

3) Le directeur désire associer chaque secteur à une couleur de sorte que deux secteurs ne portent pas la même couleur.

a- Démontrer que le nombre chromatique (G) du graphe vérifie y(G)≥4.

b- Expliquer pourquoi y(G) ≤5.

c- Proposer un coloriage du graphe permettant de déterminer son nombre chromatique.

4. Une famille se trouve dans le secteur E et doit se rendre dans le secteur F. Cela étant, les parents connaissent