Polytree - Polytree
v matematika a konkrétněji v teorie grafů, a polytree[1] (také zvaný řízený strom,[2] orientovaný strom[3][4] nebo jednotlivě připojená síť[5]) je směrovaný acyklický graf jehož podkladový neorientovaný graf je a strom. Jinými slovy, pokud jej vyměníme směrované hrany s neorientovanými hranami získáme neorientovaný graf, který je obojí připojeno a acyklický.
A polyforest (nebo řízený les nebo orientovaný les) je směrovaný acyklický graf, jehož podkladový neorientovaný graf je a les. Jinými slovy, pokud nahradíme jeho směrované hrany neorientovanými hranami, získáme neorientovaný graf, který je acyklický.
Polytree je příkladem orientovaný graf.
Termín polytree byl vytvořen v roce 1987 Rebane a Perla.[6]
Související struktury
- An stromovost je řízený kořen strom, tj. a směrovaný acyklický graf ve kterém existuje jediný zdrojový uzel, který má jedinečnou cestu ke každému dalšímu uzlu. Každý arborescence je polytree, ale ne každý polytree je arborescence.
- A multitree je směrovaný acyklický graf, ve kterém podgraf dosažitelný z kteréhokoli uzlu tvoří strom. Každý polytree je a multitree.
- The dosažitelnost vztah mezi uzly polytree tvoří a částečná objednávka to má dimenze objednávky maximálně tři. Pokud je dimenze objednávky tři, musí existovat podmnožina sedmi prvků X, yi, a zi (pro i = 0, 1, 2) takové, že pro každého i, buď X ≤ yi ≥ zinebo X ≥ yi ≤ zi, s těmito šesti nerovnostmi definujícími strukturu polytree na těchto sedmi prvcích.[7]
- A plot nebo klikatá poset je speciální případ polystromu, ve kterém je podkladovým stromem cesta a hrany mají orientace, které se podél cesty střídají. The dosažitelnost objednávání v polytree bylo také nazýváno a zobecněný plot.[8]
Výčet
Počet zřetelných stromů na n neoznačené uzly pro n = 1, 2, 3, ..., je
Sumnerova domněnka
Sumnerova domněnka, pojmenované po Davidovi Sumnerovi, to uvádí turnaje jsou univerzální grafy pro polytrees v tom smyslu, že každý turnaj s 2n - 2 vrcholy obsahují každý polystrom s n vrcholy jako podgraf. Přestože zůstává nevyřešen, bylo prokázáno pro všechny dostatečně velké hodnoty n.[9]
Aplikace
Polytromy byly použity jako a grafický model pro pravděpodobnostní uvažování.[1] Pokud Bayesovská síť má tedy strukturu polystromu šíření víry může být použito k účinnému provedení závěru na něm.[5][6]
The obrysový strom funkce se skutečnou hodnotou na a vektorový prostor je polystrom, který popisuje sady úrovní funkce. Uzly stromu obrysu jsou sady úrovní, které procházejí a kritický bod funkce a hrany popisují souvislé sady úrovní bez kritického bodu. Orientace hrany je určena porovnáním hodnot funkcí na odpovídajících dvou úrovních.[10]
Viz také
Poznámky
- ^ A b Dasgupta (1999).
- ^ Deo 1974, str. 206.
- ^ Harary & Sumner (1980).
- ^ Simion (1991).
- ^ A b Kim & Pearl (1983).
- ^ A b Rebane & Pearl (1987).
- ^ Trotter & Moore (1977).
- ^ Ruskey, Frank (1989), „Generování transpozice střídavých permutací“, Objednat, 6 (3): 227–233, doi:10.1007 / BF00563523, PAN 1048093
- ^ Kühn, Mycroft & Osthus (2011).
- ^ Carr, Snoeyink & Axen (2000).
Reference
- Carr, Hamish; Snoeyink, Jacku; Axen, Ulrike (2000), „Výpočet vrstevnicových stromů ve všech rozměrech“, v Proc. 11. ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), str. 918–926
- Dasgupta, Sanjoy (1999), „Learning polytrees“, v Proc. 15. konference o nejistotě v umělé inteligenci (UAI 1999), Stockholm, Švédsko, červenec-srpen 1999 (PDF), str. 134–141.
- Deo, Narsingh (1974), Teorie grafů s aplikacemi ve strojírenství a informatice (PDF), Englewood, New Jersey: Prentice-Hall, ISBN 0-13-363473-6.
- Harary, Franku; Sumner, David (1980), „Dichromatické číslo orientovaného stromu“, Journal of Combinatorics, Information & System Sciences, 5 (3): 184–187, PAN 0603363.
- Kim, Jin H .; Pearl, Judea (1983), „Výpočtový model pro kauzální a diagnostické uvažování v inferenčních motorech“, v Proc. 8. mezinárodní společná konference o umělé inteligenci (IJCAI 1983), Karlsruhe, Německo, srpen 1983 (PDF), s. 190–193.
- Kühn, Daniela; Mycroft, Richard; Osthus, Deryk (2011), „Důkaz o Sumnerově univerzální domněnce o turnaji pro velké turnaje“, Proceedings of the London Mathematical Society Třetí série, 102 (4): 731–766, arXiv:1010.4430, doi:10.1112 / plms / pdq035, PAN 2793448.
- Rebane, George; Pearl, Judea (1987), „Obnova kauzálních poly stromů ze statistických údajů“, v Proc. 3. výroční konference o nejistotách v umělé inteligenci (UAI 1987), Seattle, WA, USA, červenec 1987 (PDF), s. 222–228[trvalý mrtvý odkaz ].
- Simion, Rodica (1991), "Stromy s 1 faktory a orientované stromy", Diskrétní matematika, 88 (1): 93–104, doi:10.1016 / 0012-365X (91) 90061-6, PAN 1099270.
- Trotter, William T., Jr.; Moore, John I., Jr. (1977), „Dimenze rovinných posetů“, Journal of Combinatorial Theory, Řada B, 22 (1): 54–67, doi:10.1016 / 0095-8956 (77) 90048-X.