Le graphe ci-dessous représente le plan d'une ville. Le sommet A désigne l'emplacement des services techniques. Les sommets B, C, D, E, F et G désignent les emplacements de jardins publics. Une arête représente l'avenue reliant deux emplacements et est pondérée par le nombre de feux tricolores situés sur le trajet.
Les parties I et II sont indépendantes.
partie I : On s'intéresse au graphe non pondéré.
Répondre sans justification aux quatre questions suivantes :
Ce graphe est-il connexe ?
Un graphe est connexe si deux sommets quelconques sont reliés par une chaîne.
Ce graphe est-il complet ?
Un graphe simple est dit complet si tous ses sommets sont adjacents.
Ce graphe admet-il une chaîne eulérienne ?
Ce graphe admet-il un cycle eulérien?
Déterminer, en justifiant, le nombre chromatique de ce graphe.
partie II : On s'intéresse au graphe pondéré.
Proposer un trajet comportant un minimum de feux tricolores reliant A à G. La réponse sera justifiée par un algorithme.
Algorithme de Dijkstra.
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.