Quelle est la formule pour trouver les différents arbres non étiquetés qui peuvent être formés à partir d'un ensemble donné de nœuds?

Je fais juste une recherche sur un projet et j'ai rencontré un problème. Je serais très reconnaissant si quelqu'un pouvait m'aider avec ça. Considérons la figure ci-dessous:Quelle est la formule pour trouver les différents arbres non étiquetés qui peuvent être formés à partir d'un ensemble donné de nœuds?

enter image description here

Deux points reliés par un résultat en ligne dans un seul diagramme, trois points reliés par des lignes simples entraîne également une figure peu importe comment vous joindre les points, le résultat est le même . Mais comme nous augmentons les points, il y a différentes possibilités, comme on le voit avec quatre points.

Existe-t-il une formule pour compter le nombre d'arbres non étiquetés pouvant être formés à partir d'un ensemble de nœuds?

Source

2011-02-21 jarus

Cela ressemble à un problème de devoirs, donc je ne répondrai pas directement. Cependant, pour vous montrer du doigt, il semble que vous parlez de quelque chose lié à des «graphiques aléatoires». – bblack

Aussi probablement plus adapté à http://math.stackexchange.com/ vu comme c'est la formule? Plutôt que de le programmer? – dbjohn

Pourquoi trois points ne donnent pas deux chiffres?Est-ce que la règle selon laquelle le premier point ne peut avoir qu'une seule ligne en sort? –

Il s'agit d'un problème de nombre de graphes non-isomorphes.

Pour le cas général, il y a 2^(n ) graphes non isomorphes sur n sommets où (n ) est coefficient binomial "n supérieur à 2". Toutefois, cela peut également vous donner des graphiques supplémentaires en fonction des graphiques considérés comme identiques (vous n'étiez pas non plus sûr à 100% quels graphiques s'appliquent).

See this paper. And this article on MathWorld.

EDIT: Si vous souhaitez compter les arbres étiquetés, seule la formule est n^(n-2).

Wikipedia.

Source

2011-02-21 19:52:49

Merci pour la réponse. – jarus

Vous voulez probablement le nombre d'arbres avec n nœuds non étiquetés: http://oeis.org/A000055 –

Comme indiqué par mzabsky ci-dessus, le nombre d'arbres couvrant d'un graphique complet est donné par n^(n-2) (Cayley ?). Dans Mma 7, il y a une commande 'NumberOfSpanningTrees' dans le paquet Combinatorica qui pourrait être utile. Peut-être mis à jour dans Mma8. Par exemple Needs ["Combinatorica"]; NumberOfSpanningTrees [CompleteGraph [4]] donne 16 (comme prévu). Vous pouvez bénéficier de Mathematica/Combinatorica. – tomd

Comme suggéré dans les commentaires, votre question peut être formulée comme la détermination du nombre d'arbres non marqués sur n sommets. Notez que ceci diffère significativement de la question de compter arbres étiquetés (dont il existe n^{n-2}) ou graphes étiquetés (dont il existe 2^\ binom {n} {2}).

L'Encyclopédie en ligne des séquences entières contient beaucoup de bonnes données sur ce problème (y compris le code pour générer la séquence): https://oeis.org/A000055. En particulier, il donne une fonction génératrice A (x) pour ces nombres, qui est la meilleure solution connue à ce jour (du point de vue mathématicien):

A (x) = 1 + T (x) - T^2 (x)/2 + T (x^2)/2, où T (x) = x + x^2 + 2x^3 + ...

Si vous ne connaissez pas les fonctions génératrices, pensez-y comme un polynôme soigneusement conçu dont les coefficients forment la séquence désirée. C'est-à-dire que le coefficient de x^n dans ce polynôme serait le nombre d'arbres non étiquetés sur n sommets.

Comme une dernière prise, vous pouvez trouver cette référence utile: http://austinmohr.com/work/trees. Il donne quelques chiffres et images pour les arbres de dix sommets maximum.

Source

2013-02-15 05:20:32

Quelle est la formule pour trouver les différents arbres non étiquetés qui peuvent être formés à partir d'un ensemble donné de nœuds?

Répondre

Questions connexes