Multitree - Multitree
v kombinatorika a teoretický řád matematika, a multitree může popisovat jednu ze dvou ekvivalentních struktur: a směrovaný acyklický graf (DAG), ve kterém množina vrcholů dosažitelných z jakéhokoli vrcholu indukuje a strom nebo částečně objednaná sada (poset), který nemá čtyři položky A, b, C, a d tvořící diamantový podřád s A ≤ b ≤ d a A ≤ C ≤ d ale s b a C navzájem nesrovnatelné (nazývané také a Poset bez diamantů[1]).
v teorie výpočetní složitosti, byly také nazývány multitromy silně jednoznačné grafy nebo mangrovy; mohou být použity k modelování nedeterministické algoritmy ve kterém je nanejvýš jedna výpočetní cesta spojující jakékoli dva stavy.[2]
Více stromů lze použít k reprezentaci vícenásobného překrývání taxonomie na stejné zemi.[3] Pokud rodokmen může obsahovat více manželství z jedné rodiny do druhé, ale neobsahuje manželství mezi dvěma pokrevními příbuznými, pak tvoří multitree.[4]
Ekvivalence mezi DAG a definicemi posetů
V orientovaném acyklickém grafu, pokud množina vrcholů dosažitelných z jakéhokoli vrcholu vyvolá strom, nebo ekvivalentně, pokud existuje maximálně jedna směrovaná cesta mezi dvěma vrcholy v obou směrech, pak jeho dosažitelnost relace je částečná objednávka bez diamantů. Naopak, v částečném pořadí, pokud je bez diamantů, pak jeho přechodná redukce identifikujte směrovaný acyklický graf, ve kterém sada vrcholů dosažitelných z jakéhokoli vrcholu vyvolá strom
Rodiny bez diamantů
Bez diamantů rodina sad je rodina F sad, jejichž objednávání zařazení tvoří poset bez diamantů. Li D(n) označuje největší možnou rodinu podmnožin bez diamantů n- sada prvků, pak je známo, že
a předpokládá se, že limit je 2.[1]
Související struktury
A polytree, zaměřený acyklický graf vytvořený přiřazením orientace ke každému okraji neorientovaného stromu, lze považovat za zvláštní případ multitree.
Sada všech vrcholů připojených k jakémukoli vrcholu v multitree tvoří stromovost.
Slovo „multitree“ se také používá k označení a sériově paralelní dílčí řád,[5] nebo do jiných struktur vytvořených kombinací více stromů.
Reference
- ^ A b Griggs, Jerrold R .; Li, Wei-Tian; Lu, Linyuan (2010), Rodiny bez diamantů, arXiv:1010.5311, Bibcode:2010arXiv1010.5311G.
- ^ Allender, Eric; Lange, Klaus-Jörn (1996), „StUSPACE (log n) ⊆ DSPACE (log2 n/ log log n)", Algorithms and Computation, 7. mezinárodní sympozium, ISAAC '96, Osaka, Japonsko, 16. – 18. Prosince 1996, sborník, Přednášky v informatice, 1178, Springer-Verlag, str. 193–202, doi:10.1007 / BFb0009495.
- ^ Furnas, George W.; Zacks, Jeff (1994), „Multitrees: obohacení a opětovné použití hierarchické struktury“, Proc. Konference SIGCHI o lidských faktorech ve výpočetních systémech (CHI '94), str. 330–336, doi:10.1145/191666.191778.
- ^ McGuffin, Michael J .; Balakrishnan, Ravin (2005), „Interaktivní vizualizace genealogických grafů“, Sympozium IEEE o vizualizaci informací„Los Alamitos, CA, USA: IEEE Computer Society, s. 3–3, doi:10.1109 / INFOVIS.2005.22.
- ^ Jung, H. A. (1978), „O třídě posetů a odpovídajících grafech srovnatelnosti“, Journal of Combinatorial Theory, Řada B, 24 (2): 125–133, doi:10.1016/0095-8956(78)90013-8, PAN 0491356.