Les réseaux routiers - Lycée de la Versoie (Thonon les Bains)

Dans un réseau routier, que l’on va modéliser par un graphe, un employé doit faire un tour de toutes les routes pour s’assurer qu’elles sont en bon état.

L’idéal serait de le faire dans le moins de temps possible. Est ce que c’est toujours possible ? Est ce que c’est toujours possible en partant du dépôt (qui se trouve à l’un des nœuds du graphe) ? Si c’est toujours possible, en donner une démonstration, sinon, dire pour quels réseaux c’est possible. Dans tous les cas ou c’est possible, décrire comment construire un tel trajet.

S’il existe des cas ou ce n’est pas possible, dire dans ces cas quel est le chemin le plus court possible ?