Pauvre facteur!

SXB
SXB
dans Géométrie
Un facteur part d'un centre de livraison et veut livrer dans son morceau de quartier qui a la forme d'un polygone régulier à n côtés (n >= 3) "centré" sur la poste (c'est à dire que toutes les médiatrices des côtés du polygone se coupent à la poste).

On suppose que le facteur roule parallèlement aux bords de la rue, sachant qu'il n'y a que deux types de rues:

* Les rues qui joignent la poste au "mini périph" que constitue le polygone.

* Les rues du "mini périph, c'est à dire les côtés du polygone.

Supposons que le facteur peut livrer dans toute une rue en n'y passant qu'une fois (en gros il peut traverser la rue pour livrer et n'a donc pas à faire deux passages ou plus).

Quel est le modèle de trajet qu'il doit empolyer pour livrer toute les marchandises du quartier en parcourant une distance minimale?

J'ai peut-être été faible dans la rigueur, mais le bon sens compensera.

Merci d'y répondre, avant demain si possible.

Réponses

  • jobherzt
    jobherzt
    a mon sens, c'est plus de la théorie des graphes que de la geometrie. ce que je peux dire a chaud, si j'ai bien compris ta description, c'est qu'il n'et pas possible de faire la tournée en passant une et une seule fois par chaque rue.
  • jaybe
    jaybe
    Il part de la poste en choisissant un sommet au hasard, puis il parcourt le périphérique dans son intégralité, enfin il revient à la poste. S'il doit passer deux fois par rue, il fait un tour en sens inverse quand il a fini le premier.
  • bosio frederic0
    bosio frederic0
    Attaention. Il doit passer dans chaque rue reliant la poste a un sommet. Comme chaque sommet du polygone est trivalent, il doit y passer au moins deux fois.
  • jobherzt
    jobherzt
    a priori il n'y a pas plus court que de faire chacun des triangles composant la figure..
  • bosio frederic0
    bosio frederic0
    Euh, des triangles, il y en a vraiment baeaucoup. Je pense que si le nombre de cotes est grand, le plus cour est de faire beaucoup de petits triangles (i.e. a un seul cote du polygone et deux rues reliant la poste au polygone), ainsi qu'un grand tour. A quelques exceptions pres, chaque rue reliant la poste au polygone sera parcourue une seule fois et la moitie des rues du polygone sera parcourue deux fois, l'autre une seule fois.

    Toutefois, pour les petites valeurs du nombre de cotes, il y a mieux (pour un triangle, ne parcourir qu'une fois chaque cote du triangle et deux fois les autres rues me semble mieux -mais je n'ai pas fait le calcul- que de parcourir un triangle puis de fair une tour complet). Je vais verifier.
  • bosio frederic0
    bosio frederic0
    Non, je me trompais. En fait, meme pour le triangle il vaut mieux faire d'abord un triangle puis un tour complet, d'autant plus que je m'apercois qu'on n'est pas oblige de faire le tour complet. On peut oublier le cote qu'on a deja fait, ce qui raccourcit encore le trajet.
  • jaybe
    jaybe
    Ok, une nouvelle tentative : commencer par doubler les arêtes issues de la poste. Puis on retire deux par deux de telles arêtes d'un même triangle en rajoutant une arête sur le troisième coté (à la fin, il y a la moitié (ou la moitié moins une) des arêtes extérieures qui sont doublées). Il reste à voir qu'il existe bien un chemin Eulérien sur le graphe obtenu.
  • jacquot
    jacquot
    Bonsoir,

    Là, je me suis intéressé à l'hexagone régulier (côté = rayon = 1)
    J'arrive à une tournée de 15.
    Je tiens un croquis à votre disposition sur demande. Je saurais démontrer qu'on ne peut pas faire mieux en utilisant "valences" des sommets, selon la terminologie de bosio frederic.

    Ensuite, pour les polygones (réguliers) suivants, cela se compliquera suivant la parité du nombre des sommets... de plus, il vaudra mieux parcourir 2 fois un côté, plutôt qu'un rayon parce que les côtés seront plus courts que les rayons

    PS, pour un octogone régulier de rayon 1 j'ai une tournée de $8 +24.sin (\frac {\pi }{8})$
  • jacquot
    jacquot
    Voilà,
    Pour l'heptagone, ce sera $ 8 + 20 sin(\frac {\pi }{7})$

    Je pense être en mesure de pouvoir généraliser à présent. l'octogone et l'heptagone étant de bons exepmles pour comprendre la tournée du facteur.
    A suivre, si cela intéresse quelqu'un.
  • SXB
    SXB
    Ah toutes ces réponses me touchent, mais elles ne m'aident pas encore bcp.

    En effet j'avais déà trouvé la formule suivante pour un sous-domaine de solutions:

    soit un polygone régulier à n côtés et O son centre.

    Appellons le [A1;...;An]. On pose R=OA1=...=OAn et c=A1A2=...=AnA1=2Rsin(Pi/n).

    6099
    6100
    6101
    6102
  • SXB
    SXB
    Waah! Je viens de trouver encore mieux!

    On remplace "2k-1 divise n" par "2k divise n".

    Et là bim bam boum (voir le dessin que je vais mettre pour n=20 et k=2):

    6103
  • jaybe
    jaybe
    La théorie des graphes te dit que, pour tout cycle dans un graphe orienté, et en tout sommet, le nombre d'arêtes qui commence par ce sommet doit être égal au nombre d'arêtes qui finissent par ce sommet. Ici, tout sommet sur le périphérique est relié à trois arêtes, donc pour faire un chemin qui passe par toutes les arêtes (un cycle eulérien), il est nécessaire que, parmi les arêtes issues d'un même sommet périphérique, l'une d'entre elles soit parcourue au moins deux fois. Pour rajouter le moins de distance possible, on les groupe deux par deux ; dans le cas pair, cela suffit, et dans le cas impair, il faut rajouter une fois le parcours sommet->poste pour le dernier sommet. Il reste à construire un tel cycle : par exemple, on peut commencer par un parcours périphérique complet, puis faire des aller-retours de la poste vers la périphérie en tournant dans le sens trigonométrique.
  • SXB
    SXB
    Ouais mais là je crois que ma dernière sol est meilleure, d'autant plus que n est grand: exemple dessin avec n=20: difficile de faire mieux, car à mesure que n augmente, c'est le nombre de rayons parcourus qui doit être limité au maximum, ainsi que le nombre de fois (nombre rationnel) que le périph est parcouru.

    Tout rayon est parcouru au moins une fois, donc le nombre de rayons parcourus est au moins égal au nombre de côtés du polygone.

    Ma dernière solution décrit un parcours où le cercle est parcouru 1.5 fois (en tout cas pour n pair) et chaque rayon ne l'est qu'une fois. Je pense que c'est la solution optimale, mais qui sait peut-être qu'il y aura mieux. Pour n impair (n=2k+1) , il en va de même sauf que le cercle (2(k+1) + k)/(2k+1) fois, c'est à dire (3k+2)/(2k+1) fois (et don un peu plus de 1.5 fois).

    Pour parler avec tes termes en décrivant une nouvelle fois ma solution, on part de la poste, on arrive sur le périph, on recule d'un cran sur le périph, on avance de deux crans sur le périph et on revient en O. Cela donne un motif que l'on répète un nombre de fois égal à la partie entière de n/2... et on bidouille pour le dernier motif.
  • jacquot
    jacquot
    Salut, SXB

    Tu as bien trouvé le chemin minimal.

    Comme te l'a expliqué jaybe, les sommets sont des points de passage, tout chemin qui y arrive doit en repartir, ils sont donc connectés un nombre pair de fois (au moins 4 fois)

    la solution que tu donnes consiste à choisir les parcours doublés sur les côtés, de préférence aux rayons ce qui est plus économique, dès lors que n>6
    (voir les formules proposées plus haut pour n=8 et n=7 conformes à ta description).

    Les cas n<6 seront différents.
    Cordialement.
  • jaybe
    jaybe
    En fait, les cas $n<6$ sont semblables : même si une arête vers le centre est alors plus courte qu'une arête périphérique, placer une arête vers le centre ne règle le degré que d'un sommet, tandis que placer une arête extérieure règle le degré de deux sommets.

    SXB, ta solution fait bien partie des solutions optimales (il y en a beaucoup d'autres !).
  • jacquot
    jacquot
    D'accord avec ton analyse, jaybe!
  • SXB
    SXB
    Oui, merci à tous les deux. La phrase clé était "les sommets sont des points de passage, tout chemin qui y arrive doit en repartir, ils sont donc connectés un nombre pair de fois"et donc nécessairement au moins 4 fois. Merci à tous les deux!
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 25

ChaurienFoysGot66JLapinMatricule_63PetitLutinMalicieuxTOTO25Thierry Pomamanussistfjzeste +13 Invités