Náhodný strom

V teorii pravděpodobnosti náhodný strom je strom definován pomocí zákona pravděpodobnosti na souboru stromů (v tom smyslu, že v grafu). Například náhodný strom s n uzly lze vybrat náhodně ze všech stromů s n uzly podle zákona pravděpodobnosti, například s jednotným zákonem . Existují i jiné způsoby generování určitých konkrétních stromů (například binární). Na Galton-Watson stromy jsou speciální případy náhodných stromů.

Jednotná hřídel

Jednotný strom s n uzly je strom vybrána náhodně z třídy stromů s jednotným zákona pravděpodobnosti v této třídě. Někdy je možné spojit jejich zákon se zákonem Galton-Watsonova stromu .

Rovnoměrně zakořeněný rovinný strom

Zvažte třídu zakořeněných (neoznačených) planárních stromů s n uzly.

Jednotný zakořeněné planární strom má stejný zákon pravděpodobnosti jako Galton-Watson strom podmíněné mít n uzly a jejichž reprodukční práva je geometrický zákon parametru 1/2.

Jednotný označený a zakořeněný strom

Zvažte třídu označených a zakořeněných (nerovinných) stromů s n uzly.

Značená a kořeny jednotný strom má stejný zákon pravděpodobnosti jako Galton-Watson strom podmíněné mít n uzly a jehož reprodukce zákon je zákon Poissonovo parametru 1.

Jednotný binární strom

Zvažte třídu binárních stromů s n uzly. Pokud vezmeme v úvahu pouze vnitřní uzly binárního stromu, to znamená, že odstraníme listy stromu, zůstanou tři typy uzlů:

uzly bez vláken, které dříve měly 2 listová vlákna,
uzly s 1 vláknem, jehož druhým vláknem byl dříve list (všimněte si, že existují dvě možnosti pro umístění listu: pravý nebo levý),
uzly se 2 nitěmi, z nichž žádný nebyl dříve list.

Přidáním listů na všechna volná místa najdeme počáteční binární strom.

Tak, jednotný binární strom má stejný zákon pravděpodobnosti jako Galton-Watson strom podmíněné mít n uzly a jehož reprodukce zákon je binomické zákon B (2,1 / 2) . To znamená, že každý uzel má 1/4 pravděpodobnost, že bude mít 0, 1/4 bude mít 2 syny a 1/2 že bude mít 1 syna.

Jednotný krycí strom

Nechť G je graf. Kostry ( spanning tree v angličtině) G je subgraph z G obsahující všechny uzly a část okraje, a které je hřídel , to znamená, An neorientovaný graf , acyklické a související . Jednotný kostra je kostra náhodně vybraný ze všech kostry z G se stejnou pravděpodobností.

Nechť V a w dvěma uzly G . Celý spanning tree obsahuje přesně jednu cestu mezi v a w . Vezmeme-li tuto cestu v jednotném kostře, získáme náhodnou cestu. Zákon o této cestě je stejná jako práva na náhodné procházky vymazány smyček ( loop-vymazány náhodné procházky v angličtině) počínaje objem a zastavil w .

Okamžitým důsledkem je náhodná chůze vymazané smyčky symetrická ve svých počátečních a koncových bodech. Přesněji řečeno, náhodná procházka s vymazanou smyčkou počínaje od v a zastavená na w má stejný zákon jako náhodná chůze s obrácenou smyčkou začínající od w a zastavená na v . Což není triviální.

Existuje několik algoritmů pro generování uniformních koster. Pojďme zde uvést Wilsonův algoritmus . Pojďme vzít dva uzly a provést náhodnou procházku s vymazanými smyčkami z jednoho bodu do druhého. Dále vezměte třetí uzel, který není v takto konstruované cestě, a proveďte náhodnou procházku s vymazanou smyčkou, dokud nesplní cestu, která byla dříve vytvořena. začneme znovu, dokud strom nepokryje všechny uzly. A konečně, bez ohledu na to, jakou metodu použijete k výběru počátečních uzlů, získáte stejný zákon o kostře, jednotný zákon.

Graf může mít různé kostry. Můžeme tedy každému váhu přiřadit váhu, což je hodnota představující pravděpodobnost, že bude vybrán (nízká váha pro vysokou pravděpodobnost). Rozpětí stromu má tedy váhu, která je součtem hmotností jeho hran. Minimální pokrývající strom nebo minimální pokrývající strom je pak krycí strom s hmotností menší než nebo se rovná hmotnosti všech ostatních krycích stromů.

Můžeme také přiřadit náhodnou váhu každé hraně pomocí jednotných náhodných proměnných přes [0,1] nezávisle. Minimální náhodný STP je pak strom spanning 0 minimální hmotnost.

Náhodný binární strom

V teorii pravděpodobnosti a v informatice , je náhodná binární strom je binární strom vybrán náhodně pomocí zákona pravděpodobnosti na sadu binárních stromů. Používá se několik metod: binární stromy vytvořené postupným vkládáním uzlů podle náhodné permutace a binární stromy vybrané diskrétním jednotným zákonem , binární separací stromů.

Náhodnou obměnou

Pro libovolnou sadu čísel vytvoříme binární vyhledávací strom vložením každého nového čísla jako listu stromu. Poloha vložení je určena dichotomickým hledáním na předchozích číslech. Například pro sekvenci (1,3,2) je 1 kořen, 3 je pravé dítě 1 a 2 je levé dítě 3. Existuje 6 různých permutací (1,2,3), ale existuje je pouze 5 různých stromů, (2,1,3) a (2,3,1) dávají stejný strom.

Jednotné právo

Počet binárních stromů s n uzly je n-tým katalánským číslem . Každý strom má tedy pravděpodobnost, že se objeví. Rémy algoritmus generuje v lineárním čase jednotný binární strom. $\ scriptstyle C_n = \ frac {(2n)!} {n! (n + 1)!}$ $\ scriptstyle 1 / C_n$

Binární oddělení

Můžeme generovat binární náhodné stromy s n uzly zvážením náhodné proměnné X s hodnotami v] 0,1 [. První celá čísla Xn (s ohledem na celočíselnou část) jsou přiřazena levému podstromu, další celé číslo bude kořen a ostatní do pravého podstromu. Pro každý podstrom opakujeme. Pokud je X vybráno rovnoměrně v průběhu intervalu, výsledný strom je stejný jako binární náhodný strom konstruovaný s náhodnou permutací, když je kořen vybrán jednotně. Devroye a Kruszewski ukazují, že pokud X dodržuje zákon beta a vhodně reprezentuje hrany, lze takto generované stromy použít k simulaci fylogenetických stromů .

Galton-Watsonovy stromy

Galton-Watsonův strom představuje genealogii Galton-Watsonova procesu, ve kterém má každý uzel náhodný počet dětí: každému uzlu jsou přiřazeny nezávislé náhodné proměnné se stejným zákonem reprodukce.

Dodatky

Související články

Poznámky a odkazy

JL Rémy, Iterativní proces počítání binárních stromů a jeho aplikace na jejich náhodnou generaci , RAIRO, Informatique Théorique, 19.2 (1985), str. 179-195
Donald E. Knuth, The Art of Computer Programming , roč. 4.4 ( Generování všech stromů ), Addison Wesley, str. 18
L. Devroye, P. Kruszewski, Botanická krása náhodných binárních stromů , Přednášky v informatice, Springer-Verlag , sv. 1027 (1996), s. 166–177, doi 10.1007 / BFb0021801.

(en) M. Drmota, Random trees - An Interplay between Combinatorics and Probability , Springer Verlag, Wien / New York (2009), ( ISBN 978-3-211-75355-2 )