Polytree - Polytree
V matematice a konkrétněji v teorii grafů je polytree (nazývaný také směrovaný strom , orientovaný strom nebo jednotlivě připojená síť ) směrovaný acyklický graf, jehož podkladovým neřízeným grafem je strom . Jinými slovy, pokud nahradíme jeho směrované hrany neorientovanými hranami, získáme neorientovaný graf, který je propojený i acyklický .
Polyforest (nebo směřuje lesní nebo orientovaný les ) je orientovaný acyklický graf, jehož základní neorientovaný graf je 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ého grafu .
Termín polytree byl vytvořen v roce 1987 Rebane a Pearl .
Související struktury
- Stromová je zaměřen kořeny stromů , tj orientovaný acyklický graf , ve kterém existuje jediný zdrojový uzel, který má jedinečnou cestu ke každému jinému uzlu. Každý arborescence je polytree, ale ne každý polytree je arborescence.
- Multitree je orientovaný acyklický graf, ve kterém je subgraph dosažitelný z kteréhokoliv uzlu tvoří strom. Každý polytree je multitree .
- Vztah dosažitelnosti mezi uzly polytree tvoří částečný řád, který má dimenzi řádu nejvýše tři. Pokud je dimenze řádu tři, musí existovat podmnožina sedmi prvků x , y i a z i (pro i = 0, 1, 2 ) tak, aby pro každé i buď x ≤ y i ≥ z i , nebo x ≥ y i ≤ z i , přičemž těchto šest nerovností definuje strukturu polytree na těchto sedmi prvcích.
- Plot nebo cik-cak poset je zvláštní případ polytree ve kterém je základní strom je cesta a hrany mají směry, které se střídají podél cesty. Dosažitelnost uspořádání v polytree byl také nazýván zobecněný plot .
Výčet
Počet odlišných polytromů na n neoznačených uzlech pro n = 1, 2, 3, ... je
Sumnerova domněnka
Sumnerova domněnka , pojmenovaná po Davidovi Sumnerovi, uvádí, že turnaje jsou univerzální grafy pro polytromy, v tom smyslu, že každý turnaj s 2 n - 2 vrcholy obsahuje každý polytree s n vrcholů jako podgraf. Přestože zůstává nevyřešen, bylo prokázáno pro všechny dostatečně velké hodnoty n .
Aplikace
Polytromy byly použity jako grafický model pro pravděpodobnostní uvažování . Pokud má Bayesiánská síť strukturu polystromu, pak lze použít šíření víry k účinnému provedení závěru na ní.
Obrys strom z funkce skutečný-cenil na vektorový prostor je polytree který popisuje sady úrovně funkce. Uzly stromu obrysu jsou sady úrovní, které procházejí kritickým bodem funkce a hrany popisují souvislé sady sad úrovní bez kritického bodu. Orientace hrany je určena porovnáním hodnot funkcí na odpovídajících dvou úrovních.
Viz také
Poznámky
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) , s. 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, Frank ; Sumner, David (1980), „Dichromatické číslo orientovaného stromu“, Journal of Combinatorics, Information & System Sciences , 5 (3): 184–187, MR 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 Sumnerova univerzálního dohadu 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 , MR 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.
- Simion, Rodica (1991), „Stromy s 1 faktory a orientovanými stromy“, Diskrétní matematika , 88 (1): 93–104, doi : 10,1016 / 0012-365X (91) 90061-6 , MR 1099270.
- Trotter, William T., Jr.; Moore, John I., Jr. (1977), „Dimenze rovinných posetů“, Journal of Combinatorial Theory , Series B , 22 (1): 54–67, doi : 10,1016 / 0095-8956 (77) 90048-X.
