Le graphe ci-dessous, modélise le plan d'un quartier historique d'une ville. Les sommets sont les différents centres d'intérêts et les arêtes les rues.
On appelle M la matrice associée à ce graphe les sommets étant rangés dans l'ordre alphabétique.
On donne deux matrices et .
Une des deux matrices R ou S est la matrice . Sans calculs, indiquer laquelle des deux matrices R ou S est la matrice en justifiant la réponse.
Le terme d'indice de la matrice donne le nombre de chaînes de longueur 4 entre le sommet de rang i et le sommet de rang j du graphe.
Le coefficient de la première ligne et quatrième colonne de la matrice R est , celui de la matrice S est . Or il y trois chaînes de longueur 4 entre le sommet A et le sommet D : A - B - C - E - D, A - F - C - E - D et A - F - I - E - D. Donc la matrice R ne peut pas être la matrice .
La matrice S est la matrice .
Un touriste a quitté son hôtel H et s'est rendu au jardin J. Au cours de son déplacement, il est passé exactement trois fois devant un des centres d'intérêt du quartier.
Combien de trajets différents a-t-il pu suivre ? Expliquer.
Le touriste est passé exactement trois fois devant un des centres d'intérêt du quartier donc son parcours est modélisé par une chaîne de longueur 4 entre le sommet H et le sommet J.
Le coefficient de la huitième ligne et de la dernière colonne de la matrice étant égal à 4, il y a quatre chaînes de longueur 4 entre le sommet H et le sommet J.
Le touriste a pu emprunter quatre trajets différents pour aller de son hôtel au jardin.
Déterminer en justifiant si ce graphe est connexe.
Les termes de la matrice ne sont pas nuls. Par conséquent, pour toute paire de sommets du graphe il existe au moins une chaîne de longueur 4 les reliant donc le graphe est connexe.
Est-il possible pour un touriste de parcourir chaque rue du quartier une et une seule fois en partant de son hôtel H ?
Effectuer un parcours qui passe une seule fois par chaque rue c'est chercher si il existe une chaîne eulérienne.
Le graphe est connexe et il n'y a que deux sommets A et G de degré impair, il existe donc des chaînes eulérienne d'extrémités A et G.
Un touriste ne peut pas parcourir chaque rue du quartier une et une seule fois en partant de son hôtel H.
Sur le graphe pondéré ci-dessous, on a indiqué sur les arêtes les distances en mètres entre les différents lieux.
À l'aide d'un algorithme, déterminer la distance minimale permettant d'aller du sommet H (hôtel) au sommet J (jardin). Préciser alors le trajet à emprunter.
Pour déterminer le trajet le plus court pour aller du sommet H au sommet J, on utilise l'algorithme de Dijkstra.
| A | B | C | D | E | F | G | H | I | J | Sommet sélectionné |
| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 0 | ∞ | ∞ | H (0) |
| ∞ | 130 (H) | ∞ | 260 (H) | ∞ | ∞ | ∞ | ∞ | ∞ | B (130) | |
| 820 (B) | 290 (B) | 260 (H) | 570 (B) | ∞ | ∞ | ∞ | ∞ | D (260) | ||
| 820 (B) | 290 (B) | 540 (D) | ∞ | ∞ | ∞ | ∞ | C (290) | |||
| 820 (B) | 530 (C) | 990 (C) | ∞ | 930 (C) | ∞ | E (530) | ||||
| 820 (B) | 990 (C) | ∞ | 810 (E) | ∞ | I (810) | |||||
| 820 (B) | 940 (I) | ∞ | 970 (I) | A (820) | ||||||
| 940 (I) | 1070 (A) | 970 (I) | F (940) | |||||||
1050 (F) | 970 (I) | J (970) |
Le sommet J étant marqué, pour lire la chaîne de poids minimal, on part de J et on remonte la chaîne en suivant les prédécesseurs. .
Le trajet le plus court pour aller de H à J est H - B - C - E - I - J, la distance parcourue est de 970 mètres.
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.