Bonjour, est-ce que vous pourriez m'aider pour cette exo SVP ??? je m'en sors vraiment pas j'ai réussi à faire que la question 1-a), je suis vraiment bloqué
Un parc de loisirs propose à ses visiteurs des parcours d?accrobranche.
Les différents parcours sont modélisés par le graphe G de la figure 4 où les sommets correspondent aux neuf arbres marquant leurs extrémités. Chaque parcours est représenté par une arête du graphe et peut être réalisé dans les deux sens.
Les distances des parcours entre deux arbres, exprimées en mètres, sont indiquées sur les arêtes. (le graphe est dans l'adresse à la fin)

a) Expliquer pourquoi Énora ne peut pas réaliser un itinéraire complet d?accrobranche, c?est-à-dire un itinéraire empruntant une fois et une seule chaque parcours. (c bon j'ai trouvé car pas de chaîne eulérienne)

b) Énora souhaiterait réaliser un itinéraire empruntant au moins une fois chaque parcours. Déterminer les parcours où elle pourra passer deux fois afin de minimiser la distance totale de son itinéraire.

c) Donner la longueur minimale, exprimée en mètres, d?un tel itinéraire. Proposer un itinéraire possible.

2- L?organisateur du parc de loisirs voudrait moderniser, en trois étapes, les différents parcours de son parc. Il envisage de le faire en modernisant, à chaque étape, un tiers des parcours. Pendant les travaux seuls les parcours à moderniser sont inaccessibles.
Lors de la première étape il souhaite laisser accessibles des parcours reliant tous les arbres entre eux et minimisant la distance totale.

a) Déterminer les parcours qu?il est possible de rénover lors de la première étape (vous pouvez utiliser l?algorithme de Kruskal pour déterminer un arbre couvrant minimal).

b) Énora voudrait, dans ces conditions, réaliser un itinéraire passant par tous les arbres et qui emprunte chacun des parcours disponibles une fois et une seule. Est-ce possible ? Si oui, par quel(s) arbre(s) Énora peut-elle commencer son itinéraire ? Donner la longueur d?un tel itinéraire.

http://****  (graphe)

malou > ***image rapatriée**** merci d'en faire autant la prochaine fois