グラフとネットワーク

ランダムツリーを生成する方法は？



How Generate Random Tree



解決：

あなたは馬と迷路から木を作ることができます;-)

迷路から木へ



馬から木へ

これらの画像は、のドキュメントに記載されています。 SkeletonTransform と MorphologicalGraph 。



実際、木はいたるところにあります。任意の式は任意の木の構造を持っています。積分を取ることを想像してみてください：

積分[Sin [（1-x）/（1 + x）]、x]
 Sinの積分[（1-x）/（1 + x）]
 
これにより、からアルゴリズムを適用すると、かなりランダムなツリーが得られます。 この答え -ここでは、スタイルの最後の行のみを示しています。
 
 
 
Graph [edges、VertexLabels-> [email protected]、ImagePadding-> {{1、35}、{0、10}}、GraphLayout-> 'RadialDrawing'、GraphStyle-> 'ThickEdge'、DirectedEdges-> False]
 式からの木
 
さて、もっと深刻なことに注意してください。これを行うには、おそらくかなりの数の異なる方法があります。 @rm -rfの答えに加えて、他に6つの可能性について言及します。
 
     
  1.   ランダムツリーアグリゲーション  
    2.  
  2.   クラスカルのアルゴリズムを使用して町を接続する -平面構造のきちんとしたランダムなポイント
    3.  
  3.   再帰関数評価ステップのツリー形式 -別のアプローチの鍵を与えることができます
    4.  
  4.   画像処理 - 上記を参照
    5.  
  5.   ランダムな表現 - 上記を参照
    6.  
  6.   完璧な木をランダムに切ります 。
    7.  
 
指定した数のレベルとブランチの完全なツリーを生成できます。これは7つのレベルと3つのブランチのツリーです：
 
g = CompleteKaryTree [7、3、GraphStyle-> 'LargeNetwork'、GraphLayout-> 'RadialDrawing'、VertexShapeFunction->（{PointSize [0]、Point [＃]}＆）]
 7つのレベルと3つのブランチを持つk-aryツリー
 
次に、制御された数のエッジをドロップし、最大の連結成分を選択します。そのようなランダムなサンプルをいくつか示します。
 
rg = Subgraph [g、Sort [ConnectedComponents [Graph [RandomSample [＃、Round [Length [＃] .6]]＆@ EdgeList [g]]]、[email protected]＃1> [email protected]＃2＆] [[1]]、GraphStyle-> 'LargeNetwork'、GraphLayout-> 'RadialDrawing']＆/ @ Range [12]
 k-aryツリーのランダムな部分グラフ
 
私が使用することに注意してくださいどこでも「RadialDrawing」レイアウト。これは大きな木に適しています。もちろん、標準のものを使用できます。
 
AdjacencyGraph [＃、GraphStyle-> 'LargeNetwork'、AspectRatio-> .5]＆/ @（AdjacencyMatrix / @ rg）
 隣接グラフ
 
それでも、放射状のものは大きな木に最適です：
 
g = CompleteKaryTree [10、4、GraphStyle-> 'LargeNetwork'、GraphLayout-> 'RadialDrawing'、VertexShapeFunction->（{PointSize [0]、Point [＃]}＆）]; Subgraph [g、Sort [ConnectedComponents [Graph [RandomSample [＃、Round [Length [＃] .45]]＆@ EdgeList [g]]]、[email protected]＃1> [email protected]＃2＆] [[ 1]]、GraphStyle-> 'LargeNetwork'、GraphLayout-> 'RadialDrawing'、VertexShapeFunction->（{PointSize [0]、Point [＃]}＆）]
 k-aryツリーのサブグラフ
  
これは、の例に基づいてそれを行う1つの方法です。TreePlot。ランダムなエッジのセットを生成し、次のようにグラフを作成する関数を作成します。
 
vtx []：= Table [i RandomInteger [{0、i-1}]、{i、1、50}]; [メール保護] []
 
 
いくつか生成します：
 
Table [[email protected] []、{12}] 〜Partition〜4 //グリッド
 
  
NS 組み合わせ論 パッケージには機能があります対応するプリューファーコードからツリーを生成するためのCodeToLabeledTree []。古い機能が適応されたので 組み合わせ論  組み込みではなく、Graph []オブジェクトバージョン8で導入されたGraph []オブジェクトには、パッケージ内のコードの変更が必要です。
 
CodeToLabeledTree [l_List、opts ___]：= Module [{m = Range [Length [l] + 2]、x、i}、TreeGraph [Append [Table [x = Min [Complement [m、Drop [l、i-1] ]]; m = Complement [m、{x}]; UndirectedEdge @@ Sort [{x、l [[i]]}]、{i、Length [l]}]、UndirectedEdge @@ Sort [m]]、opts]] /; Complement [l、Range [Length [l] + 2]] == {}
これから、次のようなランダムツリーを生成できます。
 
With [{n = 50}、（*頂点の数*）BlockRandom [SeedRandom [42、Method-> 'MersenneTwister']; （*再現性のために*）CodeToLabeledTree [RandomInteger [{1、n}、n-2]、GraphLayout-> 'SpringEmbedding']]]
 プリューファーコードからのランダムグラフ
 
（NS 組み合わせ論 関数RandomTree []はこのように実装されています。）