シュトララー数

数学において、数学的木のシュトラール数またはホートン・シュトラール数は、その木の分岐の複雑さを数値的に表す尺度です。

これらの数値は、ロバート・E・ホートン （1945年）とアーサー・ニューウェル・シュトレーラー（1952年、1957年）によって、河川や小川の複雑さを測定する方法として水文学の分野で最初に開発されました。この分野では、これらはシュトレーラー川次数 と呼ばれ、支流の階層に基づいて川のサイズを定義するために使用されます。同じ数値は、 Lシステムや（生物学的）樹木や動物の呼吸器系や循環器系などの階層的な生物学的構造の分析、高水準プログラミング言語のコンパイルのためのレジスタ割り当て、ソーシャルネットワークの分析でも使用されます。

このコンテキストにおけるすべてのツリーは、ルートからリーフに向かう有向グラフです。言い換えると、ツリーは樹状です。ツリー内のノードの次数は、そのノードの子の数です。次のように、ツリーのすべてのノードに、ボトムアップの順序でシュトララー数を割り当てることができます。

• ノードがリーフ（子を持たない）の場合、その Strahler 数は 1 になります。
• ノードに Strahler 数iの子が 1 つあり、他のすべての子の Strahler 数がi未満である場合、ノードの Strahler 数は再びiになります。
• ノードに Strahler 数iの子が 2 つ以上あり、より大きな数を持つ子がない場合、ノードの Strahler 数はi  + 1 になります。

ツリーの Strahler 数は、そのルート ノードの数です。

アルゴリズム的には、これらの番号は、深さ優先探索を実行し、各ノードの番号を後順に割り当てることによって割り当てることができます。同じ番号は、ツリーを一連の段階で簡略化する剪定プロセスによっても生成できます。このプロセスでは、各段階ですべてのリーフ ノードと、リーフにつながる次数 1 のノードのすべてのパスが削除されます。ノードの Strahler 数は、このプロセスによって削除される段階であり、ツリーの Strahler 数は、すべてのノードを削除するのに必要な段階の数です。ツリーの Strahler 数の別の同等の定義は、指定されたツリーに同相的に埋め込むことができる最大の完全二分木の高さです。ツリー内のノードの Strahler 数は、同様に、そのノードの下に埋め込むことができる最大の完全二分木の高さです。

シュトララー数iを持つノードは、シュトララー数i − 1を持つ子孫が少なくとも 2 つ、シュトララー数i − 2 を持つ子孫が少なくとも 4 つなど  、また葉の子孫が少なくとも 2 ^{i  − 1 個なければなりません。したがって、} n個のノードを持つ木では、最大のシュトララー数は log ₂  n  + 1です。 ^[1]ただし、木が完全な二分木を形成しない限り、そのシュトララー数はこの境界よりも小さくなります。すべての可能な二分木から一様にランダムに選択されたnノードの二分木では、ルートの期待インデックスは、高い確率で log ₄ nに非常に近くなります。^[2] 

シュトレーラーの河川順序を水文学に応用すると、河川網内の河川または川の各セグメントはツリーのノードとして扱われ、下流の次のセグメントがその親として扱われる。2 つの1 次ストリームが合流すると、 2 次ストリームが形成される。2 つの 2 次ストリームが合流すると、3 次ストリームが形成される。より低い次数のストリームがより高い次数のストリームに合流しても、より高い次数のストリームの順序は変更されない。したがって、1 次ストリームが 2 次ストリームに合流する場合、それは 2 次ストリームのままである。2 次ストリームが別の 2 次ストリームと合流して初めて、3 次ストリームになる。数学的なツリーと同様に、インデックスiのセグメントには、インデックス 1 の少なくとも 2 ^{i  − 1}の異なる支流が流れ込む必要がある。その後の関係の検討によりこの主張は裏付けられ、法則が示す特性からは河川網の構造や起源を説明する結論を導き出すことはできないことが立証された。^{[3] [4]}

