Exercice

Partie A

Le graphe suivant représente le plan d’une ville. Les arêtes du graphe représentent les principales avenues et les sommets du graphe les carrefours entre ces avenues.

1 Donner l’ordre du graphe puis le degré de chacun des sommets.

2 Un piéton peut-il parcourir toutes ces avenues sans emprunter plusieurs fois la même avenue :

a. en partant d’un carrefour et en revenant à son point de départ ? Justifier la réponse.

b. en partant d’un carrefour et en arrivant à un carrefour différent ? Justifier la réponse.

Partie B

Dans le graphe ci-dessous, on a indiqué, pour cette même ville, le sens de circulation pour les véhicules sur les différentes avenues.

1 Peut-on trouver un trajet de longueur quelconque qui permet d’aller de D à B en respectant les sens de circulation ? Justifier la réponse.

2 Écrire la matrice M associée à ce graphe (on rangera les sommets dans l’ordre alphabétique).

3 On donne la matrice :

M 3 =( 1 3 1 0 0 3 0 1 1 0 0 0 0 1 1 0 0 1 0 3 2 1 0 0 0 1 3 0 1 1 0 1 0 0 0 1 ).

a. Que représentent les coefficients de cette matrice ?

b. Comment y a-t-il de chemins de longueur 3 partant du carrefour B et arrivant en A ?

Écrire tous ces chemins.

c. Combien y a-t-il de chemins de longueur 3 arrivant au point E ? Expliquer la démarche.