Le graphe suivant représente le plan d'une ville. Les arêtes du graphe représentent ses avenues commerçantes et les sommets du graphe les carrefours de ces avenues.
Donner l'ordre de ce graphe, puis le degré de chacun de ses sommets.
L'ordre d'un graphe est le nombre de ses sommets. Le degré d'un sommet est égal au nombre d'arêtes dont ce sommet est une extrémité.
Un piéton peut-il parcourir toutes ces avenues sans emprunter plusieurs fois la même avenue ? Justifier votre réponse.
Parcourir toutes ces avenues sans emprunter plusieurs fois la même avenue revient à chercher une chaîne eulérienne.Un graphe connexe admet une chaîne eulérienne si et seulement si le nombre de ses sommets de degré impair est 0 ou 2.
Dans le graphe suivant, on a indiqué le sens de circulation dans les différentes avenues.
Écrire la matrice M associée à ce graphe.
(On rangera les sommets dans l'ordre alphabétique).
Dans la matrice associée à un graphe orienté, poser , est équivalent à dire que les sommets et sont reliés par une arête orientée d'origine et d'extremité .
Quel est le nombre de trajets de longueur 2 reliant D à B ?
Comment pourrait-on obtenir ce résultat uniquement par le calcul à partir de la matrice M ?
Le terme situé à l'intersection de la ligne i et de la colonne j de la matrice donne le nombre de chaînes de longueur 2 reliant le sommet au sommet .
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.