河川として認められるためには、水文学的特徴は循環的または通年的である必要があります。循環的（または「断続的」）河川は、少なくとも 1 年のうちの一部は水路に水が流れています。河川または小川の指数は、1（支流のない河川）から 12（世界で最も勢いのあるアマゾン川の河口）までの範囲になります。オハイオ川は 8 位、ミシシッピ川は10 位です。地球上の小川の 80% は、第 1 位から第 3 位の源流河川であると推定されています。^[5]

河川ネットワークの分岐率が高い場合、洪水の可能性が高くなります。また、集中する時間も短くなります。^{[6]分岐率は、個別の比率を見ることで、}流域のどの部分が比較的洪水の可能性が高いかを示すこともできます。ほとんどの英国の河川の分岐率は3〜5です。^[7]

Gleyzer ら (2004) は、 GISアプリケーションで Strahler 流次数値を計算する方法について説明しています。このアルゴリズムは、ESRI ArcGIS Pro 3.3.x ツールの RivEX によって実装されています。このアルゴリズムへの入力は、ノードで結合されたアーク (またはエッジ) として表される水域の中心線のネットワークです。湖の境界と川岸は、アークとして使用しないでください。これらは通常、不正確なトポロジを持つ非ツリー ネットワークを形成します。

代替的な河川順序付けシステムは、シュリーブ^{[8] [9]}とホジキンソンら^[3]によって開発されました。ストララーとシュリーブのシステムの統計的比較と、河川/リンクの長さの分析は、スマート^[10]によって提供されています。

シュトララー番号は、河川だけでなく、あらゆる階層システムの統計分析に適用できます。

• Arenasら（2004）は、ソーシャルネットワークの分析におけるHorton-Strahler指標の応用について説明しています。
• Ehrenfeucht、Rozenberg、Vermeir (1981) は、Strahler 番号付けの変形 (葉で 1 ではなく 0 から始まる) をtree-rankと呼び、 L システムの解析に適用しました。
• シュトララー番号は、樹木の分岐構造^[11]や動物の呼吸器系や循環器系^{[12]などの生物学的階層にも適用されている。}

高級プログラミング言語をアセンブリ言語に変換する場合、式ツリーを評価するために必要なレジスタの最小数は、まさにそのストララー数である。この文脈では、ストララー数はレジスタ数とも呼ばれる。^[13]

使用可能なレジスタよりも多くのレジスタを必要とする式ツリーの場合、Sethi-Ullman アルゴリズムを使用して、式ツリーを、レジスタを可能な限り効率的に使用するマシン命令のシーケンスに変換し、中間値がレジスタからメイン メモリにスピルされる回数と、結果として得られるコンパイル済みコード内の命令の合計数を最小限に抑えることができます。

木のストララー数と関連して、分岐比があります。これは、木がバランスにどれだけ近いかを表す数値です。階層内の各順序iについて、 i番目の分岐比は

${\displaystyle {\frac {n_{i}}{n_{i+1}}}}$

ここで、n _{i は}順序iのノードの数を表します。

階層全体の分岐比は、異なる次数の分岐比を平均することで得られます。完全な二分木では分岐比は 2 になりますが、他の木では分岐比が大きくなります。これは無次元数です。

任意の無向グラフGのパス幅は、 Gを部分グラフとして含む区間グラフHが存在し、 H内の最大クリークがw + 1 個の頂点を持つような最小の数wとして定義できます。木 (方向とルートを忘れて無向グラフとして表示) の場合、パス幅は Strahler 数とは異なりますが、密接に関連しています。パス幅wと Strahler 数s を 持つ木では、これら 2 つの数は不等式^{[14]によって関連しています。}

w ≤ s ≤ 2 w + 2 です。

ツリーだけでなくサイクルを含むグラフを処理できるため、Strahler 数と比較して、pathwidth の汎用性が向上します。ただし、Strahler 数とは異なり、pathwidth はグラフ全体に対してのみ定義され、グラフ内の各ノードに対して個別に定義されるわけではありません。

