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

Arborescence infinie




  1. #1
    hedonyPower

    Arborescence infinie

    Bonjour,

    Je me pose la question suivante au sujet des arborescences binaires infinies :

    1. Est-il possible de définir "l'ensemble des feuilles" d'un tel arbre ? (en considérant la limite à l'infini du processus de construction de l'ensemble des feuilles de profondeur n par exemple...)

    2. Si oui peut on établir une bijection entre l'ensemble des feuilles et l'ensemble des chemins infinis qui partent de la racine ?

    J'ai essayé d'apporter un élément de réponse à la première question :

    Voici comment je construis mon arboresence A binaire infinie :

    On se donne un sommet racine * et chaque sommet de A possède exactement deux fils différents l'un de l'autre (un fils droit et un fils gauche).

    Ensuite je peux attribuer à chaque sommet une coordonnée différente dans un repère orthogonal.

    On attribue par coor le point de coordonnées coor(*) = (1,1) à la racine *.

    On attribue par coor les points de coordonnées coor(e)=(x_e,y_e) à chaque sommet e de l'arborescence en fonction du point de coordonnées (x_p, y_p)attribué à son père, c'est à dire :
    \begin{itemize}
    \item x_e=x_p - y_p/2 et y_e=y_p/2 ssi e est le fils droit de p
    \item x_e=x_p+y_p/2 et y_e=y_p/2 ssi e est le fils gauche de p
    \end{itemize}

    On obtient une sorte de fractale qui présente une série de points qui se répartissent en pyramide et dont le sommet est *. Cette série de points converge vers le segment défini entre les coordonnées (0,0) et (2,0) lorsqu'on effectue une infinité d'itérations du processus (c'est la base de la pyramide).

    coor est une bijection entre les sommets de A et les points de la figure obtenue.

    Peut-on dire que les feuilles de A correspondent aux points du segment entre (0,0) et (2,0) ?

    C'est la manière que j'ai trouvé de définir les feuilles de A. Est-ce correct ?

    -----


  2. Publicité
  3. #2
    Médiat

    Re : Arborescence infinie

    As-tu penser à numéroter des noeuds comme un nombre réel entre 0 et 1 écrit en binaire ?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  4. #3
    invité576543
    Invité

    Re : Arborescence infinie

    Tu peux faire un parallèle avec des réels et leur écriture en base 2. La correspondance avec le segment [0,1] est naturelle.

    Cordialement,


  5. #4
    super nono

    Re : Arborescence infinie

    Le plus simple serait peut-être de voir ça numériquement :

    Tu attribues à "fils droit" le chiffre 1 et à "fils gauche" le chiffre 0, le chemin infini peut s'écrire par une suite de chiffres 0 ou 1, tu rajoutes "0," devant et tu trouves l'écriture d'un nombre réel en binaire.

    Plus besoin de fractales, il faut juste faire attention aux nombres qui ont deux écritures en base 2, c'est à dire ceux de la forme q/(2^p)
    Dernière modification par super nono ; 19/09/2007 à 13h36. Motif: grillé !

  6. #5
    hedonyPower

    Re : Arborescence infinie

    Oui, j'y avais pensé... mais cela signifie que l'ensemble des feuilles de l'arborescence est indénombrable...
    Et si on considère la procédure qui consiste à parcourir l'arborescence en largeur et attribuer à chaque sommet le successeur de l'entier attribué au sommet précédent (sachant qu'on a attribué 0 à la racine), n'a-t-on pas là une procédure de dénombrement des sommets de l'arborescence ?

    Comme les feuilles sont des sommets de cette arborescence elles sont dénombrables non ? et on obtient une contradiction non ?

    du coup y'a une erreur quelque part qu'en pensez vous ?

    Merci de vos réponses en tous cas !

  7. A voir en vidéo sur Futura
  8. #6
    invité576543
    Invité

    Re : Arborescence infinie

    Citation Envoyé par hedonyPower Voir le message
    Oui, j'y avais pensé... mais cela signifie que l'ensemble des feuilles de l'arborescence est indénombrable...
    Ben oui...

    Et si on considère la procédure qui consiste à parcourir l'arborescence en largeur et attribuer à chaque sommet le successeur de l'entier attribué au sommet précédent (sachant qu'on a attribué 0 à la racine), n'a-t-on pas là une procédure de dénombrement des sommets de l'arborescence ?
    Qu'appelles-tu "parcourir en largeur"? Je pense qu'en cherchant à définir précisément ce que tu cherches à dire, tu devrais découvrir une difficulté.

    Par exemple, quelle est la suite du parcours immédiatement après la feuille correspondant à "toujours 0" (ou toujours à gauche, selon ta description)?

    Cordialement,

  9. #7
    Médiat

    Re : Arborescence infinie

    Citation Envoyé par hedonyPower Voir le message
    Et si on considère la procédure qui consiste à parcourir l'arborescence en largeur et attribuer à chaque sommet le successeur de l'entier attribué au sommet précédent (sachant qu'on a attribué 0 à la racine), n'a-t-on pas là une procédure de dénombrement des sommets de l'arborescence ?

    Comme les feuilles sont des sommets de cette arborescence elles sont dénombrables non ? et on obtient une contradiction non ?
    C'est comme si tu proposais de compter les réels dans [0 ; 1[ en comptant d'abord ceux qui n'ont pas de décimales (en base 10), puis ceux qui ont 1 décimale, etc. et pourtant l'intervalle [0 ; 1[ n'est pas dénombrable.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  10. Publicité
  11. #8
    hedonyPower

    Re : Arborescence infinie

    Re-bonjour et merci pour les réponses,

    mon idée c'est d'attribuer l'entier m à tout sommet s de l'arborescence en fonction de l'entier n attribué à son père et tel que :

    - m=2*n ssi s est un fils gauche
    - m=2*n+1 ssi s est un fils droit

    (cela revient à parcourir l'arborescence en largeur : à chaque profondeur n on commence par la gauche et on termine par le sommet à droite)

    On peut prouver par récurrence qu'on peut attribuer un tel entier à tout sommet de l'arborescence (puisque chaque sommet est soit fils droit soit fils gauche d'un sommet auquel on a déjà attribué un entier).

    Une feuille possède aussi un père auquel on a attribué cet entier non ? Du coup on peut la dénombrer de la même façon...
    Je me doute bien qu'il y a une erreur quelque part mais je ne la vois pas !

    qu'en pensez vous

  12. #9
    invité576543
    Invité

    Re : Arborescence infinie

    J'ai écrit [0,1] et non pas [0,1[ après mûre réflexion.

    Cordialement,

  13. #10
    Médiat

    Re : Arborescence infinie

    Citation Envoyé par hedonyPower Voir le message
    Une feuille possède aussi un père auquel on a attribué cet entier non ? Du coup on peut la dénombrer de la même façon...
    Je me doute bien qu'il y a une erreur quelque part mais je ne la vois pas !
    De la même façon qu'il n'y a qu'un nombre fini de réels ayant toutes les décimales après la 100 000 ième égales à 0...
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  14. #11
    invité576543
    Invité

    Re : Arborescence infinie

    Citation Envoyé par hedonyPower Voir le message
    Re-bonjour et merci pour les réponses,

    mon idée c'est d'attribuer l'entier m à tout sommet s de l'arborescence en fonction de l'entier n attribué à son père et tel que :

    - m=2*n ssi s est un fils gauche
    - m=2*n+1 ssi s est un fils droit
    Cela donne un nombre infini pour toutes les feuilles sauf à la toute à gauche.

    On peut prouver par récurrence qu'on peut attribuer un tel entier à tout sommet de l'arborescence (puisque chaque sommet est soit fils droit soit fils gauche d'un sommet auquel on a déjà attribué un entier).
    Uniquement à tous les noeuds de l'arborescence. Pas aux feuilles. Ta récurrence ne peut pas parler d'autre chose que des noeuds.

    Une feuille possède aussi un père auquel on a attribué cet entier non ?
    Non, et c'est ça la difficulté. Une feuille n'a pas de père, parce que les noeuds ont pour fils des noeuds, jamais des feuilles.

    Cordialement,

  15. #12
    hedonyPower

    Re : Arborescence infinie

    En fait, peut-on dire que l'ensemble des feuilles de l'arborescence n'existe pas ? et que dès qu'on suppose l'existence d'une feuille on peut trouver un sommet dont elle est le père ?

    Cette manière de voir est-elle juste ?

    Mais dans ce cas, que dire de l'ensemble des sommets de l'arborescence que j'ai mis en bijection avec les points du segment (0,0) -> (0,2) (avec la fractale ?)...

    Peut-on dire qu'ils existent mais qu'il est impossible d'en exiber n'en serait-ce qu'un seul ?

  16. #13
    invité576543
    Invité

    Re : Arborescence infinie

    Citation Envoyé par hedonyPower Voir le message
    En fait, peut-on dire que l'ensemble des feuilles de l'arborescence n'existe pas ?
    Si on peut en donner une définition utilisable de manière cohérente, il existe! C'est la magie des maths...

    et que dès qu'on suppose l'existence d'une feuille on peut trouver un sommet dont elle est le père ?
    Tu n'es pas d'accord avec l'affirmation que les deux fils d'un sommet sont aussi des sommets et pas des feuilles?

    C'est l'intervention de l'infini qui donne un statut spécial aux feuilles: ce ne sont pas des fils de sommet, mais autre chose.

    Peut-on dire qu'ils existent mais qu'il est impossible d'en exiber n'en serait-ce qu'un seul ?
    C'est facile d'en exhiber pas mal. Celle qui est l'aboutissement de la branche "toujours à gauche". Celle de la branche "toujours à droite". Celle de la branche "à gauche six fois, puis ensuite toujours à droite". Celle de la branche "à gauche puis à droite alternativement".

    C'est la même relation qu'entre réels et rationnels. On peut exhiber facilement des rationnels dans un intervalle réel, mais l'intervalle réel n'est pas dénombrable.

    Cordialement,
    Dernière modification par invité576543 ; 19/09/2007 à 14h55.

  17. #14
    hedonyPower

    Re : Arborescence infinie

    Hmmm...

    Quelque chose m'échappe décidément...
    Car je n'ai définit mon arborescence qu'avec un ensemble infini de sommets dont chacun est le père de l'autre et je me retrouve avec des sommets d'une autre nature qui n'ont plus de père... J'ai les oreilles qui fument là...

    Bon ... je me rends compte que je joue avec l'infini comme avec le feu (et je n'y vois que du feu)...

    En tous cas, Merci à tous pour vos réponses !

    Bonne continuation

  18. #15
    invité576543
    Invité

    Re : Arborescence infinie

    Citation Envoyé par hedonyPower Voir le message
    Quelque chose m'échappe décidément...
    L'infini, ce n'est pas facile!

    Car je n'ai définit mon arborescence qu'avec un ensemble infini de sommets dont chacun est le père de l'autre
    Tu peux très bien définir l'arbre comme cela. Mais cela ne suffit pas pour parler de feuilles. Dans un tel arbre, il n'y a que des sommets. Et chaque sommet sauf le premier a un père et deux fils.

    Si tu conçois une feuille comme n'ayant pas de fils, ça ne peut pas être un élément de cet arbre-là: il n'a que des sommets, et aucune feuille.

    (Dans l'analogie avec réels/rationnels, cela correspond aux "nombres binaux" par analogie aux nombres décimaux, les nombres qui s'écrivent avec un nombre fini de chiffres binaires après la virgule. C'est une partie des rationnels.)

    et je me retrouve avec des sommets d'une autre nature qui n'ont plus de père... J'ai les oreilles qui fument là...
    Les feuilles, vu comme "la limite à l'infini du processus" ne sont pas des sommets d'une autre nature. Elles s'ajoutent aux sommets, et proviennent du passage à la limite.

    (Dans l'analogie avec réels/rationnels, ajouter les feuilles c'est comme compléter les nombres binaux avec les autres réels. C'est similaire au passage de Q à R. Les réels ajoutés ne sont pas des binaux, de même que les feuilles ne sont pas des sommets.)

    Cordialement,

  19. #16
    Médiat

    Re : Arborescence infinie

    Citation Envoyé par hedonyPower Voir le message
    On peut prouver par récurrence qu'on peut attribuer un tel entier à tout sommet de l'arborescence (puisque chaque sommet est soit fils droit soit fils gauche d'un sommet auquel on a déjà attribué un entier).

    Une feuille possède aussi un père auquel on a attribué cet entier non ? Du coup on peut la dénombrer de la même façon...
    Je me doute bien qu'il y a une erreur quelque part mais je ne la vois pas !
    Je ne sais pas si cela va te permettre une meilleure intuition, mais tu ne dois pas oublier que la réunion de toutes les suites de longueur fini (à support fini serait un meilleur vocabulaire) ne contient aucune suite de longueur infinie...
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  20. #17
    Médiat

    Re : Arborescence infinie

    Pour essayer d'être un peu plus clair qu'hier soir, tu as deux façons extrêmement différentes de construire ton arbre :
    • tu construis un arbre qui est la réunion de tous les arbres de longueur n pour tout n (c'est à dire un arbre qui est la réunion de tous les arbres finis), là on peut dire
      • que chaque feuille est rattachée à un sommet (son prédécesseur)
      • tu peux parcourir ton arbre en largeur (tu peux compter les décimaux)
      • l'arbre réunion est dénombrable
    • tu t'autorises les branches de longueur et on peut dire
      • les feuilles ne sont pas rattachées à un sommet (pas de prédécesseur)
      • tu ne peux pas parcourir ton arbre en largeur, car tu n'atteindras jamais les branches de longueur infinie (tu ne peux pas compter les réels)
      • l'arbre réunion n'est pas dénombrable
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  21. #18
    invité576543
    Invité

    Re : Arborescence infinie

    Une petite remarque supplémentaire, dans le cas de l'arbre infini avec feuilles, les feuilles ont des ancètres, mais pas de père!

    La relation qui reste entre sommets et feuille est "le sommet s fait partie des ancêtres de la feuille f". C'est cette relation qui permet une structure commune entre sommets et feuilles, une sorte d'arbre, mais différente d'un arbre fini.

    Ainsi, un sommet à deux fils, un nombre fini de sommets ancêtres, et s'il a au moins un ancêtre, il a un sommet père; ça, c'est commun à toutes les structures d'arbres. Un sommet a un nombre infini de descendants, dont un nombre infini dénombrable de sommets et un nombre infini non dénombrable de feuilles.

    Une feuille a un nombre infini (dénombrable) de sommets ancêtres, mais pas de père. Pour toute paire de sommets ancêtres d'une même feuille, l'un est l'ancêtre de l'autre. (Réciproquement, si on a un ensemble infini de sommets telle que pour toute paire de sommets de l'ensemble, l'un est l'ancêtre de l'autre, alors il y a une et une seule feuille dont ces sommets sont tous des ancêtres.)

    ---

    Un arbre fini (avec feuilles donc), l'arbre infini avec feuilles et l'arbre infini sans feuille sont trois structures différentes, et le mot "feuille" dans le cas fini ne réfère pas exactement à la même chose que le mot feuille dans le cas infini. (Les deux notions de feuille partagent les propriétés de ne pas avoir de fils et d'avoir des ancêtres, mais la notion de père, ou d'être à gauche ou à droite du père, n'existe que dans le cas fini. Dans le cas fini une feuille est définie par sa liste d'ancêtres et par sa position (gauche ou droite); dans le cas infini, une feuille est définie par sa liste d'ancêtres.

    Prendre conscience de la différence entre les trois structures, et des différentes significations du mot feuille devrait permettre de lever la confusion.

    Cordialement,

  22. #19
    hedonyPower

    Re : Arborescence infinie

    Merci à tous pour vos réponses, c'est effectivement beaucoup plus clair maintenant.
    A bientot

Sur le même thème :

Discussions similaires

  1. imprimer une arborescence
    Par abracadabra75 dans le forum Logiciel - Software - Open Source
    Réponses: 21
    Dernier message: 21/11/2005, 16h29
  2. lecteur mp3 et arborescence
    Par planck dans le forum Matériel - Hardware
    Réponses: 0
    Dernier message: 29/06/2005, 14h31