En combinatoria y matemática teórica del orden , un árbol múltiple puede describir cualquiera de dos estructuras equivalentes: un grafo acíclico dirigido (DAG) en el que el conjunto de vértices alcanzables desde cualquier vértice induce un árbol , o un conjunto parcialmente ordenado (poset) que no tener cuatro artículos un , b , c , y d formando un suborden de diamante con un ≤ b ≤ d y un ≤ c ≤ d pero con b y cincomparables entre sí (también llamado poset sin diamantes [1] ).
En la teoría de la complejidad computacional , los árboles múltiples también se han denominado gráficos o manglares fuertemente inequívocos ; se pueden usar para modelar algoritmos no deterministas en los que hay como máximo una ruta computacional que conecta dos estados cualesquiera. [2]
Los árboles múltiples se pueden utilizar para representar múltiples taxonomías superpuestas sobre el mismo conjunto de bases. [3] Si un árbol genealógico puede contener múltiples matrimonios de una familia a otra, pero no contiene matrimonios entre dos parientes consanguíneos, entonces forma un árbol múltiple. [4]
Equivalencia entre las definiciones de DAG y poset
En un grafo acíclico dirigido, si el conjunto de vértices alcanzables desde cualquier vértice induce un árbol, o de manera equivalente si hay como máximo una ruta dirigida entre dos vértices cualesquiera en cualquier dirección, entonces su relación de accesibilidad es un orden parcial sin diamantes. Por el contrario, en un orden parcial, si no tiene diamantes, entonces su reducción transitiva identifica un grafo acíclico dirigido en el que el conjunto de vértices alcanzables desde cualquier vértice induce un árbol.
Familias sin diamantes
Una familia de conjuntos sin diamantes es una familia F de conjuntos cuyo orden de inclusión forma un conjunto sin diamantes. Si D ( n ) denota la familia de subconjuntos sin diamantes más grande posible de un conjunto de n elementos, entonces se sabe que
y se conjetura que el límite es 2. [1]
Estructuras relacionadas
A poliárbol , un gráfico acíclico dirigido formado mediante la asignación de una orientación a cada borde de un árbol no dirigido, se puede ver como un caso especial de un MultiTree.
El conjunto de todos los vértices conectados a cualquier vértice en un árbol múltiple forma una arborescencia .
La palabra "multitree" también se ha utilizado para referirse a un orden parcial serie-paralelo , [5] u otras estructuras formadas mediante la combinación de varios árboles.
Referencias
- ↑ a b Griggs, Jerrold R .; Li, Wei-Tian; Lu, Linyuan (2010), Familias sin diamantes , arXiv : 1010.5311 , Bibcode : 2010arXiv1010.5311G.
- ^ Allender, Eric ; Lange, Klaus-Jörn (1996), "StUSPACE (log n ) ⊆ DSPACE (log 2 n / log log n )", Algoritmos y Computación, Séptimo Simposio Internacional, ISAAC '96, Osaka, Japón, 16-18 de diciembre de 1996 , Actas , Lecture Notes in Computer Science, 1178 , Springer-Verlag, págs. 193–202, doi : 10.1007 / BFb0009495.
- ^ Furnas, George W .; Zacks, Jeff (1994), "Multiárboles: enriquecimiento y reutilización de la estructura jerárquica", Proc. Conferencia SIGCHI sobre factores humanos en sistemas informáticos (CHI '94) , págs. 330–336, doi : 10.1145 / 191666.191778 , S2CID 18710118.
- ^ McGuffin, Michael J .; Balakrishnan, Ravin (2005), "Visualización interactiva de gráficos genealógicos", Simposio IEEE sobre visualización de información , Los Alamitos, CA, EE.UU .: IEEE Computer Society, p. 3, doi : 10.1109 / INFOVIS.2005.22 , S2CID 15449409.
- ^ Jung, HA (1978), "Sobre una clase de posets y los gráficos de comparabilidad correspondientes", Journal of Combinatorial Theory, Serie B , 24 (2): 125-133, doi : 10.1016 / 0095-8956 (78) 90013-8 , MR 0491356.