Grafi In Omrežja

Kako ustvariti naključno drevo?

How Generate Random Tree



Rešitev:

Iz konjev in labirintov lahko naredite drevesa ;-)

labirint na drevo



konj na drevo



Slike za njih najdete v dokumentaciji za SkeletonTransform in Morfološki graf .



Pravzaprav so drevesa povsod. Samovoljni izrazi imajo strukturo poljubnih dreves. Predstavljajte si, da vzamete integral:

Integrirajte [Sin [(1 - x)/(1 + x)], x]
 integral Sin [(1 - x)/(1 + x)]
 
Tako boste dobili precej naključno drevo, če uporabite algoritem iz ta odgovor - Tukaj podajam samo zadnjo vrstico s slogi:
 
 
 
Graf [robovi, oznake VertexLabels -> [zaščiteno z e -pošto], ImagePadding -> {{1, 35}, {0, 10}}, GraphLayout -> 'RadialDrawing', GraphStyle -> 'ThickEdge', DirectedEdges -> False]
 drevo iz izraza
 
Zdaj pa resneje: verjetno obstaja kar nekaj različnih načinov za to. Poleg odgovora @rm -rf omenjam še 6 drugih možnosti.
 
     
  1.   Naključno združevanje dreves  
    2.  
  2.   Povezovanje mest z uporabo Kruskalovega algoritma - Čiste, naključne točke pri konstrukciji ravnine
    3.  
  3.   Drevesna oblika korakov vrednotenja rekurzivne funkcije - lahko da ključ do drugega pristopa
    4.  
  4.   Obdelava slik - glej zgoraj
    5.  
  5.   Naključni izrazi - glej zgoraj
    6.  
  6.   Naključno porežite popolno drevo .
    7.  
 
Ustvarite lahko celotno drevo z določenim številom ravni in vej. Tu je drevo s 7 ravnmi in 3 vejami:
 
g = CompleteKaryTree [7, 3, GraphStyle -> 'LargeNetwork', GraphLayout -> 'RadialDrawing', VertexShapeFunction -> ({PointSize [0], Point [#]} &)]
 k-arno drevo s 7 ravnmi in 3 vejami
 
Nato spustite nadzorovano število robov in izberite največjo priključeno komponento. Tukaj je nekaj takih naključnih vzorcev:
 
rg = Podgraf [g, Razvrsti [ConnectedComponents [Graf [RandomSample [ #, Round [Length [ #] .6]] &@EdgeList [g]]]], [email protected] #1> [email protected] #2 &] [[1]], GraphStyle -> 'LargeNetwork', GraphLayout -> 'RadialDrawing'] & /@ Range [12]
 naključni podgrafi k-arnega drevesa
 
Upoštevajte, da uporabljamPostavitev 'RadialDrawing' povsod, kar je dobro za velika drevesa. Seveda lahko uporabite standardno:
 
AdjacencyGraph [#, GraphStyle -> 'LargeNetwork', AspectRatio -> .5] & /@ (AdjacencyMatrix /@ rg)
 graf sosednosti
 
Kljub temu je radialni odličen za velika drevesa:
 
g = CompleteKaryTree [10, 4, GraphStyle -> 'LargeNetwork', GraphLayout -> 'RadialDrawing', VertexShapeFunction -> ({PointSize [0], Point [#]} &)]; Podgraf [g, Razvrsti [Povezane komponente] 1]], GraphStyle -> 'LargeNetwork', GraphLayout -> 'RadialDrawing', VertexShapeFunction -> ({PointSize [0], Point [#]} &)]
 podgraf k-arnega drevesa
  
Tu je en način, kako to narediti na podlagi primera vTreePlot. Ustvarjamo funkcijo za ustvarjanje naključnega niza robov in oblikujemo graf kot:
 
vtx []: = Tabela [i RandomInteger [{0, i - 1}], {i, 1, 50}]; [zaščiteno po e -pošti] []
 
 
Ustvari več:
 
Tabela [[zaščitena e -pošta] [], {12}] ~ Particija ~ 4 // Mreža
 
  
The Kombinatorika paket ima funkcijoCodeToLabeledTree [] za ustvarjanje dreves iz njihovih ustreznih kod Prüfer. Ker je bila stara funkcija prilagojena za Kombinatorika  Objekti Graph [], v nasprotju z vgrajenimiObjekti Graph [], predstavljeni v različici 8, so potrebne nekatere spremembe kode v paketu:
 
CodeToLabeledTree [l_List, opts___]: = Modul [{m = Razpon [Dolžina [l] + 2], x, i}, TreeGraph [Dodaj [Tabela [x = Min [Dopolnilo [m, Padec [l, i - 1]) ]]; m = komplement [m, {x}]; UndirectedEdge @@ Sort [{x, l [[i]]}], {i, Length [l]}], UndirectedEdge @@ Sort [m]], opts]] /; Dopolnilo [l, obseg [dolžina [l] + 2]] == {}
Iz tega lahko ustvarite naključno drevo tako:
 
Z [{n = 50}, ( * število oglišč *) BlockRandom [SeedRandom [42, Metoda -> 'MersenneTwister']; ( * za ponovljivost *) CodeToLabeledTree [RandomInteger [{1, n}, n - 2], GraphLayout -> 'SpringEmbedding']]]
 naključni graf iz Prüferjeve kode
 
( Kombinatorika funkcijoRandomTree [] je izveden na ta način.)