Les parties A et B peuvent être traitées indépendamment
On considère le graphe Γ ci-dessous :
Ce graphe admet-il une chaîne eulérienne ? Justifier la réponse. Si oui donner une telle chaîne.
La chaîne A - B - C - D - E - F - G contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets distincts, il existe une chaîne les reliant donc le graphe est connexe.
Dans un graphe non orienté, le degré d'un sommet du graphe est le nombre d'arêtes issues de ce sommet. D'où :
| Sommets | A | B | C | D | E | F | G |
| Degré des sommets du graphe | 2 | 4 | 4 | 5 | 4 | 4 | 3 |
Le graphe est connexe et contient seulement deux sommets de degré impair donc il existe une chaîne eulérienne commençant par un des deux sommets de degré impair (D ou G) et finissant par le deuxième sommet de degré impair.
Le graphe Γ admet une chaîne eulérienne. Par exemple D - C - A - B - C - F - G - D - F - E - B - D - E - G.
Ce graphe admet-il un cycle eulérien ? Justifier la réponse. Si oui donner un tel cycle.
Les sommets du graphe Γ ne sont pas tous de degré pair, donc il n'existe pas de cycle eulérien.
Donner la matrice M associée au graphe Γ. Les sommets seront pris dans l'ordre alphabétique : A, B, C, D, E, F, G.
La matrice d'adjacence du graphe est
Une région est munie d'un réseau de trains, représenté par le graphe Γ ci-dessous.
Les stations sont symbolisées par les sommets A, B, C, D, E, F et G. Chaque arête représente une ligne reliant deux gares. Les temps de parcours (correspondance comprise) en minutes entre chaque sommet ont été rajoutés sur le graphe.
Déterminer le plus court chemin en minutes, reliant la gare B à la gare G. Justifier la réponse grâce à un algorithme.
Pour déterminer le trajet le plus court pour aller de B à G, on utilise l'algorithme de Dijkstra.
| A | B | C | D | E | F | G | Sommet sélectionné |
| ∞ | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | B (0) |
| 4 (B) | 7 (B) | 18 (B) | 21 (B) | ∞ | ∞ | A (4) | |
| 7(B) | 18 (B) | 21 (B) | ∞ | ∞ | C (7) | ||
| 17 (C) | 21 (B) | 32 (C) | ∞ | D (17) | |||
| 21 (B) | 29 (D) | 48 (D) | E (21) | ||||
| 29 (D) | 38 (E) | F (29) | |||||
| 36 (F) | G (36) |
Le sommet G étant marqué, pour lire la chaîne de poids minimal, on part de G et on "remonte" la chaîne en suivant les prédécesseurs. .
Le plus court chemin en minutes, reliant la gare B à la gare G est B-C-D-F-G. Le temps minimum de parcours est de 36 minutes.
Quelle est la longueur en minutes de ce chemin ?
La longueur en minutes du chemin B-C-D-F-G est de 36 minutes.
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.