ストラー数

数学において、数学の木のストラー数またはホルトン–ストラー数は、分岐複雑度の数値尺度である。これらの数は、first=Robert E. と first=Arthur Newell によって、水文学で発展した。この応用において、彼らはストラー河川次数  と見なされ、支線の階層に基づいたストリームサイズを定義するのに使用される。彼らは、L-systems および  木および動物の呼吸器、循環器および階層的生物学的構造の分析において、また、高水準言語のコンパイルのためのレジスタ割り付け、およびソーシャルネットワーク分析において生じる。代替の河川次数の系  は、Shreve と Hodgkinson らによって発展した。ストラー数および shreve 系の統計的比較、流れ/リンク長の分析とともに、Smart によって与えられている。

1. 定義
-----

この文脈におけるすべての木は、有向グラフである。葉に向かって、根から方向付けされている。言い換えれば、有向木である。ある木のあるノードの次数は、ちょうど子の数である。ある木のすべてのノードにストラー数を割り当ててもよい。ボトムアップオーダーでは、次のようになる。

ノードが葉  なら、そのストラー数は 1 である。
ノードがストラー数 //i// で 1 つの子を持っており、すべてのほかの子が //i// より低いストラー数を持っているならば、そのノードのストラー数は //i// である。
ノードがストラー数 //i// で 2 つ以上の子を持ち、より大きい数を持つ子がいない場合、そのノードのストラー数は //i//+1 である。アルゴリズム的には、これらの数は post-order による深さ優先探索を行うことで割り当てられる。同じ数が、木がステージのシーケンスで単純化される中での枝刈り過程で生成される。そこでは各ステージで、全葉ノードおよび次数 1 の深さのすべての葉につながるノードを除外する。ノードのストラー数は、ステージである。そこでは、このプロセスによって除外され、木のストラー数はそのノードすべてを除外するのに必要なステージの数である。ある木のストラー数のその他の等価な定義は、与えられた木に対して同相的に埋め込まれる  ことができるもっとも大きい完全二分木の高さである。ある木のあるノードのストラー数は、同様に、ノードの下に埋め込まれることができるもっとも大きい完全二分木の高さである。

ストラー数 i}} のどのノードも、少なくとも、ストラー数 //i// − 1}} の 2 つの子孫、少なくともストラー数 //i// − 2}} の 4 つの子孫、そして少なくとも 2//i// − 1}} の葉の子孫を持たなければならない。それゆえ、n}} ノードの木において、最も大きい可能なストラー数は、log2 //n// + 1}} であるDevroye。しかしながら、木が完全二分木を作らないならば、そのストラー数はこの境界よりも小さいだろう。n}} ノードの二分木において、選ばれた均一にランダムに、すべての可能な二分木の間で、期待される根のインデックスは log4 //n//}} に高確率でとても近くなる。

2. 応用
-----

2.1. 川のネットワーク
-------------

水文学へのストラー河川次数の応用において、河川ネットワーク  内の流れまたは川の各セグメントは、木のノードとして扱われる。次のセグメントの下流をその親として。2つの 1次流  が一体となるとき、彼らは 2次流  を形成する。2次流が一体となるとき、彼らは 3 次流を形成する。より大きい次流に参加するより小さい次流の流れは、より大きい次数を変化させない。このようにして、1次流が2次流に参加するならば、それは2次流のままである。2次流が他の2次流と結合しない限りは、3次流にはならない。数学木と同様に、インデックス //i// のセグメントは少なくとも 2//i//   −   1 の異なるインデックス 1 の支流で供給されなければならない。Shreve は、Horton と Strahler の法則はトポロジカル的にランダム分布から期待されるべきだと述べた。後にこの関係に関するレビューにおいて、この議論が、この法則が描写する特性から流れのネットワークの起源や構造を説明する一切の結論は引き出されないことを確かめた。

