Sur le graphe ci-contre, les sept sommets A, B, C, D, E, F et G correspondent à sept villes. |
Les questions 1, 2 et 3 sont indépendantes.
Est-il possible de trouver un trajet, utilisant les liaisons existantes, qui part d'une des sept villes et y revient en passant une fois et une seule fois par toutes les autres villes ?
Trouver un trajet, utilisant les liaisons existantes, qui part d'une des sept villes et y revient en passant une fois et une seule fois par toutes les autres villes revient à chercher un cycle de longueur 7.
Il suffit de trouver un trajet qui convienne :
Par exemple A-C-E-F-D-G-B-A.
Un cycle n'a ni origine ni extremité, A-C-E-F-D-G-B-A, A-B-G-D-F-E-C-A ou E-F-D-G-B-A-C-E définissent le même cycle.
On note M la matrice associée au graphe ci-dessus. Les sommets sont rangés suivant l'ordre alphabétique.
On donne
Donner le nombre de chemins de longueur 3 qui relient le sommet A au sommet F. Les citer tous. Aucune justification n'est demandée.
Le nombre de chaînes de longueur 3 qui relient le sommet A au sommet F est le terme situé à l'intersection de la première ligne et la cinquième colonne de la matrice .
4 de chemins de longueur 3 relient le sommet A au sommet F : A-B-D-F, A-B-E-F, A-C-D-F et A-C-E-F.
On donne ci-dessous et sur le graphe ci-contre les distances exprimées en centaines de kilomètres entre deux villes pour lesquelles il existe une liaison :
AB : 5 ; AC : 7 ;
BD : 8 ; BE : 15 ;
BG : 6 ; CD : 10 ;
CE : 15 ; DF : 20 ;
DG : 10 ; EF : 5 ;
Un représentant de commerce souhaite aller de la ville A à la ville F.
En expliquant la méthode utilisée, déterminer le trajet qu'il doit suivre pour que la distance parcourue soit la plus courte possible et donner cette distance
Pour déterminer le plus court chemin possible pour aller de la station E à la station S on utilise l'algorithme de Dijkstra.
| A | B | C | D | E | F | G | Sommet sélectionné et commentaires |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | A de poids 0 on marque les sommets adjacents A et B |
| 5 (A) | 7 (A) | ∞ | ∞ | ∞ | ∞ | B on marque les sommets adjacents D , E et G | |
| 7 (A) | 13 (B) | 20 (B) | ∞ | 11 (B) | Con conserve le poids de D (7+10>13) et E (7+15>20) | ||
| 13 (B) | 20 (B) | ∞ | 11 (B) | Gon conserve le poids de D (11+10>13) | |||
| 13 (B) | 20 (B) | ∞ | D on marque le sommet adjacent F | ||||
| 20 (B) | 33 (D) | Eon change le poids de F (20+5<33) | |||||
| 25 (E) | F |
Pour déterminer le trajet le plus court on remonte les sommets à l'envers :
F vient de E qui vient de B qui vient de A.
Le trajet le plus court est A-B-E-F, la distance parcourue est de 2 500 kilomè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.