Si nous considérons un arbre comme un ensemble ordonné partiel, il devient un cas particulier de jointure-semi-réseau. Pour un joint-semi-réseau, nous voulons être capables de calculer la limite supérieure (unique) la moins haute de deux éléments (plus ou moins) efficacement. Dans le cas d'un arbre, une structure de données qui permettrait cela serait de stocker pour chaque élément dans le nœud correspondant un pointeur vers le parent et une mesure de distance vers la racine. (En fait, un étiquetage basé sur un tri topologique habituellement utilisé pour "une mesure de distance à la racine", en fait tout ce qui est nécessaire est un ordre partiel compatible qui peut être évalué efficacement).
Chaque jointure-semi-réseau fini peut être représenté comme un ensemble de sous-ensembles d'un ensemble fini avec confinement dans l'ordre de telle sorte que la plus petite borne supérieure soit donnée par l'union des ensembles. Par conséquent, la représentation de chaque élément par un nombre fini d'étiquettes et le calcul de la limite inférieure la plus haute par l'union des étiquettes correspondantes seraient une structure de données possible. (En regardant le complément, on voit qu'il serait également possible de définir la borne inférieure la plus basse comme intersection des balises correspondantes.) Une structure de données beaucoup plus courante consiste simplement à utiliser une matrice pour stocker tous les résultats de "a <= b "ou même tous les résultats de" join (a, b) ".
Cependant, utiliser une telle structure de données pour représenter un arbre serait assez étrange. Existe-t-il plus de structures de données arborescentes pour les demi-réseaux de jointures, qui permettent toujours (plus ou moins) un calcul efficace de la limite la plus haute (unique) de deux éléments? (Peut-être une sorte de graphique acyclique dirigé avec des informations supplémentaires dans les nœuds, similaire à la mesure de la distance à la racine de l'arbre?)
la source
Réponses:
Ce billet de blog sur la théorie des réseaux a une section de référence utile, qui contient entre autres "La théorie des réseaux avec applications" par Vijay K. Garg. Le chapitre 2 «Représentation des posets» décrit certaines structures de données pour représenter les posets et explique comment calculer la jointure (x, y) à l'aide d'une telle structure de données.
Les deux premières structures de données discutées sont la représentation de liste d'adjacence du graphe de réduction transitive (= diagramme de Hasse / relation de couverture) et le graphe de fermeture transitive (= relation de poset). Une remarque sur les avantages de l'utilisation d'un tri topologique pour étiqueter les nœuds précède cette discussion. Notez que les étiquettes de tri topologique seraient assez bonnes comme "une mesure de distance à la racine", qui était une partie de la structure de données pour un arbre dans la question.
Les autres représentations discutées sont "Représentation squelettique", "Représentation matricielle" et "Représentation basée sur les dimensions". La "représentation squelettique" est intéressante et utile, mais basée sur une (= toute) décomposition en chaîne du poset. La «représentation matricielle» peut sembler banale, mais c'est probablement la meilleure représentation pour la plupart des problèmes pratiques. La "représentation basée sur les dimensions" représente le poset comme le sous-ensemble du produit cartésien d'ordres linéaires, mais le calcul de la représentation minimale de ce type est NP-difficile.
En conclusion, la représentation la plus arborescente de celles-ci est la représentation de la liste d'adjacence de la réduction transitive avec un étiquetage des nœuds par un tri topologique (au lieu de "une mesure de distance à la racine"). C'est en fait l'une des représentations utilisées par Sage (l'autre est la "représentation matricielle").
la source