• 川の幹線。通常は、最も高いシュトララー数を持つ支流をたどって見つけます。
• Pfafstetter コーディング システム

• アレナス、A.ダノン、Ｌ．ディアス・ギレラ、A.グライザー首相。 Guimerá, R. (2004)、「ソーシャル ネットワークにおけるコミュニティ分析」、European Physical Journal B、38 (2): 373–380、arXiv : cond-mat/0312040、Bibcode :2004EPJB...38..373A、doi :10.1140/epjb/e2004-00130-1、S2CID  9764926。
• ボルヒャート、ロルフ; スレイド、ノーマン A. (1981)、「分岐比と樹木の適応形状」、植物誌、142 (3): 394–401、doi :10.1086/337238、hdl : 1808/9253、JSTOR  2474363、S2CID  84145477。
• Devroye, Luc ; Kruszewski, Paul (1995)、「ランダムツリーの Horton–Strahler 数に関する注記」、Information Processing Letters、56 (2): 95–99、doi :10.1016/0020-0190(95)00114-R。
• デヴロイ、L. ; Kruszewski, P. (1996)、「ランダム試行の Horton–Strahler 数について」、RAIRO Informatique Théorique et Applications、30 (5): 443–456、doi : 10.1051/ita/1996300504431、MR  1435732
• Ehrenfeucht, A. ; Rozenberg, G. ; Vermeir, D. (1981)、「有限木ランクを持つ ETOL システムについて」、SIAM Journal on Computing、10 (1): 40–58、doi :10.1137/0210004、MR  0605602。
• Ershov, AP (1958)、「算術演算のプログラミングについて」、Communications of the ACM、1 (8): 3–6、doi : 10.1145/368892.368907、S2CID  15986378。
• Flajolet, P. ; Raoult, JC; Vuillemin, J. (1979)、「算術式の評価に必要なレジスタの数」、理論計算機科学、9 (1): 99–125、doi : 10.1016/0304-3975(79)90009-4。
• Gleyzer, A.; Denisyuk, M.; Rimmer, A.; Salingar, Y. (2004)、「編組および非編組ネットワークにおける Strahler 流序を計算するための高速再帰 GIS アルゴリズム」、Journal of the American Water Resources Association、40 (4): 937–946、Bibcode :2004JAWRA..40..937G、doi :10.1111/j.1752-1688.2004.tb01057.x、S2CID  128399321。
• ホースフィールド、キース (1976)、「呼吸器系への応用における分岐木の数学的性質」、数理生物学紀要、38 (3): 305–315、doi :10.1007/BF02459562、PMID  1268383、S2CID  189888885。
• ホートン、RE（1945）、「河川とその流域の侵食発達：定量的形態学への水理物理学的アプローチ」、アメリカ地質学会紀要、56（3）：275–370、doi：10.1130/0016-7606（1945）56[275：EDOSAT]2.0.CO;2、S2CID  129509551。
• Lanfear, KJ (1990)、「Strahler 流次数を自動的に計算する高速アルゴリズム」、アメリカ水資源協会誌、26 (6): 977–981、Bibcode :1990JAWRA..26..977L、doi :10.1111/j.1752-1688.1990.tb01432.x。
• ルッテンバーガー、マイケル。 Schlund、Maxmilian (2011)、冪等性を超えた Parikh の定理の拡張、arXiv : 1112.2864、Bibcode :2011arXiv1112.2864L
• Strahler, AN (1952)、「侵食地形の高度測定（面積-高度）分析」、アメリカ地質学会紀要、63 (11): 1117–1142、doi :10.1130/0016-7606(1952)63[1117:HAAOET]2.0.CO;2。
• Strahler, AN (1957)、「流域地形の定量分析」、アメリカ地球物理学連合誌、38 (6): 913–920、Bibcode :1957TrAGU..38..913S、doi :10.1029/tr038i006p00913。
• ウォー、デイビッド（2002）、地理学、統合アプローチ（第3版）、ネルソン・ソーンズ。