流れとして資格付けするために、水文学の特徴は再帰的  または多年生  のどちらかでなければならない。再帰的  ) の流れは、少なくともその年の部分の間、チャネルに水を持っている。流れまたは川のインデックスは、1 から12  にわたるかもしれない。オハイオ川は、次数 8 で、ミシシッピ川は 次数 10 である。惑星上の河川の80％が1次から3次の水源であるということが推定されている。

もし、川のネットワークの二分岐割合  が小さければ、洪水の確率が高くなる。高分岐割合が示すように、水は広がるよりもひとつのチャネルに濃縮されるためである。二分岐割合は、流域  がより氾濫しやすいことを示す  と比較した場合)。

たいていのイギリスの河川は、3から5の二分岐割合を持つ。

Gleyzer は、地理情報システム  アプリケーション内で、ストラー流次数値を計算する方法を示した。このアルゴリズムは、[1] ESRI ArcGIS 10.2.1 tool に実装されている。入力は、ノードで結ばれたアーク  で表現された川のセンターラインのネットワークである。池の境界と川岸は、アークとして扱われるべきではない。これらは、一般に正しくないトポロジーを持った、木でないネットワークを形成するためである。

2.2. その他の階層システム
---------------

ストラーの番号付けは川だけでなく、どの階層システムの統計分析にも適用できるかもしれない。

Arenas らは、ソーシャルネットワークの分析に Horton-Strahler index の応用を描写している。
Ehrenfeucht らは、ストラー数の変異形  を適用した 。これを、L-systemの分析では tree-rank とよぶ。
ストラー数は、生物学的階層にも適用されてきた 。

2.3. レジスタアロケーション
----------------

高水準言語をアセンブリ言語に翻訳する際、式木  を評価するのに必要となるレジスタの最小数は、まさにそのストラー数である。この文脈において、ストラー数は、レジスタ数とよばれてもよい。

利用できるよりも多くのレジスタを要求する式木に対して、セシィ–ウルマン法  のアルゴリズムは、式木を、可能な限り効果的にレジスタを使用するマシンインストラクションシーケンスに翻訳するのに使用されてもよい。そして、中間値がレジスタからメインメモリに及ぶ回数および、結果のコンパイルコードにおけるインストラクションの全体数を最小にする。

3. 関連するパラメータ
------------

3.1. 二分岐割合 
------------------------------

木のストラー数に関連するのは二分岐割合である。木が、平衡  にどれだけ近いかを描写する数である。階層における各次数 i}} に対して、i}} 番目の二分岐割合は、//ni/////n////i// + 1}} である。ここで、ni}} は次数 i}} のノードの数を表す。

全体の階層の二分岐割合は、異なる次数の二分岐割合の平均で取られるかもしれない。完全二分木では、二分岐割合は 2 となる。一方、他の木はより小さい二分岐割合を持つ。 二分岐割合は無次元の数である。

3.2. 経路幅 
--------------------

任意の無向グラフ G の経路幅は、サブグラフとして G を含む 中間グラフ H が存在し、H の中のもっとも大きいクリーク //w// + 1 の頂点を持つもっとも小さい数 //w// として定義される。木に対して 、経路幅は、ストラー数とは異なる。しかし、それと密接に関係している。経路幅 //w// とストラー数 //s// の木において、不等式

//w// ≤ s ≤ 2//w// + 2によってこの2つの数は関連付けられる。

木だけでなく、サイクルを持ったグラフを扱う経路幅の能力は、ストラー数と比較して余分な多才性を与えている。しかし、ストラー数と異なり、経路幅は全体のグラフに定義される。グラフの中の各ノードに対して別々に定義されない。

4. 脚注
-----

5. 参考文献
-------

first=R. E..
last=Strahler.
last=Strahler.
last=Strahler.
last1=Gleyzer.
last1 = Ehrenfeucht .

6. 関連項目
-------

本流  - もっとも大きいストラー数を持つ枝に従う。