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.
Donner l'ordre du graphe puis le degré de chacun des sommets.
Il y a 6 sommets donc le graphe est d'odre 6. Les degrés des sommets sont :
Sommet du graphe 𝒢 | A | B | C | D | E | F |
Degré | 4 | 3 | 4 | 3 | 3 | 3 |
Un piéton peut-il parcourir toutes ces avenues sans emprunter plusieurs fois la même avenue :
en partant d'un carrefour et en revenant à son point de départ ? Justifier la réponse.
Il y a 4 sommets de degré impair donc il n'existe pas de cycle eulérien. Par conséquent :
un piéton ne peut pas parcourir toutes ces avenues sans emprunter plusieurs fois la même avenue en partant d'un carrefour et en revenant à son point de départ.
en partant d'un carrefour et en arrivant à un carrefour différent ? Justifier la réponse.
Il y a 4 sommets de degré impair donc il n'existe pas de chaîne eulérienne. Par conséquent :
un piéton ne peut pas parcourir toutes ces avenues sans emprunter plusieurs fois la même avenue en partant d'un carrefour et en arrivant à un carrefour différent.
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.
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.
Dans le graphe orienté, il n'existe qu'un seul circuit d'origine D c'est le cicuit D - A - E - D donc :
il n'xiste pas de trajet de longueur quelconque qui permet d'aller de D à B en respectant les sens de circulation.
Écrire la matrice M associée à ce graphe (on rangera les sommets dans l'ordre alphabétique)
On donne la matrice
Que représentent les coefficients de cette matrice ?
Le coefficient situé à l'intersection de la i-ième ligne et j-ième colonne de la matrice donne le nombre de circuits orientés de longueur 3 partant du carrefour i et arrivant au carrefour j.
Combien y-a-t-il de chemins de longueur 3 partant du carrefour B et arrivant en A ?
Écrire tous ces chemins.
Le coefficient situé à l'intersection de la deuxième ligne et de la première colonne de la matrice est égal à 3 donc :
il y a trois de chemins de longueur 3 partant du carrefour B et arrivant en A : B - C - B - A ; B - C - D - A et B - F - C - A.
Combien y-a-t-il de chemins de longueur 3 arrivant au point E ? Expliquer la démarche.
Le nombre de chemins de longueur 3 arrivant au point E est égal à la somme des coefficients de la cinquième colonne de la matrice .
Il y a six de chemins de longueur 3 arrivant au point E.
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.