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 ( à ne pas confondre avec un cycle eulérien). Il suffit de trouver un trajet qui convienne.
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 terme situé à l'intersection de la ligne i et de la colonne j de la matrice , donne le nombre de chaînes de longueur n reliant le sommet et le sommet du graphe.
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
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.