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

Matroïde



  1. #1
    blade_

    Matroïde


    ------

    Bonjour, j'ai un petit problème qui me fatigue depuis quelques jours.

    La notion de matroïde utilisée ici est celle de Whitney, à savoir:

    un matroïde est un couple est un ensemble fini non vide et vérifie les deux propriétés suivantes:

    1. , implique . (hérédité)

    2. , , , tel que . (propriété de l'échange)

    Il s'agit de montrer la chose suivante:

    Si est un matroïde, alors avec est aussi un matroïde.

    Pour le faire, j'ai utilisé la définition donnée du matroïde.
    La propriété d'hérédité est très facile à prouver mais j'ai du mal avec celle de l'échange car jusqu'ici, je n'ai réussi à prouver qu'elle était vérifiée que sous certaines conditions et pas dans le cas général. Si quelqu'un a une idée ou une piste, je l'en remercie d'avance.

    -----

  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
    OBerge

    Re : Matroïde

    Salut,

    avec cette définition des matroïdes, cet exercice n'est en effet pas vraiment trivial. Par contre, il y en a une, dite de "caractérisation par les bases" qui lui supprime toute difficulté (mais cette caractérisation n'est à nouveau pas si évidente que ça à démontrer), bref.

    Des notions de bases et deux questions préparatoires sur les matroïdes, qui simplifient un peu le discours:

    - Les éléments de I sont appelés les "indépendants" de M (par analogie avec l'algèbre linéaire).
    - Une base de M est un indépendant de M qui est maximal pour l'inclusion.
    Exo 1: Vérifie (si tu ne l'as pas déjà fait) que toutes les bases de M ont le même nombre d'éléments (ce qui d'ailleurs, dans le cas linéaire, permet de définir la dimension d'un espace vectoriel)
    Exo 2: être un indépendant de M est équivalent à être contenu dans une base de M.

    Ainsi, I' n'est rien d'autre que les parties F de E pour lesquelles il existe une base de M disjointe de F.

    Pour démontrer que satisfait l'axiome d'échange, il suffit donc, comme tu l'as dit, de montrer que si avec |F|<|G|, alors il existe un avec .

    C'est à dire qu'il faut trouver un de sorte qu'il existe une base de M disjointe de .

    Voici de quoi démarrer (il est conseillé de faire un dessin):

    Par définition de G, il existe une base B de M disjointe de G (cette base peut éventuellement rencontrer F). Considère , dont tu constateras immédiatement que c'est un élément de I.

    De même, il existe une base de M contenue dans , et tu pourras démontrer facilement que ceci implique que est contenu dans une base B' de M disjointe de F (voir exo 2)!

    Il nous suffit ainsi pour conclure de montrer qu'il existe tel que F+x reste disjointe de B'!

    A partir d'ici, je te laisse terminer en utilisant l'exo 1. N'hésites pas à poser d'autres questions si tu le souhaites.

    Bon courage.

    OBerge

  5. #3
    blade_

    Re : Matroïde

    Avant toute chose, merci beaucoup de prendre le temps de me répondre.

    J'ai bien compris le raisonnement, mais j'ai une question: (en reprenant les mêmes notations)

    Comment peut-on être sûr que ne contient pas ? Parce que si c'est le cas, j'ai l'impression qu'on ne peut pas conclure...

    Puisqu'on ne trouvera pas de tel que est disjoint de .

    Merci encore.

  6. #4
    OBerge

    Re : Matroïde

    On démontre par l'absurde que n'est pas contenu dans B'.

    Une indication supplémentaire pour cela: si tu supposes que l'inclusion est satisfaite, alors tu peux montrer facilement (en utilisant les résultats intermédiaires) que , ce qui contredit le résultat de l'exercice 1.

  7. A voir en vidéo sur Futura
  8. #5
    blade_

    Re : Matroïde

    Ok, donc si j'arrive à montrer que ladite inclusion n'est pas satisfaite, alors je peux conclure; je vais voir ça...

    Merci!!

  9. #6
    blade_

    Re : Matroïde

    Ca y est, j'ai enfin trouvé. La démonstration par l'absurde reposait entre autres sur l'utilisation du fait que . Merci, le problème me semble résolu.

  10. Publicité