On considère le graphe ci-dessous :
On appelle M la matrice d'adjacence de ce graphe, les sommets étant pris dans l'ordre alphabétique. Une des trois matrices R, S ou T est la matrice .
; ;
Sans calculer la matrice , indiquer quelle est la matrice en justifiant votre choix.
En déduire le nombre de chaînes de longueur 4 entre B et H.
Déterminer en justifiant si le graphe est complet.
Déterminer en justifiant si le graphe est connexe.
Ce graphe modélise une partie du plan d'une commune. Les arêtes du graphe représentent les rues et les sommets du graphe sont les points de vente de quotidiens.
Est-il possible de planifier un parcours permettant le nettoyage de toutes ces rues sans emprunter plusieurs fois la même rue ? Justifier la réponse. Si oui proposer un parcours.
Le graphe pondéré ci-dessous, donne en minutes, les durées moyennes des parcours des différentes rues en tenant compte des sens uniques.
Après avoir effectué une livraison au point de vente A, le livreur doit récupérer les quotidiens invendus au point de vente G.
En utilisant un algorithme, déterminer le trajet le plus rapide pour aller de A à G.
Est-il possible en partant de A d'effectuer une tournée qui dure moins de 45 minutes en passant par tous les points de vente de quotidiens ?
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.