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.
Ce graphe est d'ordre 6.
Le degré d'un sommet est égal au nombre d'arêtes dont ce sommet est une extrémité.
Les degrés des différents sommets sont donnés dans le tableau ci-dessous:
Sommets | 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 ? 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.
Quatre sommets sont de degré impair donc il n'existe pas de chaîne eulérienne dans ce graphe.
Un piéton ne peut pas parcourir toutes ces avenues sans emprunter plusieurs fois la même avenue.
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é .
Les sommets étant classés dans l'ordre alphabétique, la matrice associée à ce graphe est
Quel est le nombre de trajets de longueur 2 reliant D à B ?
Il y a deux trajets de longueur 2 reliant D à B. Les trajets D-A-B et D-C-B.
Comment pourrait-on obtenir ce résultat uniquement par le calcul à partir de la matrice M ?
Le terme situé à l'intersection de la quatrième ligne et de la deuxième colonne de la matrice , donne le nombre de chaînes de longueur 2 reliant le sommet D au sommet B .
donc il y a deux trajets de longueur 2 reliant D à B.
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.