Dans le graphe ci-dessous, les sommets représentent différentes zones de résidence ou d'activités d'une municipalité. Une arête reliant deux de ces sommets indique l'existence d'une voie d'accès principale entre deux lieux correspondants.
Donner, sans justifier, le degré de chacun des sommets (la réponse pourra être présentée sous forme de tableau où les sommets seront mis dans l'ordre alphabétique).
Dans un graphe simple non orienté, le degré d'un sommets est le nombre d'arêtes issues de ce sommet :
| Sommet | A | B | C | D | E | F | G |
| Degré | 2 | 4 | 5 | 5 | 4 | 4 | 2 |
Donner la matrice M associée au graphe (les sommets seront mis dans l'ordre alphabétique).
La matrice M associée au graphe est
On donne la matrice . Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant A et F puis donner leur liste.
Le coefficient situé à l'intersection de la première ligne et de la sixième colonne de la matrice donne le nombre de chaînes de longueur 3 reliant les sommets A et F :
Il y 5 chemins de longueur 3 reliant A et F : A-B-C-F ; A-B-D-F ; A-B-E-F ; A-C-D-F et A-C-E-F.
Pour sa campagne électorale, un candidat souhaite parcourir toutes les voies d'accès principales de ce quartier sans emprunter plusieurs fois la même voie. Montrer qu'un tel parcours est possible.
Les coefficients de la matrice sont tous non nuls, par conséquent, il existe au moins une chaîne de longueur 3 reliant deux sommets quelconques du graphe donc le graphe est connexe.
D'autre part, les sommets C et D sont les seuls sommets de degré impair. Le graphe est connexe et il y a exactement deux sommets de degré impair donc il existe une chaîne eulérienne d'extrémités C et D.
Il est possible de parcourir toutes les voies d'accès principales de ce quartier sans emprunter plusieurs fois la même voie.
Dans le graphe ci-dessous, les valeurs indiquent, en minutes, les durées moyennes des trajets entre les différents lieux via les transports en commun.
Ce même candidat se trouve à la mairie (A) quand on lui rappelle qu'il a un rendez-vous avec le responsable de l'hôpital situé en zone G.
En utilisant l'algorithme de Dijkstra, déterminer le chemin de durée minimale que ce candidat devra emprunter pour arriver à son rendez-vous.
| A | B | C | D | E | F | G | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | A (0) |
| 8 (A) | 4 (A) | ∞ | ∞ | ∞ | ∞ | C (4) | |
| 8 (A) | 20 (C) | 16 (C) | 24 (C) | ∞ | B (8) | ||
| 12 (B) | 16 (C) | 24 (C) | ∞ | D (12) | |||
| 16 (C) | 24 (C) | 32 (D) | E (16) | ||||
| 20(E) | 32 (D) | F (20) | |||||
| 28 (F) | G (28) |
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 chemin de durée minimale que ce candidat devra emprunter pour arriver à son rendez-vous est A-C-E-F-G.
Combien de temps faut-il prévoir pour effectuer ce trajet ?
Le poids de la chaîne A-C-E-F-G est 28. Il faudra prévoir 28 minutes pour effectuer ce trajet.
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.