28 de junio de 2015

9 messages - Retourner à l'article
  • Graphes 2

    le 28 de junio de 2015 à 08:59, par Christophe Boilley

    Le problème 9 me laisse perplexe. Si on relie Toulouse à Saint-Louis du Sénégal, puis Saint-Louis à Natal au Brésil, on obtient bien un graphe connexe. Mais comment Mermoz aurait-il fait avec la fermeture de Saint-Louis, si l’on s’interdit d’inventer d’autres escales ?

    Pour obtenir la propriété voulue, j’aurais plutôt mis comme hypothèse que deux quelconques des aéroports sont toujours parcourus par au moins un cycle.

    Répondre à ce message
    • Graphes 2

      le 28 de junio de 2015 à 11:04, par Idéophage

      Bonjour,

      Si on choisit de fermer Toulouse ou Natal, les deux autres aéroports peuvent toujours être reliés, donc la propriété est vérifiée sur ce graphe.

      Répondre à ce message
      • Graphes 2

        le 28 de junio de 2015 à 12:19, par Christophe Boilley

        C’est l’éternel problème de l’article « un », tantôt universel, tantôt existentiel. Dans le problème 6, par exemple, il ne suffit pas de trouver un graphe connexe satisfaisant la propriété, mais de montrer que tous les graphes connexes avec un sommet de plus que le nombre d’arêtes sont des arbres.

        Répondre à ce message
        • Graphes 2

          le 28 de junio de 2015 à 16:04, par Idéophage

          Ah, d’accord. Donc vous avez raison, ce que vous avez donné est une propriété nécessaire et suffisante si on veut pouvoir supprimer tout aéroport.

          Concernant l’ambiguïté du langage, c’est vrai que ce n’est pas forcément clairement défini, mais je n’ai pas souvenir d’avoir été gêné par une telle ambiguïté un jour… Peut-être que l’on peut préciser la chose en disant que, par défaut, « un » donne ∀, mais que si on est dans une possibilité (« on peut »), alors c’est plutôt ∃. Dans le cas général, on dit « pour toute possibilité d’instanciation des variables », mais si on est dans une possibilité, c’est « il existe une instanciation des variables ».

          À cela se rajoute peut-être le fait qu’il est aussi naturel de dire « pouvoir fermer tel aéroport (précis) sans perdre la connexité »… Bref.

          Répondre à ce message
          • Graphes 2

            le 28 de junio de 2015 à 16:27, par Idéophage

            Ce que j’ai dit ne fonctionne pas, en fait.

            Répondre à ce message
  • Graphes 2

    le 28 de junio de 2015 à 18:57, par Ilia Itenberg

    Dans le problème 9, la phrase «Montrer qu’on peut fermer un aéroport de ce réseau ...»
    signifie, bien sûr, «Montrer qu’il existe un aéroport de ce réseau tel qu’on puisse fermer cet aéroport ...».

    Pour pouvoir fermer TOUT aéroport du réseau sans perdre la possibilité de joindre deux autres quelconques aéroports du réseau, il n’est pas suffisant de supposer que deux quelconques des aéroports sont toujours parcourus par au moins un cycle. Par contre, il est suffisant de supposer, par exemple, que deux quelconques des aéroports sont parcourus par au moins un cycle qui ne passe jamais deux fois par le même aéroport (à l’exception du début et la fin du cycle).

    Répondre à ce message
  • Graphes 2

    le 14 de septiembre de 2015 à 23:34, par richecoeur

    Proposition de réponse au problème 1: supposons que nous nous déplaçons de planètes en planètes par les liaisons définies dans l’énoncée. Lorsque j’arrive à destination et je décide de retourner vers mon point de départ, j’emprunterai nécessairement la dernière liaison que j’ai suivi lors de mon arrivée à destination puisqu’elle est unique. D’où l’impossibilité de ne pas passer au moins deux fois par une même liaison.

    Répondre à ce message
    • Graphes 2

      le 16 de septiembre de 2015 à 11:11, par Sébastien Kernivinen

      Bonjour,

      Bravo pour votre proposition de solution au problème 1.

      Cependant, elle est incomplète: Que dire du cas où votre planète de départ est la même que celle d’arrivée ?

      cordialement,

      Sébastien.

      Répondre à ce message
  • Problème 1

    le 16 de septiembre de 2015 à 21:33, par richecoeur

    Le tronçon (arête) retour qui mènerait à la planète de départ est nécessairement celui emprunté en premier puisqu’il est unique ( par définition) dans ce cas aussi il est impossible de ne pas emprunter un tronçon deux fois.

    Répondre à ce message
Pour participer à la discussion merci de vous identifier : Si vous n'avez pas d'identifiant, vous pouvez vous inscrire.
La traducción del sitio del francés al castellano se realiza gracias al apoyo de diversas instituciones de matemáticas de América Latina.