Hispanopedia Wiki
En combinatoria y teoría del orden , un multiárbol puede describir cualquiera de dos estructuras equivalentes: un gráfico acíclico dirigido (DAG) en el que hay como máximo un camino dirigido entre dos vértices cualesquiera , o equivalentemente en el que el subgráfico alcanzable desde cualquier vértice induce un árbol no dirigido , o un conjunto parcialmente ordenado (poset) que no tiene cuatro elementos a , b , c y d formando un suborden de diamante con a ≤ b ≤ d y a ≤ c ≤ d pero con b y c incomparables entre sí (también llamado un poset libre de diamante [1] ).
En la teoría de la complejidad computacional , los multiárboles también se han denominado gráficos fuertemente inequívocos o manglares ; se pueden utilizar para modelar algoritmos no deterministas en los que hay como máximo una ruta computacional que conecta dos estados cualesquiera. [2]
Los multiárboles se pueden utilizar para representar múltiples taxonomías superpuestas sobre el mismo conjunto base. [3] Si un árbol genealógico puede contener múltiples matrimonios de una familia con otra, pero no contiene matrimonios entre dos parientes consanguíneos, entonces forma un multiárbol. [4]
Equivalencia entre las definiciones de DAG y poset
En un grafo acíclico dirigido, si hay como máximo un camino dirigido entre dos vértices cualesquiera, o equivalentemente, si el subgrafo alcanzable desde cualquier vértice induce un árbol no dirigido, entonces su relación de alcanzabilidad es un orden parcial sin rombos. Por el contrario, en un orden parcial sin rombos, la reducción transitiva identifica un grafo acíclico dirigido en el que el subgrafo alcanzable desde cualquier vértice induce un árbol no dirigido.
Familias sin diamantes
Una familia de conjuntos sin diamantes es una familia F de conjuntos cuyo orden de inclusión forma un conjunto parcial sin diamantes. Si D ( n ) denota la mayor familia posible de subconjuntos sin diamantes de un conjunto de n elementos, entonces se sabe que
- ,
y se conjetura que el límite es 2. [1]
Estructuras relacionadas
Un poliárbol , un gráfico acíclico dirigido formado al orientar los bordes de un árbol no dirigido, es un caso especial de un multiárbol.
El subgrafo accesible desde cualquier vértice de un multiárbol es una arborescencia enraizada en el vértice, es decir, un poliárbol en el que todos los bordes están orientados lejos de la raíz.
La palabra "multiárbol" también se ha utilizado para referirse a un orden parcial serie-paralelo , [5] o a otras estructuras formadas mediante la combinación de múltiples árboles.
Referencias
- ^ ab 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 )", Algorithms and Computation, 7.º Simposio Internacional, ISAAC '96, Osaka, Japón, 16-18 de diciembre de 1996, Actas , Lecture Notes in Computer Science, vol. 1178, Springer-Verlag, págs. 193-202, doi :10.1007/BFb0009495 .
- ^ Furnas, George W. ; Zacks, Jeff (1994), "Multitrees: 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, California, EE. UU.: IEEE Computer Society, pág. 3, doi : 10.1109/INFOVIS.2005.22, S2CID 15449409.
- ^ Jung, HA (1978), "Sobre una clase de conjuntos parciales 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.