Répondre à la discussion
Affichage des résultats 1 à 4 sur 4

Graphes Valués



  1. #1
    cartapuces

    Graphes Valués


    ------

    Bonjour à tous,

    Je suis en MPSI, option informatique. La question que j'aimerais vous poser est soulevée dans un DM d'info que j'ai à faire, mais c'est entièrement une question de maths.

    Le sujet est le deuxième problème du concours mines-ponts 2008, accessible via le lien suivant: http://minesponts.scei-concours.org/.../info-2008.pdf. La question qui me tracasse est la question 25: c'est la deuxième question de la 4ème partie (pour y répondre, la lecture des parties 1, 2 et 3 n'est absolument pas nécessaire, il suffit de connaître les notations introduites en tout début de problème).

    Je ne parviens absolument pas à établir l'inégalité demandée. Quelqu'un pourrait me mettre sur la voie??

    Merci,


    Cartapuces.

    -----

  2. Publicité
  3. 📣 Nouveau projet éditorial de Futura
    🔥🧠 Le Mag Futura est lancé, découvrez notre 1er magazine papier

    Une belle revue de plus de 200 pages et 4 dossiers scientifiques pour tout comprendre à la science qui fera le futur. Nous avons besoin de vous 🙏 pour nous aider à le lancer...

    👉 Je découvre le projet

    Quatre questions à explorer en 2022 :
    → Quels mystères nous cache encore la Lune 🌙 ?
    → Pourra-t-on bientôt tout guérir grâce aux gènes 👩‍⚕️?
    → Comment nourrir le monde sans le détruire 🌍 ?
    → L’intelligence artificielle peut-elle devenir vraiment intelligente 🤖 ?
  4. #2
    acx01b

    Re : Graphes Valués

    salut

    tu prends les arrêtes de ton tour T, et tu les minores par les arrêtes qui sont dans ton Eval

    un sommet u_a de ton tour T qui est dans U, dont les 2 sommets voisins sont u_b et u_c, tu peux minorer : (u_b,u_a) + (u_a,u_c) par eval2(....,u_a)
    reste à trouver un bon minorant pour les sommets de ton tour qui ne sont pas dans U, et ça devrait fonctionner

  5. #3
    cartapuces

    Re : Graphes Valués

    Bonjour,

    Je ne vois pas très bien ce que tu veux dire. j'ai effectivement essayé de minorer le poids des arrêtes du tour T par celui des arrêtes de mon eval, mais je ne vois pas comment faire apparaître le facteur 1/2.
    En fait, l'inégalité demandée revient à montrer que:

    la somme des arrêtes dont les sommets sont dans U est supérieure ou égale à partie entière ( 1/2 * eval1(...)+eval1(...) + eval2(...) ).

    Comme tu me l'as dit, j'ai sommé le poids des arrêtes des sommets dans U et les ai majoré par une somme des eval2(..., u_a), un sommet sur deux. Mais je n'arrive pas à conclure...

  6. #4
    acx01b

    Re : Graphes Valués

    prends un graphe à 4 sommets : a,b,c,d
    ton tour c'est (a,b,c,d)
    ta chaine c'est (a,b)
    U = (c,d)
    U' = U union {a,b} = (a,b,c,d)

    poids(tour) = (a,b) + (b,c) + (c,d) + (d,a)
    eval(chaine) = (a,b) + 1/2 (min(b,U) + min(c,U') + min2(c,U') + min(d,U') + min2(d,U') + min (a,U))

    (b,c) + (c,d) est minoré par min(c,U') + min2(c,U')
    (c,d) + (d,a) est minoré par min(d,U') + min2(d,U')
    (b,c) est minoré par min(b,U)
    (d,a) est minoré par min (a,U)

    donc 2 ((b,c) + (c,d) + (d,a))
    est minoré par :
    min(b,U) + min(c,U') + min2(c,U') + min(d,U') + min2(d,U') + min (a,U)

  7. A voir en vidéo sur Futura

Discussions similaires

  1. encore un pb de graphes
    Par christophe_de_Berlin dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 23/03/2008, 10h05
  2. (dm) GRAPHES
    Par blueangel974 dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 21/04/2007, 18h19
  3. Théorie des graphes et graphes de liaisons
    Par Eogan dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 08/12/2006, 23h59
  4. Graphes de Coxeter
    Par fderwelt dans le forum Mathématiques du supérieur
    Réponses: 6
    Dernier message: 30/06/2006, 11h02
  5. Graphes
    Par oli1978 dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 19/12/2005, 14h24