On considère le graphe de sommets A, B, C, D, E et F dont la matrice associée est
Quel est le nombre d'arêtes de ce graphe ?
La matrice M est symétrique par rapport à sa diagonale donc le graphe n'est pas orienté. Or dans un graphe non orienté, la somme des degrés des sommets est égale au double du nombre d'arêtes.
| Sommets | A | B | C | D | E | F | Somme |
| Degrés | 3 | 4 | 3 | 4 | 2 | 4 | 20 |
Le nombre d'arêtes du graphe est égal à 10.
Ce graphe est-il complet ? Ce graphe est-il connexe ?
Certains coefficients de la matrice M situés en dehors de la diagonale sont nuls donc le graphe n'est pas complet.
Tous les termes de la matrice sont non nuls il existe donc au moins un chaîne de longueur 2 entre deux sommets quelconques du graphe le graphe est connexe.
Ce graphe admet-il une chaîne eulérienne ? Justifier la réponse. Si oui donner une telle chaîne.
Le graphe est connexe et il y a exactement deux sommets de degré impair donc il existe une chaîne eulérienne par exemple A - B - D - F - B - E - F - C - D - A - C.
Pour chercher une chaîne eulérienne, représenter le graphe ayant pour matrice M
Après avoir chargé son camion à l'entrepôt noté A, un livreur doit livrer cinq clients notés B, C, D, E et F.
Le graphe ci-dessous, modélise le réseau routier en tenant compte des sens de circulation et des temps de parcours en minutes.
Quel trajet permet de minimiser le temps de parcours pour effectuer les cinq livraisons ?
En utilisant l'algorithme de Dijkstra, déterminons les temps de parcours minimum de l'entrepôt à chacun des clients.
| A | B | C | D | E | F | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | A (0) |
| 32 (A) | 15 (A) | ∞ | ∞ | ∞ | C (15) | |
| 32 (A) | 22 (C) | ∞ | ∞ | D (22) | ||
| 30 (D) | ∞ | ∞ | B (30) | |||
| ∞ | 46 (B) | F (46) | ||||
| 64 (F) | E (64) |
Le dernier sommet E étant marqué, pour lire la chaîne de poids minimal reliant A à E, on part de E et on "remonte" la chaîne en suivant les prédécesseurs. .
Comme la chaîne A-C-D-B-F-E contient tous les sommets du graphe, la chaîne de poids minimal reliant A à E permet d'effectuer les cinq livraisons.
Le trajet qui permet de minimiser le temps de parcours pour effectuer les cinq livraisons est A-C-D-B-F-E.
Après avoir effectué ses livraisons, le livreur doit retourner l'entrepôt. Quel trajet lui permet de minimiser son temps de parcours pour le retour ?
En ne tenant pas compte des arrêts nécessaires pour effectuer les livraisons, le trajet du retour est-il plus rapide que celui de l'aller ?
À l'aide de l'algorithme de Dijkstra, déterminons la chaîne de poids minimal reliant E à A.
| E | B | C | D | F | A | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | E (0) |
| 24 (E) | ∞ | ∞ | 18 (E) | ∞ | F (18) | |
| 24 (E) | 44 (F) | 37 (F) | ∞ | B (24) | ||
| 44 (F) | 32 (B) | 64 (A) | D (32) | |||
| 44 (F) | 48 (D) | C (44) | ||||
| 48 (D) | A (48) |
Le trajet le plus rapide pour reourner à l'entrepôt est E-B-D-A. Le temps de parcours au retour est de 48 minutes contre 64 minutes à l'aller.
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.