ストラー数
 | この項目「ストラー数」は翻訳されたばかりのものです。不自然あるいは曖昧な表現などが含まれる可能性があり、このままでは読みづらいかもしれません。（原文：en:Strahler number 13:10, 16 April 2017 (UTC)） 修正、加筆に協力し、現在の表現をより自然な表現にして下さる方を求めています。ノートページや履歴も参照してください。（2017年5月） |
数学において、数学の木のストラー数（ストラーすう）またはホルトン–ストラー数（ホルトン ストラーすう）は、分岐複雑度の数値尺度である。これらの数は、Robert E. Horton (1945) と Arthur Newell Strahler (1952, 1957) によって、水文学で発展した。この応用において、彼らはストラー河川次数 (strahler stream order) と見なされ、支線の階層に基づいたストリームサイズを定義するのに使用される。彼らは、L-systems および (生物学的) 木および動物の呼吸器、循環器および階層的生物学的構造の分析において、また、高水準言語のコンパイルのためのレジスタ割り付け、およびソーシャルネットワーク分析において生じる。代替の河川次数の系 (stream order systems) は、Shreve[1][2] と Hodgkinson ら[3]によって発展した。ストラー数および shreve 系の統計的比較、流れ/リンク長の分析とともに、Smart[4] によって与えられている。
定義
[編集]この文脈におけるすべての木は、有向グラフである。葉に向かって、根から方向付けされている。言い換えれば、有向木である。ある木のあるノードの次数は、ちょうど子の数である。ある木のすべてのノードにストラー数を割り当ててもよい。ボトムアップオーダーでは、次のようになる。
- ノードが葉 (子を持ってない) なら、そのストラー数は 1 である。
- ノードがストラー数 i で 1 つの子を持っており、すべてのほかの子が i より低いストラー数を持っているならば、そのノードのストラー数は i である。
- ノードがストラー数 i で 2 つ以上の子を持ち、より大きい数を持つ子がいない場合、そのノードのストラー数は i+1 である。
アルゴリズム的には、これらの数は post-order による深さ優先探索を行うことで割り当てられる。同じ数が、木がステージのシーケンスで単純化される中での枝刈り過程で生成される。そこでは各ステージで、全葉ノードおよび次数 1 の深さのすべての葉につながるノードを除外する。ノードのストラー数は、ステージである。そこでは、このプロセスによって除外され、木のストラー数はそのノードすべてを除外するのに必要なステージの数である。ある木のストラー数のその他の等価な定義は、与えられた木に対して同相的に埋め込まれる (homeomorphically embedded) ことができるもっとも大きい完全二分木の高さである。ある木のあるノードのストラー数は、同様に、ノードの下に埋め込まれることができるもっとも大きい完全二分木の高さである。
ストラー数 i のどのノードも、少なくとも、ストラー数 i − 1 の 2 つの子孫、少なくともストラー数 i − 2 の 4 つの子孫、そして少なくとも 2i − 1 の葉の子孫を持たなければならない。それゆえ、n ノードの木において、最も大きい可能なストラー数は、log2 n + 1 である[5]。しかしながら、木が完全二分木を作らないならば、そのストラー数はこの境界よりも小さいだろう。n ノードの二分木において、選ばれた均一にランダムに、すべての可能な二分木の間で、期待される根のインデックスは log4 n に高確率でとても近くなる[6]。
応用
[編集]川のネットワーク
[編集]水文学へのストラー河川次数の応用において、河川ネットワーク (river network) 内の流れまたは川の各セグメントは、木のノードとして扱われる。次のセグメントの下流をその親として。2つの 1次流 (first order stream) が一体となるとき、彼らは 2次流 (second-order stream) を形成する。2次流が一体となるとき、彼らは 3 次流を形成する。より大きい次流に参加するより小さい次流の流れは、より大きい次数を変化させない。このようにして、1次流が2次流に参加するならば、それは2次流のままである。2次流が他の2次流と結合しない限りは、3次流にはならない。数学木と同様に、インデックス i のセグメントは少なくとも 2i − 1 の異なるインデックス 1 の支流で供給されなければならない。Shreve は、Horton と Strahler の法則はトポロジカル的にランダム分布から期待されるべきだと述べた。後にこの関係に関するレビューにおいて、この議論が、この法則が描写する特性から流れのネットワークの起源や構造を説明する一切の結論は引き出されないことを確かめた[3][7]。
流れとして資格付けするために、水文学の特徴は再帰的 (recurring) または多年生 (Perennial stream) のどちらかでなければならない。再帰的 (recurring) (または間欠性 ("intermittent")) の流れは、少なくともその年の部分の間、チャネルに水を持っている。流れまたは川のインデックスは、1 (支流の無い流れ)から12 (世界的に最も力強い川、アマゾン川の口) にわたるかもしれない。オハイオ川は、次数 8 で、ミシシッピ川は 次数 10 である。惑星上の河川の80％が1次から3次の水源であるということが推定されている[8]。
もし、川のネットワークの二分岐割合 (bifurcation ratio) が小さければ、洪水の確率が高くなる。高分岐割合が示すように、水は広がるよりもひとつのチャネルに濃縮されるためである。二分岐割合は、流域 (drainage basin) がより氾濫しやすいことを示す (別の割合 (separate ratios) と比較した場合)。
たいていのイギリスの河川は、3から5の二分岐割合を持つ。[9]
Gleyzer et al. (2004) は、地理情報システム (GIS) アプリケーション内で、ストラー流次数値を計算する方法を示した。このアルゴリズムは、RivEX ESRI ArcGIS 10.2.1 tool に実装されている。入力は、ノードで結ばれたアーク (またはエッジ) で表現された川のセンターラインのネットワークである。池の境界と川岸は、アークとして扱われるべきではない。これらは、一般に正しくないトポロジーを持った、木でないネットワークを形成するためである。
その他の階層システム
[編集]ストラーの番号付けは川だけでなく、どの階層システムの統計分析にも適用できるかもしれない。
- Arenas et al. (2004) らは、ソーシャルネットワークの分析に Horton-Strahler index の応用を描写している。
- Ehrenfeucht, Rozenberg & Vermeir (1981) らは、ストラー数の変異形 (variant) を適用した (葉で、1 の代わりに 0 からスタートする)。これを、L-systemの分析では tree-rank とよぶ。
- ストラー数は、生物学的階層にも適用されてきた (木のブランチング構造[10]および動物の呼吸器および循環器系のブランチング構造[11])。
レジスタアロケーション
[編集]高水準言語をアセンブリ言語に翻訳する際、式木 (expression tree) を評価するのに必要となるレジスタの最小数は、まさにそのストラー数である。この文脈において、ストラー数は、レジスタ数とよばれてもよい[12]。
利用できるよりも多くのレジスタを要求する式木に対して、セシィ–ウルマン法 (Sethi–Ullman) のアルゴリズムは、式木を、可能な限り効果的にレジスタを使用するマシンインストラクションシーケンスに翻訳するのに使用されてもよい。そして、中間値がレジスタからメインメモリに及ぶ回数および、結果のコンパイルコードにおけるインストラクションの全体数を最小にする。
関連するパラメータ
[編集]二分岐割合 (Bifurcation ratio)
[編集]木のストラー数に関連するのは二分岐割合である。木が、平衡 (balanced) にどれだけ近いかを描写する数である。階層における各次数 i に対して、i 番目の二分岐割合は、ni/ni + 1 である。ここで、ni は次数 i のノードの数を表す。
全体の階層の二分岐割合は、異なる次数の二分岐割合の平均で取られるかもしれない。完全二分木では、二分岐割合は 2 となる。一方、他の木はより小さい二分岐割合を持つ。 二分岐割合は無次元の数である。
経路幅 (Pathwidth)
[編集]任意の無向グラフ G の経路幅は、サブグラフとして G を含む 中間グラフ H が存在し、H の中のもっとも大きいクリーク w + 1 の頂点を持つもっとも小さい数 w として定義される。木に対して (その方向と根を忘れることで、無向グラフと見なす)、経路幅は、ストラー数とは異なる。しかし、それと密接に関係している。経路幅 w とストラー数 s の木において、不等式
- w ≤ s ≤ 2w + 2
によってこの2つの数は関連付けられる[13]。
木だけでなく、サイクルを持ったグラフを扱う経路幅の能力は、ストラー数と比較して余分な多才性を与えている。しかし、ストラー数と異なり、経路幅は全体のグラフに定義される。グラフの中の各ノードに対して別々に定義されない。
脚注
[編集]- ^ Shreve, R.L., 1966. Statistical law of stream numbers. Journal of Geology 74, 17–37.
- ^ Shreve, R.L., 1967. Infinite topologically random channel networks. Journal of Geology 75, 178–186.
- ^ a b Hodgkinson, J.H., McLoughlin, S. & Cox, M.E. 2006. The influence of structural grain on drainage in a metamorphic sub-catchment: Laceys Creek, southeast Queensland, Australia. Geomorphology, 81: 394-407.
- ^ Smart, J.S. 1968, Statistical properties of stream lengths, Water Resources Research, 4, No 5. 1001-1014.
- ^ Devroye & Kruszewski (1996).
- ^ Devroye and Kruszewski (1995, 1996).
- ^ Kirchner, J.W., 1993. Statistical inevitability of Horton Laws and the apparent randomness of stream channel networks. Geology 21, 591–594.
- ^ “Stream Order - The Classification of Streams and Rivers”. 2011年12月11日閲覧。
- ^ Waugh (2002)
- ^ Borchert & Slade (1981)
- ^ Horsfield (1976)
- ^ Ershov (1958); Flajolet, Raoult & Vuillemin (1979).
- ^ Luttenberger & Schlund (2011), using a definition of the "dimension" of a tree that is one less than the Strahler number.
参考文献
[編集]- Horton, R. E. (1945), “Erosional development of streams and their drainage basins: hydro-physical approach to quantitative morphology”, Geological Society of America Bulletin 56 (3): 275–370, doi:10.1130/0016-7606(1945)56[275:EDOSAT]2.0.CO;2.
- Strahler, A. N. (1952), “Hypsometric (area-altitude) analysis of erosional topology”, Geological Society of America Bulletin 63 (11): 1117–1142, doi:10.1130/0016-7606(1952)63[1117:HAAOET]2.0.CO;2.
- Strahler, A. N. (1957), “Quantitative analysis of watershed geomorphology”, Transactions of the American Geophysical Union 38 (6): 913–920, doi:10.1029/tr038i006p00913.
- Strahler, A. N. (1952), “Hypsometric (area-altitude) analysis of erosional topology”, Geological Society of America Bulletin 63 (11): 1117–1142, doi:10.1130/0016-7606(1952)63[1117:HAAOET]2.0.CO;2.
- Gleyzer, A.; Denisyuk, M.; Rimmer, A.; Salingar, Y. (2004), “A fast recursive GIS algorithm for computing Strahler stream order in braided and nonbraided networks”, Journal of the American Water Resources Association 40 (4): 937–946, doi:10.1111/j.1752-1688.2004.tb01057.x.
- Ehrenfeucht, A.; Rozenberg, G.; Vermeir, D. (1981), “On ETOL systems with finite tree-rank”, SIAM Journal on Computing 10 (1): 40–58, doi:10.1137/0210004, MR605602.
関連項目
[編集]- 本流 (main stem) - もっとも大きいストラー数を持つ枝に従う。