On a schématisé ci-dessous le plan d'une MJC (Maison de la Jeunesse et de la Culture) par un graphe dont les sommets sont les salles et les arêtes sont les passages (portes, couloirs ou escaliers) entre les salles.
On appelle H le hall d'entrée et B le bureau du directeur.
En fin de journée, un agent de service fait le tour de la MJC pour récupérer dans chaque salle (bureau du directeur et hall inclus) les objets oubliés par les enfants.
Préciser si ce graphe est connexe en justifiant la réponse.
La chaîne H - F - A - B - C - E - D 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.
Déterminer, en justifiant, si l'agent de service peut passer par toutes les salles en utilisant une fois et une seule chaque passage.
Le graphe est connexe et deux sommets F et D du graphe sont de degré impair, il existe donc une chaîne eulérienne d'extrémités F et D.
L'agent de service peut passer par toutes les salles en utilisant une fois et une seule chaque passage.
On range les sommets par ordre alphabétique. Donner la matrice d'adjacence M associée au graphe.
On donne : En déduire le nombre de chemins de longueur 4 entre les sommets B et H.
Le terme de la matrice situé à l'intersection de la deuxième ligne et de la dernière colonne est égal à 6. Il existe six chemins de longueur 4 entre les sommets B et H.
On a indiqué sur le graphe ci-dessous le temps en minute mis pour passer entre les différentes salles en ouvrant et fermant les portes à clé.
À l'aide d'un algorithme, déterminer le temps minimal en minute pour aller de B à H.
À l'aide de l'algorithme de Dijkstra, déterminons le temps minimal en minute pour aller de B à H.
| B | A | C | D | E | F | H | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | B (0) |
| 2 (B) | 2 (B) | ∞ | ∞ | ∞ | ∞ | A (2) | |
| 2 (B) | ∞ | 4 (A) | 5 (A) | ∞ | C (2) | ||
| 3 (C) | 4 (A) | 5 (A) | ∞ | D (3) | |||
| 4 (A) | 5 (A) | 5 (D) | E (4) | ||||
| 4 (E) | 5 (D) | F (4) | |||||
| 5 (D) | H (5) |
Le sommet H étant marqué, pour lire la chaîne de poids minimal, on part de H et on "remonte" la chaîne en suivant les prédécesseurs. .
Le plus court chemin pour aller de B à H est B - C - D - H. Ce trajet dure 5 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.